遍历二叉搜索树时出错 - Python

Question

我正在尝试运行树遍历的经典算法。我创建了一个示例树并测试了 preorder、inorder 和 postorder 算法是否正常工作。但是在测试之后我得到了不正确的结果。当我运行从节点 A 开始的 preorder 算法时，我得到这个序列 {A,C,H,D,G}，当我应该得到{A,C,D,H,G}.

我不认为我在代码的遍历部分遗漏了什么，但也许我在树定义中。我自己看不到错误。

class Node:
    id = 0
    def __init__(self,value):
        self.id = id
        Node.id += 1
        self.value = value
        self.left_child = None
        self.right_child = None

    def insert_left_child(self, new_node):
        if self.is_leaf():
            self.insert_left_child(new_node);
        else:
            # As there is already a left child, the pointers must be
            # redistributed to include the new child. 
            current_left_child = self.left_subtree()
            self.insert_left_child(new_node)
            new_node.insert_left_child(current_left_child)

    def insert_right_child(self, new_node):
        if self.is_leaf():
            self.insert_right_child(new_node);
        else:
            # As there is already a right child, the pointers must be
            # redistributed to include the new child.
            current_right_child = self.right_subtree()
            self.insert_right_child(new_node)
            new_node.insert_right_child(current_right_child)

    def left_subtree(self):
        return self.left_child

    def right_subtree(self):
        return self.right_child

    def insert_left_child(self,child_node):
        self.left_child = child_node

    def has_left_children(self):
        return self.left_child != None

    def insert_right_child(self,child_node):
        self.right_child = child_node

    def has_right_children(self):
        return self.right_child != None

    def is_leaf(self):
        return (not self.has_left_children()) & (not self.has_right_children())


class BinaryTree:
    def __init__(self):
        self.root = Node('root')

    def preorder(self,current_node = None):
        if current_node is None:
            current_node = self.root

        print current_node.value
        if current_node.has_left_children():
            self.inorder(current_node.left_subtree())
        if current_node.has_right_children():
            self.inorder(current_node.right_subtree())

    def inorder(self,current_node = None):
        if current_node is None:
            current_node = self.root

        if current_node.has_left_children():
            self.inorder(current_node.left_subtree())
        print current_node.value
        if current_node.has_right_children():
            self.inorder(current_node.right_subtree())

    def postorder(self,current_node = None):
        if current_node is None:
            current_node = self.root

        if current_node.has_left_children():
            self.inorder(current_node.left_subtree())
        if current_node.has_right_children():
            self.inorder(current_node.right_subtree())
        print current_node.value

# Main routine

#           root
#       A           B
#     C   D       E   F
#        H G

tree = BinaryTree()

A = Node('A')
B = Node('B')
C = Node('C')
D = Node('D')
E = Node('E')
F = Node('F')
G = Node('G')
H = Node('H')

tree.root.insert_left_child(A)
tree.root.insert_right_child(B)
A.insert_left_child(C)
A.insert_right_child(D)
B.insert_left_child(E)
B.insert_right_child(F)
D.insert_left_child(H)
D.insert_right_child(G)

tree.preorder(A)

Answer 1

您从 preorder 方法调用 inorder 方法。所以当你在树中越来越深时改变算法：

    if current_node.has_left_children():
        self.inorder(current_node.left_subtree())
    if current_node.has_right_children():
        self.inorder(current_node.right_subtree())

应该是：

    if current_node.has_left_children():
        self.preorder(current_node.left_subtree())
    if current_node.has_right_children():
        self.preorder(current_node.right_subtree())

Answer 2

关于这段代码有很多要说的。您应该去掉所有多余的 accessor-methods，并立即访问左右 children。另外，考虑制作例如is_leaf 一个属性而不是一个方法。但可能导致您出错的原因如下：

class Node:
    id = 0
    def __init__(self,value):
        self.id = id
        Node.id += 1

这并不如您所想。它将内置函数 "id" 分配给您的 ID，从而使所有节点都具有相同的 ID。

要解决此问题，请使用 Node.id，或者更好的方法是：

from itertools import count


class Node(object): # if on python3, you don't need to inherit from object

    IDGEN = count()

    def __init__(self, value):
        self.id = self.IDGEN.next()
        ...

Answer 3

此处出现复制粘贴错误，您在 preorder（和 postorder）中错误地调用了 inorder。

遍历二叉搜索树时出错 - Python

Error while traversing binary search tree - Python

python

binary-tree

traversal