蟒蛇二叉搜索樹

Question

出於某種原因，我似乎無法得到「查找」方法的工作。我認爲它與一個範圍問題有關...... root.val似乎並沒有全局更新。我得到一個錯誤消息說AtributeError：「詮釋」對象有沒有屬性「VAL」 這裏是我的代碼的時刻：

class BinaryNode: 
    def __init__(self, v): 
     self.val = v 
     self.leftChild = None 
     self.rightChild = None 
    def get(self): 
     return self.val 
    def set(self, v): 
     self.val = v 
    def getChildren(self): 
     children = [] 
     if self.leftChild != None: 
      children.append(self.leftChild) 
     if self.rightChild != None: 
      children.append(self.rightChild) 
     return children 

class Tree: 
    def __init__(self): 
     self.root = None 
    def setRoot(self, node): 
     self.root = node 
    def size(self): 
     if self.root == None: 
      return 0 
    def subtreeSize(node): 
     return 1 + sum(subtreeSize(c) for c in node.getChildren()) 
     return subtreeSize(self.root) 

class BinarySearchTree(Tree): 
    def insert(self, val): 
     self.insertNode(self.root, val) 

    def insertNode(self, node, val): 
     if node is None: 
      self.setRoot(BinaryNode(val)) 
     elif val <= node.val: 
      node.leftChild = insertNode(BinaryNode(val), val) 
     elif val > node.val: 
      node.rightChild = insertNode(BinaryNode(val), val) 
     else: 
      node.val = val 


    def find(self, val): 
     self.findNode(self.root, val) 

    def findNode(self, node, val): 
     if node is None: 
      return False 
     elif val == node.val: 
      return True 
     elif val < node.val: 
      self.findNode(val, node.leftChild) 
     else: 
      self.findNode(val, node.rightChild) 


if __name__ == "__main__": 
    btree = BinarySearchTree() 
    vals = [5] 
    for v in vals: 
     btree.insert(v) 
    tests = [8, 5] 
    for t in tests: 
     print "find(%i) = %s" % (t, ("True" if btree.find(t) else "False")) 

Answer 1

一個與findNode()問題是，你缺少return語句。該

elif val < node.val: 
     self.findNode(val, node.leftChild) 
    else: 
     self.findNode(val, node.rightChild) 

應該讀

elif val < node.val: 
     return self.findNode(val, node.leftChild) 
    else: 
     return self.findNode(val, node.rightChild) 

您在insertNode()有類似的問題。

Answer 2

有兩個問題與findNode()方法：

1. 您交換的node和val參數時，你遞歸調用它。這會導致您的代碼嘗試在整數值而不是節點上查找.val。

2. 你忘了返回遞歸調用結果。

修正方法：

def find(self, val): 
    return self.findNode(self.root, val) 

def findNode(self, node, val): 
    if node is None: 
     return False 
    elif val == node.val: 
     return True 
    elif val < node.val: 
     return self.findNode(node.leftChild, val) 
    else: 
     return self.findNode(node.rightChild, val) 

你的下一個問題是你insertNode方法;您嘗試調用全局函數insertNode();那應該是self.insertNode()。然而，該方法有沒有返回值，所以你最終設置爲node.leftChild或node.rightChild到None。

你想只交出了插入點遞歸調用搜索，沒有必要使用一個返回值：

def insert(self, val): 
    if self.root is None: 
     self.setRoot(BinaryNode(val)) 
    else: 
     self.insertNode(self.root, val) 

def insertNode(self, node, val): 
    if val <= node.val: 
     if node.leftChild: 
      self.insertNode(node.leftChild, val) 
     else: 
      node.leftChild = BinaryNode(val) 
    elif val > node.val: 
     if node.rightChild: 
      self.insertNode(node.rightChild, val) 
     else: 
      node.rightChild = BinaryNode(val) 

有了這些變化，你的簡單測試打印：

find(8) = False 
find(5) = True