計算二進制搜索樹的高度的函數無法正常工作

Question

我嘗試了各種方法來計算二進制搜索樹的高度，該樹包括遞歸併且還使用列表來添加節點以及它的但對於這兩種方法，輸出都是不正確的。

這裏是我的同一代碼：

class Node: 
def __init__(self,data): 
    self.data=data 
    self.left=None 
    self.right=None 

def Insert_BTreeNode(self,data): 
    if self.data: 
     if data<=self.data: 
      if self.left is None: 
       self.left=Node(data) 
      else: 
       self.left.Insert_BTreeNode(data) 

     elif data>self.data: 
      if self.right is None: 
       self.right=Node(data) 

      else: 
       self.right.Insert_BTreeNode(data) 

    else: 
     self.data=data 

def Lookup(self,data,parent=None): 

    if data<self.data: 
     if self.left is None: 
      return None,None 
     return self.left.Lookup(data,self) 
    elif data>self.data: 
     if self.right is None: 
      return None,None 
     return self.right.Lookup(data,self) 
    else: 
     if (parent is not None): 
      print(self.data,parent.data) 
     return (self,parent) 

def Children_count(self): 
    count=0 

    if self.left: 
     count+=1 
    if self.right: 
     count+=1 

    return (count) 

def Delete(self,data): 
    children_count=0 
    node,parent=self.Lookup(data) 
    if node is not None: 
     children_count=node.Children_count() 

    if children_count==0: 
     if parent: 
      if parent.left is Node: 
       parent.left=None 
      else: 
       parent.right=None 
      del node 
     else: 
      self.data=data 

    elif children_count==1: 
     if node.left: 
      n=node.left 
     else: 
      n=node.right 
     if parent: 
      if parent.left is node: 
       parent.left=n 
      else: 
       parent.right=n 
      del node 
     else: 
      self.left=n.left 
      self.right=n.right 
      self.data=n.data 

    else: 
     parent=node 
     successor=node.right 

     while successor.left: 
      parent=successor 
      successor=successor.left 
     node.data=successor.data 

     if parent.left==successor: 
      parent.left=successor.right 

     else: 
      parent.right=successor.right 

def print_treeInorder(self): 
    if self.left: 
     self.left.print_treeInorder() 
    print(self.data) 
    if self.right: 
     self.right.print_treeInorder() 


def print_treePostorder(self): 
    if self.left: 
     self.left.print_treePostorder() 
    if self.right: 
     self.right.print_treePostorder() 
    print(self.data) 

def height(self): 
    if self is None: 
     return 0 
    else: 
     return max(height(self.getLeft()), height(self.getRight()))+ 1 

def print_treePreorder(self): 
    print(self.data) 

    if self.left: 
     self.left.print_treePreorder() 
    if self.right: 
     self.right.print_treePreorder() 

def getLeft(self): 
    return self.left 

def getRight(self): 
    return self.right 

def maxDepth(self): #Level order Traversal 
    if self is None: 
     return 1 
    q=[] 
    q.append([self,1]) 
    while(len(q))!=0: 
     node,temp=q.pop() 
     if node.getLeft()!=None: 
      q.append([node.getLeft(),temp+1]) 
     if node.getRight()!=None: 
      q.append([node.getRight(),temp+1]) 
    return temp 

b_tree_input=list(map(int,input().split())) 

root=Node(b_tree_input[0]) 

for i in range(1,len(b_tree_input)): 
    root.Insert_BTreeNode(b_tree_input[i]) 

print(root.height()) 
print(root.maxDepth()) 

對於2,1,3,4.Both的樣品輸入函數應該返回答案爲3，但是高度函數返回以下。

NameError: name 'height' is not defined

雖然MAXDEPTH（）函數返回的答案爲2

Answer 1

關於height：我不是一個Python程序員，但應該不會是

max(self.getLeft().height(), self.getRight().height()) 
// instead of 
max(height(self.getLeft()), height(self.getRight())) 

因爲height是一個成員函數？

然而，這意味着你必須調用height前檢查self.getLeft()和self.getRight()爲None值。如果您不想執行額外的檢查，請考慮使height成爲與您的班級無關的全局函數，那麼您以前的遞歸方法應該可行。

支票高度功能None可以看看如下（語法的詳細信息不能保證）：

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

在maxDepth您處理子節點在從右到左的DFS，但你只能走最後處理路徑的結果，而不是將當前temp與已經發現的最大深度進行比較。

因此，在你[2,1,3,4]例如，執行順序如下：

q=[[2,1]] -> take [2,1] -> temp=1 
q=[[1,2],[3,2]] -> take [3,2] -> temp=2 
q=[[1,2],[4,3]] -> take [4,3] -> temp=3 
q=[[1,2]] -> take [1,2] -> temp=2 
end 

我覺得現在你可以弄清楚如何改變你的算法。

此外，您應該考慮更改self is None的情況下返回0。