python - 预购打印 BST

Question

r我正在尝试以预购形式打印出我的二叉树，但是我遇到了这些错误。我还在学习python，所以我不太确定发生了什么。但我认为我的打印功能无法正常工作。不太清楚为什么 preorder_print 存在全局名称问题 =/

我的预期输出是

pre order:
4
2
1
3
8
6
10

输出：

pre order:
<BST_tree.Node instance at 0x0000000002AA0988>
<BST_tree.Node instance at 0x0000000002AA0E08>
<BST_tree.Node instance at 0x0000000002AA0E88>

我的代码：

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


def BST_Insert(root, node):     # root --> root of tree or subtree!
    if root.value is None:
        root = node             # beginning of tree
    else:
        if root.value > node.value:     # go to left
            if root.left is None:
                root.left = node
            else:
                BST_Insert(root.left, node)
        else:
            if root.value < node.value:    # go to right      
                root.right = node
            else:
                BST_Insert(root.right, node)


def preorder_print(root):
    print root
    if root.left is not None:
        preorder_print(root.left)
    else:
        if root.right is not None:
            preorder_print(root.right)


r = Node(4)
# left
a = Node(2)
b = Node(1)
c = Node(3)
# right
d = Node(8)
e = Node(6)
f = Node(10)

BST_Insert(r, a)
BST_Insert(r, b)
BST_Insert(r, c)
BST_Insert(r, d)
BST_Insert(r, e)
BST_Insert(r, f)

print "pre order:"
preorder_print(r)

* 编辑 *

谢谢大家，尤其是abarnert的帮助！！！这里是固定版本！或 preorder_print 和 BST_Inert

def BST_Insert(root, node):     # root --> root of tree or subtree!
    if root.value is None:
        root = node             # beginning of tree
    else:
        if root.value > node.value:     # go to left
            if root.left is None:
                root.left = node
            else:
                BST_Insert(root.left, node)

        if root.value < node.value:    # go to right
            if root.right is None:
                root.right = node
            else:
                BST_Insert(root.right, node)


def preorder_print(root):
    print root.value
    if root.left is not None:
        preorder_print(root.left)
    if root.right is not None:
        preorder_print(root.right)

Answer 1

很抱歉发布两个答案，但我不确定您在这里问的是两个问题中的哪一个。

您的前序遍历没有覆盖整个树，因为只要左子树不为空，您就会忽略整个右子树：

def preorder_print(root):
    print root
    if root.left is not None:
        preoder_print(root.left)
    else:
        if root.right is not None:
            preorder_print(root.right)

因此，在您的示例中，因为4节点的左侧有2节点，所以它不会看到8它下面的任何东西。然后在2. 所以，你只得到 3 个节点而不是全部 7 个。

要解决此问题，只需删除else：

def preorder_print(root):
    print root
    if root.left is not None:
        preoder_print(root.left)
    if root.right is not None:
        preorder_print(root.right)

---

您的BST_Insert功能也有问题。你可以设置root.right = node任何时间node.value > root.value，即使那里已经有东西了。所以，当你第一次尝试在任何东西的右边插入一些东西时，它会擦除​​父级——6擦除8，然后10擦除6，所以你最终只有 4、2、1、3 , 和 10。

我认为您在这里想要改变的是：

    else:
        if root.value < node.value:    # go to right      
            root.right = node
        else:
            BST_Insert(root.right, node)

… 至：

    elif root.value < node.value:    # go to right     
        if root.right is None
            root.right = node
        else:
            BST_Insert(root.right, node)

Answer 2

打印功能工作得很好。当您打印出一个没有自定义__repr__或__str__方法的对象时，这正是您应该得到的。

有两种方法可以解决这个问题。

---

首先，Node打印您要打印的信息，而不是打印对象本身。例如，改变这个：

print root

… 至：

print 'node with value {}'.format(root.value)

… 或者：

print root.value

… 或者：

print 'I've got a node and he's got a value and it's ' + str(root.value)

---

或者，如果你总是希望节点以相同的方式打印出来——例如Node(4)——你可以给类一个__repr__方法：

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

---

有时，您既想提供一种可以放入报告中的类的人类可读的良好表示，又想提供一种对例如在交互式解释器中进行实验有用的不同表示。在这种情况下，您同时定义__str__和__repr__：

def __str__(self):
    # Pick whatever you think looks nice here
    return str(self.value)
    # return 'Node: ' + str(self.value)
    # return 'Node with value {}'.format(self.value)

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

（请注意，这Node(4)是一个很好的“在交互式解释器中进行实验”表示，因为它正是您在解释器中键入以创建等效对象的内容。）

Answer 3

使用print root.value而不是print root.

解释： root是一个对象，Node类的一个实例。root.value是节点持有的实际数字。

另外：做到这一点的“正确”方法是@abarnert 通过 回答__repr__的，但对于专注于树木教学的简单练习来说，这有点过头了。

Answer 4

你想打印 root 的值

print root.value