问题遇到的现象和发生背景
调试的时候所有语句都执行了,但是插入完成之后发现只有第一个节点在树中
问题相关代码,请勿粘贴截图
class Node:
def __init__(self,key):
self.key = key
self.lc = None
self.rc = None
self.height = 0
class AVLTree:
'''avl操作'''
def __init__(self):
self.node = None
def GetHeight(self,node):
if node:
return node.height
else:
return -1
def LeftRotation(self,A):
B = A.lc
A.lc = B.rc
B.rc = A
B.height = max(self.GetHeight(B.lc),self.GetHeight(A)) + 1
A.height = max(self.GetHeight(A.rc),self.GetHeight(A.lc)) + 1
def RightRotation(self,A):
B = A.rc
A.rc = B.lc
B.lc = A
B.height = max(self.GetHeight(B.rc),self.GetHeight(A)) + 1
A.height = max(self.GetHeight(A.rc),self.GetHeight(A.lc)) + 1
return A
def LaRRotation(self,A):
A.lc = self.RightRotation(A.lc)
return self.LeftRotation(A)
def RaLRotation(self,A):
A.rc = self.LeftRotation(A.rc)
return self.RightRotation(A)
'''树操作'''
def put(self,key):
if self.node == None:
self.node = Node(key)
else:
self.node = self._put(key,self.node)
def _put(self,key,anode):
if anode == None:
anode = Node(key)
elif key < anode.key:
anode.lc = self._put(key,anode.lc)
if (self.GetHeight(anode.lc) - self.GetHeight(anode.rc)) == 2:
if key < anode.lc.key:
node = self.LeftRotation(anode)
else:
node = self.RaLRotation(anode)
elif key > anode.key:
anode.rc = self._put(key,anode.rc)
if (self.GetHeight(anode.rc) - self.GetHeight(anode.lc)) == 2:
if key > anode.rc.key:
anode = self.RightRotation(anode)
else:
anode = self.LaRRotation(anode)
else:
pass
anode.height = max(self.GetHeight(anode.lc),self.GetHeight(anode.rc)) + 1
return anode
def PreOrder(self,node):
if (node == None):
return
else:
self.PreOrder(node.lc)
print(node.key,end=' ')
self.PreOrder(node.rc)
def max(a,b):
return a if a > b else b
if __name__ == '__main__':
tree = AVLTree()
tree.put(1)
tree.put(2)
tree.put(3)
tree.put(4)
tree.put(5)
tree.PreOrder(tree.node)