书上寻找后继节点那块内容没怎么看懂，结合别的教学视频写的。求指正错误!
def __init__(self,key,val,left=None,right=None,parent=None):
self.key=key
self.val=val
self.leftchild=left
self.rightchild=right
self.parent=parent
def hasleftchild(self):
return self.leftchild
def hasrightchild(self):
return self.rightchild
def isleftchild(self):
return self.parent and self.parent.leftchild==self
def isrightchild(self):
return self.parent and self.parent.rightchild==self
def isroot(self):
return not self.parent
def isleaf(self):
return not(self.leftchild or self.rightchild)
def hasanychildren(self):
return self.rightchild or self.leftchild
def hasbothchildren(self):
return self.rightchild and self.leftchild
def replacenodedata(self,key,val,lc,rc):
self.key = key
self.val = val
self.leftchild = lc
self.rightchild = rc
if self.hasleftchild():
self.leftchild.parent=self
if self.hasrightchild():
self.rightchild.parent=self
class binarysearchtree:
def __init__(self,):
self.root=None
self.size=0
def length(self):
return self.size
def __len__(self):
return self.size
def __iter__(self):
return self.root.__iter__()
def put(self,key,val):
if self.root:
self._put(key,val,self.root)
else:
self.root=treenode(key,val)
self.size=self.size+1
def _put(self,key,val,currentnode):
if key<currentnode.key:
if currentnode.hasleftchild():
self._put(key,val,currentnode.leftchild)
else:
currentnode.leftchild=treenode(key,val,parent=currentnode)
else:
if currentnode.hasrightchild():
self._put(key,val,currentnode.rightchild)
else:
currentnode.rightchild=treenode(key,val,parent=currentnode)
def __setitem__(self, key, val):
self.put(key,val)
def get(self,key):
if self.root:
res=self._get(key,self.root)
if res:
return res.val
else:
return None
else:
return
def _get(self,key,currentnode):
if not currentnode:
return None
elif currentnode.key==key:
return currentnode
elif key<currentnode.key:
return self._get(key,currentnode.leftchild)
else:
return self._get(key, currentnode.rightchild)
def __getitem__(self, key):
return self.get(key)
#检查树中是否有某个键
def __contains__(self, key):
if self._get(key,self.root):
return True
else:
return False
#删除操作
#该节点为叶子节点
def _remove_node1(self,key,currentnode):
if currentnode==currentnode.parent.leftchild:
currentnode.parent.leftchild=None
else:
currentnode.parent.leftchild=None
#该节点只有一个子节点
def _remove_node21(self,currentnode): #该节点有左子节点
if currentnode.isleftchild():
currentnode.leftchild.parent=currentnode.parent
currentnode.parent.leftchild=currentnode.leftchild
elif currentnode.isrightchild():
currentnode.leftchild.parent=currentnode.parent
currentnode.parent.rightchild=currentnode.leftchild
else:currentnode.replacenodedata(currentnode.leftchild.key,currentnode.leftchild.val,
currentnode.leftchild.leftchild,currentnode.leftchild.rightchild)
def _remove_node22(self,currentnode): #该节点有右子节点
if currentnode.isleftchild():
currentnode.rightchild.parent = currentnode.parent
currentnode.parent.leftchild = currentnode.rightchild
elif currentnode.isrightchild():
currentnode.rightchild.parent = currentnode.parent
currentnode.parent.rightchild = currentnode.rightchild
else:
currentnode.replacenodedata(currentnode.rightchild.key, currentnode.rightchild.val,
currentnode.rightchild.leftchild, currentnode.rightchild.rightchild)
#该节点有两个子节点
def _remove_node3(self,currentnode):
succ=currentnode._findsuccessor()
succ=currentnode.leftchild.parent
succ.leftchild=currentnode.leftchild
succ = currentnode.rightchild.parent
succ.rightchild = currentnode.rightchild
succ.parent=currentnode.parent
if currentnode.isleftchild():
currentnode.leftchild=succ
else:
currentnode.rightchild=succ
#该节点有两个子节点，需要寻找后继节点
def _findsuccessor(self):
current=self
while current.hasleftchild():
current=current.leftchild
return current
def delete(self,key):
if self.size>1:
nodetoremove=self._get(key,self.root)
if not nodetoremove:
return False
if not nodetoremove.leftchild and not nodetoremove.rightchild:
self._remove_node1(nodetoremove)
elif not nodetoremove.rightchild:
self._remove_node21(nodetoremove)
elif not nodetoremove.leftchild:
self._remove_node22(nodetoremove)
else:
succ0=nodetoremove._findsuccessor()
#先删除后继节点
if succ0.rightchild:
self._remove_node22(succ0)
else:
self._remove_node1(succ0)
#后继节点移至待删除节点处
self._remove_node3(nodetoremove)
elif self.size==1 and self.root.key==key:
self.root=None
self.size=0
else:
return False
def __delitem__(self, key):
self.delete(key)
