python - 二叉树不显示当前 Python 的节点

Question

我正在尝试使用 insert 和 preorder 方法实现二叉树。

向树中添加元素后，仅显示一个元素。

有人可以告诉我我错在哪里吗？

下面是代码:

class Node(object):

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

    def __repr__(self):
        return '{}'.format(self.value)

class BinaryTree(object):

    def __init__(self, root=None):
        self.root = root

    def add(self, value):
        val = self.root
        if not val:
            self.root = value
            val = value

        elif not val.left:
            val = value
        elif not val.right:
            val = value
        else:
            self.left = val.left.add(value)
        return val

    def preorder(self):
        val = self.root
        if not val: # this will handle the case when root node is None.
            return 
        print(val)
        if val.left:
            val.left.preorder()
        if val.right:
            val.right.preorder()


def main():

    binary_tree = BinaryTree()

    print("Adding nodes to the tree")
    for i in range(1, 11):
        node = Node(i)
        binary_tree.add(node)

    print("Printing preorder...")
    binary_tree.preorder()

if __name__ == '__main__':
    main()

输出

Adding nodes to the tree
Printing preorder...
1

Answer 1

您的代码有一些不同的错误。有些与修改 self.root(或失败)的方式有关，其他则与尝试对错误类型进行递归有关。

第一个问题(这就是代码无提示失败的原因)与 BinaryTree.add 方法有关，该方法在树为空时不执行任何操作。问题是您将局部变量 val 初始化为等于根节点(如果有的话)，然后将其重新绑定(bind)到其他值。但这根本不会改变根值，只会改变本地 val 变量。

我建议你把val全部去掉，直接读写self.root。然后您实际上会取得一些进展，并看到其他问题。

这是一个开始:

def add(self, value):
    if self.root is None:
        self.root = value
    elif self.root.left.left is None:
        self.root.left = value
    ...

我提到的其他问题都很相似，不过一个出现在 BinaryTree.add 中，另一个出现在 BinaryTree.preorder 中。问题是您尝试对根节点的子节点之一调用相同的方法(add 或 preorder)。但节点是 Node 实例，并且没有您在 BinaryTree 类中定义的方法。

这个问题没有上一个问题那么明显的解决方案。一种想法可能是将方法的逻辑移至 Node 类(您可以在其中轻松递归)，并仅将空树处理代码保留在 BinaryTree 方法中(其他所有事情都委托(delegate)给根节点)。