我嘗試了各種方法來計算二進制搜索樹的高度,該樹包括遞歸併且還使用列表來添加節點以及它的但對於這兩種方法,輸出都是不正確的。計算二進制搜索樹的高度的函數無法正常工作
這裏是我的同一代碼:
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
當我將左指針傳遞給高度函數時,高度函數將正常工作。 –
@DhruvMarwha從你的問題很難看出哪些方法屬於你的類定義,但看到以下Q/A:http://stackoverflow.com/questions/6349554/recursion-within-a-class – grek40
我讀了Q/A但問題沒有解決。 –