时间戳

首页 > 解决方案 > Python - 提高树数据结构的效率

python - Python - 提高树数据结构的效率

问题描述

我目前正在研究 python 中的 Tree 数据结构。目前，我正在尝试计算子树值，其中子树值等于给定节点子树中节点的最大值。例如对于给定的树：

       A(5)
       / \
     C(2) D(8)
      |
     B(10)

C 的子树值为 10，A 的子树值为 10，D 的子树值为 8，依此类推。我有以下代码用于将子树值向上传播（因为每个节点都有一个“subtree_value” element) 但我似乎无法改进我的算法。最初我使用递归，然后切换到嵌套循环，因为我对递归不是很有经验。但是，有什么方法可以在不需要嵌套循环的情况下做到这一点？

        node = subtree_a
        while node.parent != None: #iterates up the list until it reaches the root node
            children = node.parent.children
            for child in children:
                if (child.subtree_value > node.parent.subtree_value): #updates subtree value of parent based on largest child key
                    node.parent.set_subtree_val(child.subtree_value) 
            node = node.parent

标签： pythonperformancetree

解决方案

推荐阅读