计算二进制搜索树的高度的函数无法正常工作

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。