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

给定一棵树，我想按后序从 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

您的代码存在几个问题:

• 在 else 情况下，您未设置数字；
• 当树有一个 child 时，您不执行逻辑；和
• 您不跟踪计数器增加了多少。

您可以通过在分配号码后返回计数值来解决这些问题。所以类似:

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

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

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)