打印预订中的BST

Question

我试图打印出我的二叉树预订形式但是我遇到这些错误。我仍然在学习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 = nodenode.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是节点持有的实际数量。

另外：“适当的”方法是通过__repr__回答@abarnert的问题，但是对于围绕树木教学进行简单练习的简单练习有点矫枉过正。

Answer 4

要打印根值

print root.value