打印預訂中的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