二叉搜索樹 - 查找高度和深度

Question

這是我第一次編碼二叉查找樹。 我參考了很多從網上，並嘗試了一些他們的代碼。 想知道 爲什麼這2碼不工作，給了我同樣的錯誤，當我試圖把它打印出來

def height(self,node): 
    if node is None: 
     return 0 
    else: 
     return max(height(node.left), height(node.right)) + 1 

---

def depth(self, count=0): 
    if self.root is None: 
     return count 
    return max(depth(self.root.left, count+1), 
       depth(self.root.right, count+1)) 

都有它說

同樣的錯誤

"global name height is not define" 
"global name depth is not define" 

我不知道爲什麼，因爲我調用同一個功能

ç omplete代碼：

class BST: 
    root=None 

    def put(self, key, val): 
     self.root = self.put2(self.root, key, val) 

    def put2(self, node, key, val): 
     if node is None: 
      #key is not in tree, create node and return node to parent 
      return Node(key, val) 
     if key < node.key: 
      # key is in left subtree 
      node.left = self.put2(node.left, key, val) 
     elif key > node.key: 
      # key is in right subtree 
      node.right = self.put2(node.right, key, val) 
     else: 
      node.val = val 
     # node.count = 1 + self.size2(node.left) + self.size2(node.right) 
     return node 




    # draw the graph 
    def drawTree(self, filename): 
     # create an empty undirected graph 
     G=pgv.AGraph('graph myGraph {}') 

     # create queue for breadth first search 
     q = deque([self.root]) 
     # breadth first search traversal of the tree 
     while len(q) <> 0: 
      node = q.popleft() 
      G.add_node(node, label=node.key+":"+str(node.val)) 
      if node.left is not None: 
       # draw the left node and edge 
       G.add_node(node.left, label=node.left.key+":"+str(node.left.val)) 
       G.add_edge(node, node.left) 
       q.append(node.left) 
      if node.right is not None: 
       # draw the right node and edge 
       G.add_node(node.right, label=node.right.key+":"+str(node.right.val)) 
       G.add_edge(node, node.right) 
       q.append(node.right) 

     # render graph into PNG file 
     G.draw(filename,prog='dot') 
     os.startfile(filename) 

    def createTree(self): 
     self.put("F",6) 
     self.put("D",4) 
     self.put("C",3) 
     self.put("B",2) 
     self.put("A",1) 
     self.put("E",5) 
     self.put("I",9) 
     self.put("G",7) 


    self.put("H",8) 
     self.put("J",10) 


    def height(self,node): 
     if node is None: 
      return 0 
     else: 
      return max(height(node.left), height(node.right)) + 1 


    def depth(self, count=0): 
     if self.root is None: 
      return count 
     return max(depth(self.root.left, count+1), 
        depth(self.root.right, count+1)) 

class Node: 
    left = None 
    right = None 
    key = 0 
    val = 0 



    def __init__(self, key, val): 
     self.key = key 
     self.val = val 




bst = BST() 
bst.createTree() 
bst.drawTree("demo.png") 
print bst.get("B") 
##print bst.size("D") 
##print bst.size("F") 
print bst.depth("B") 

Answer 1

你確定你的BST.height()和BST.depth()方法是真心BST的範圍是什麼？看起來他們沒有縮進BST類。檢查你的間距。

Answer 2

Python不會範圍代碼可自動將本地類：

return max(self.height(node.left), self.height(node.right)) + 1 

和

return max(self.depth(self.root.left, count+1), 
      self.depth(self.root.right, count+1))