如何用python建立一個無指針的二叉查找樹？

Question

我已經看到「如何構建二叉樹」這個問題的一些答案，但相關的答案似乎不起作用！它們基於或多或少的算法：

def insert(item, tree): 
    if (item < tree.entry): 
     if (tree.left != None): 
      insert(item, tree.left) 
     else: 
      tree.left = Tree(item) 
    else: 
     if (tree.right != None): 
      insert(item, tree.right) 
     else: 
      tree.right = Tree(item) 

前面提到的代碼是由Isaac1000編寫的，但其他代碼非常相似。問題是，當tree.right或tree.left傳遞給函數「插入」在以下呼叫：

insert(item, tree.left) 
insert(item, tree.right) 

誰寫的代碼的人認爲通過參考，而不是副本了值，所以，tree.left或tree.right不會真的改變。最後，該函數或類似函數僅在樹的第一級或零級別工作，而不在樹的第n級。 那麼，如何構建一個沒有指針的二叉搜索樹呢？

P.S. 我說：「沒有指針」只是因爲我知道，Python有沒有拿到三分，但請告訴我，如果我錯了

@qfiard

「如果你通過一個可變的對象變成一種方法，該方法獲得對同一對象的引用，並且可以將它改變爲您的心中的喜悅，但是如果您重新綁定方法中的引用，則外部作用域將不會知道它，並且在完成後，外部引用仍然會指向原始對象。「（Blay Conrad）

這個演講使我清楚。我知道我的代碼沒有聲明，因爲我習慣重新綁定tree.left。下面的代碼是我一直在使用至今已代碼：

def insert(self, data): 
     if self is None: 
      self = Tree(data) 
     else: 
      if data < self.data: 
       Link.insert(self.left, data) 
      else: 
       Link.insert(self.right, data) 

最後，當我寫self = Tree(data)我試圖重新綁定的對象和外部範圍並沒有對它一無所知。相反，使用我發佈的過程，當我使用self.right或self.left時，我嘗試修改對象而不重新綁定，以便外部範圍記住我的更改。

Answer 1

Python中的參數是通過賦值傳遞的，這與通過引用爲可變類型（列表，對象，...）傳遞參數類似。關於這個問題的更多細節，請看這個計算器答案：https://stackoverflow.com/a/986145/2887956。

如果您使用對象來表示您的樹，則您提供的代碼可以很好地工作。以下代碼輸出

<<None, 0, None>, 1, <None, 2, None>>

class Tree(object): 

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

    def __str__(self): 
     return '<%s, %d, %s>' % (self.left, self.entry, self.right) 

def insert(item, tree): 
    if item < tree.entry: 
     if tree.left is not None: 
      insert(item, tree.left) 
     else: 
      tree.left = Tree(item) 
    else: 
     if tree.right is not None: 
      insert(item, tree.right) 
     else: 
      tree.right = Tree(item) 

root = Tree(1) 
insert(0, root) 
insert(2, root) 
print root 

你的算法也將工作，如果你使用的列表來表示你的樹，雖然你將需要大幅度修改。