Python 后序节点数

Question

我有一个二叉树，其节点如下所示。

class Node:
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.number = None
        self.left = left
        self.right = right

给定一棵树，我想按照 post 的顺序从 0 开始给它编号。我想做的一个例子

>>> left = Node(None, Node(3), Node(2))
>>> right = Node(None, Node(9), Node(10))
>>> node = Node(None, left, right)
>>> number(node)
>>> tree.left.number, tree.right.number, tree.number
0, 1, 2

但是，我无法为递归部分找到正确的案例。

我正在尝试

def number(node, count=0):
    if not node.left and not node.right:
        node.number = count
        count += 1
    else:
        number(node.left, count)
        number(node.right, count)

Answer 1

至少有两个问题：

你只给叶节点编号。
count是一个数字，不能更改"by reference"。

我建议这样（作为一般想法）：

def number(tree, count=0):
    node.number = count
    count += 1
    if node.left:
        count = number(node.left, count) + 1
    if node.right:
        count = number(node.right, count) + 1
    return count

Answer 2

您的代码有几个问题：

你没有设置 else 情况下的number；
当树有一个 child 时，您不执行实现逻辑；和

您没有跟踪计数器增加了多少。

您可以通过在分配号码后返回count值来解决这些问题。所以像：

def number(tree, count=0): # ... return new_count

现在的问题是如何给tree及其children分配编号。您可以通过首先检查左侧 child 来做到这一点。如果不是 None，则在 tree.left 上递归调用 number(..) 并存储返回计数。接下来检查右边的 child 并做同样的事情。最后，您将更新后的计数分配给 tree 本身和 return 结果。所以像：

def number(tree, count=0): if tree.left is not None: count = number(tree.left,count) if tree.right is not None: count = number(tree.right,count) tree.number = count return count+1

运行控制台中的这个：

>>> leftleft = Node(3) >>> leftright = Node(2) >>> left = Node(None,leftleft,leftright) >>> rightleft = Node(9) >>> rightright = Node(10) >>> right = Node(None,rightleft,rightright) >>> node = Node(None, left, right) >>> number(node) 7 >>> left.number,right.number,node.number (2, 5, 6) >>> leftleft.number,leftright.number,left.number,rightleft.number,rightright.number,right.number,node.number (0, 1, 2, 3, 4, 5, 6)

Python 后序节点数

Python Number nodes in postorder

python

tree

binary-tree

postorder