1

我有一个带有如下所示节点的二叉树。

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)
4

2 回答 2

1

至少有两个问题：

  • 您仅对叶节点编号。
  • count是一个数字，不能“通过引用”更改。

我建议这样的事情（作为一个总体思路）：

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
于 2017-02-25T16:56:08.010 回答
1

您的代码有几个问题：

  • 您没有设置在案例number中；else
  • 当树有一个孩子时，您不会执行逻辑；和
  • 您不会跟踪计数器增加了多少。

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

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

现在的问题是如何为 thetree及其子代分配数字。您可以通过首先检查左孩子来做到这一点。如果不是None，则number(..)递归调用tree.left并存储返回计数。接下来，您检查正确的孩子并做同样的事情。最后，您将更新的计数分配给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)
于 2017-02-25T16:56:19.643 回答