目录
二叉搜索树功能实现的过程
1.插入元素
2.查询功能
3.删除功能
4.中序遍历
5.层次遍历
6.二叉搜索树的功能完整代码
题目
19. 动态查找表 【问题描述】 利用二叉排序树完成动态查找表的建立、指定关键字的查找、插入与删除指定关键字结点。 【基本要求】 (1)显示二叉排序树的中序遍历结果 (2)查找成功与否的信息 (3)插入结点后的中序遍历结果(排序结果) (4)删除结点后的中序遍历结果(排序结果) (5)算法要点：二叉排序树建立方法；动态查找、插入、删除的方法；二叉树的中序遍历。 【测试数据】
二叉搜索树功能实现的过程
1.插入元素
先判断要插入节点的树是否空树：
是空树：直接将插入的元素作为根节点不是空树：那么将要插入的元素k和根节点比较：
要插入的元素比根节点的元素大：那么要插入的元素k将插入的位置应该是根节点p的右孩子那边的子树，所以将当前节点的位置p指向当前节点的右孩子（即p=p.rchild)，那么在将当前节点p指向p.rchild右孩子前应该先判断当前节点p是否有右孩子：
如果p没有右孩子：那么直接将要插入的元素变成节点Node后直接插进去即可，简单来说就是将要插入的元素变成节点后赋值给当前节点P的右孩子,然后右孩子的父亲等于p（即p.rchild=Node(k)，p.rchild.parent=p）如果p有右孩子，将p的右孩子赋值给p，成为当前的节点即（p=p.rchild) ,然后再将要插入的元素k和当前节点p比较大小，如果比p大，k就是在右孩子的子树上等等（重复上面的过程）
要插入的元素比根节点的元素小：那么要插入的元素k将插入的位置应该是根节点p的左孩子那边的子树，所以将当前节点的位置p指向当前节点的左孩子（即p=p.lchild)，那么在将当前节点p指向p.lchild左孩子前应该先判断当前节点p是否有左孩子：
如果p没有左孩子：那么直接将要插入的元素变成节点Node后直接插进去即可，简单来说就是将要插入的元素变成节点后赋值给当前节点P的左孩子,然后左孩子的父亲等于p（即p.lchild=Node(k)，p.l child.parent=p）如果p有左孩子，将p的左孩子赋值给p，成为当前的节点即（p=p.rchild) ,然后再将要插入的元素k和当前节点p比较大小，如果比p小，k就是在左孩子的子树上，如果插入的值比p大就是在p右子树的那边等等（一直重复上面的过程）
当找到个位置插入k值后，就退出循环，因为循环的次数是多少谁也不知道，这要根据树的系欸但个数决定的，所以用true,直到将值插进去了就退出循环，否则一直查找，或者是当找到一个节点值等于要插入的元素值时，就退出循环，告知树内存在该元素了，插入失败！
def insert(self,val): #插入节点
p=self.root#从根开始搜索
if p==None:
self.root=Node(val)
return
while True:
if valp.data:
if p.rchild ==None:
p.rchild=Node(val)
p.rchild.parent=p
break
else:
p=p.rchild
else:
print("你要插入的元素已经存在，插入失败！")
break
2.查询功能
- 先判断要插入节点的树是否空树：
- 是空树：直接将插入的元素作为根节点不是空树：那么将要插入的元素k和根节点比较：
- 要插入的元素比根节点的元素大：那么要插入的元素k将插入的位置应该是根节点p的右孩子那边的子树，所以将当前节点的位置p指向当前节点的右孩子（即p=p.rchild)，那么在将当前节点p指向p.rchild右孩子前应该先判断当前节点p是否有右孩子：
- 如果p没有右孩子：那么直接将要插入的元素变成节点Node后直接插进去即可，简单来说就是将要插入的元素变成节点后赋值给当前节点P的右孩子,然后右孩子的父亲等于p（即p.rchild=Node(k)，p.rchild.parent=p）如果p有右孩子，将p的右孩子赋值给p，成为当前的节点即（p=p.rchild) ,然后再将要插入的元素k和当前节点p比较大小，如果比p大，k就是在右孩子的子树上等等（重复上面的过程）
- 如果p没有左孩子：那么直接将要插入的元素变成节点Node后直接插进去即可，简单来说就是将要插入的元素变成节点后赋值给当前节点P的左孩子,然后左孩子的父亲等于p（即p.lchild=Node(k)，p.l child.parent=p）如果p有左孩子，将p的左孩子赋值给p，成为当前的节点即（p=p.rchild) ,然后再将要插入的元素k和当前节点p比较大小，如果比p小，k就是在左孩子的子树上，如果插入的值比p大就是在p右子树的那边等等（一直重复上面的过程）
def insert(self,val): #插入节点
p=self.root#从根开始搜索
if p==None:
self.root=Node(val)
return
while True:
if valp.data:
if p.rchild ==None:
p.rchild=Node(val)
p.rchild.parent=p
break
else:
p=p.rchild
else:
print("你要插入的元素已经存在，插入失败！")
break
2.查询功能
查询都是从树根开始查询的
- 先要判断树根是否为空，在进行下面的查询操作，因为如果树根root是None，那么说明这是一棵空树，没有元素节点，所以不需要查询，直接返回None。如果不是空树：那么就将root赋值给p，让当前节点p从树根开始遍历查找。
- 只要当前的节点不是空节点，那么就和要查找的元素element比较，如果要查找的元素element比当前节点的值p.data大，那就将p.rchild赋值给p，在将p的右孩子赋值给p前，要先判断p是否有右孩子，如果没有，说明查找失败！因为右边的节点的值都比p节点的值大，如果没有右孩子，说明没有比p再大的值了，说明查找失败，树内不存在该元素。如果有有孩子，那么将右孩子p.rchild赋值给p，成为当前节点p，然后重复上面的操作，判断当前节点p和要查找元素的值的大小，如果相等，说明找到，如果比当前节点p的值小，说明是当前节点p的左孩子，那么就要判断是否有左孩子，如果没有那么查找失败，然后一直重复上面操作，直到当前节点为空，或者找到元素了就放回当前的节点p等等。如果要查找的元素比根节点小，说明是根的左子树那边，接下来查找左子树的过程和查找右子树的过程一致。
def search(self,element,root):
if not root:#判断根是否为空
print("查找失败！原因4：树为空树！")
return None
else:
p=root
while p:#当前节点不为空
if element > p.data:#element比当前节点大
if p.rchild:#要先判断p是否有右孩子
p=p.rchild
if p.data==element:
print("查找成功1！",end=",")
print(element,end=" ")
print("的父节点是：",end=" ")
print(p.parent.data)
return p
break
else:
print("查找失败！原因1：树内不存该元素")
return None
elif element < p.data:#element比当前节点小
if p.lchild:#要先判断p是否有左孩子
p=p.lchild
if element == p.data:
print("查找成功2！",end=",")
print(element,end=" ")
print("的父节点是：",end=" ")
print(p.parent.data)
return p
break
else:
print("查找失败！原因2：树内不存该元素")
return None
else:#element等于根节点
if element ==p.data:
print("查找成功3！",end=",")
print(element,end=" ")
print("是根节点，其父节点为:None")
return p
break
else:
print("查找失败！原因3：树内不存在要查找的元素")
return None
3.删除功能
删除节点前先要查找树内是否存在要删除的节点，如果查找失败就不需要删除，查找成功则会放回要删除节点的位置给P，然后进行下一步的删除操作。
删除节点的情况分为三大类：
- 要删除的节点是叶子节点，就是没有孩子的节点的情况：
- 要删除的节点是根节点（就是仅有一个根，没有孩子）：那么直接将根删除就好，删除节点的操作就是将节点变成None(这里就是将self.root=None)要删除的节点不是根节点，那么就要分以下几种情况：
- 要删除的节点没有孩子节点：那么就直接将节点删除，这个删除又分以下两种情况：
- 要删除的节点是其父节点的左孩子：那么删除的操作就是将要删除节点的父节点的左孩子变成None,要删除节点的父亲变成None,(即p.parent.lchild=None ; p.parent=None)要删除的节点是其父孩子的右孩子：删除操作同左孩子一致
- 要删除的节点是根节点，分以下情况：
- 要删除的节点仅有左孩子：那么直接让它的左孩子成为根即可， (即self.root=p.lchild ； p.lchild.parent=None)要删除的节点仅有右孩子：那么直接让它的右孩子成为根即可， (即self.root=p.rchild ； p.rchild.parent=None)
- 要删除的节点的右孩子有左孩子，（此时的左孩子一定没有左孩子了），因为当要删除的节点有2个孩子时，那么就将要删除节点的右子树的最小左孩子赋值给要删除的节点，然后再从右子树中删除最小左孩子，这个赋值过程就是（p.data=min_child.data),然后根据以下情况判断怎么删除最小左孩子，对于这里怎么找最小左孩子是首先将p.rchild赋值给p成为当前节点，然后判断要删除的节点的右孩子有没有左孩子，如果没有左孩子，那么就说明当前的右孩子p.rchild是左子树中最小的，那么将p.rchild直接替代p,然后删除该右孩子节点（即p.data=p.rchild.data ，p.rchild.parent.rchild=None, p.rchild.parent=None),这里使用了循环while min_child.lchild来找最小左孩子，如果min_child.lchild不等于空，说明还有更小的左孩子，那么将min_child的左孩子赋值给min_child,如果为空，说明已经是最小左孩子了，没有更小的左孩子了，那么这时候就判断左孩子min_child有没有右孩子，那么就有以下两种情况：
- 要删除节点的右孩子的左孩子有右孩子：那么将左孩子赋值给要删除节点的位置后，再删除左孩子，在删除左孩子时，要将左孩子的右孩子的父亲变成左孩子min_child的父亲，min_child的父亲的左孩子变成min_child的右孩子（即
p.data=min_child.data ， min_child.rchild.parent=min_child.parent ， min_child.parent.lchild=min_child.rchild ，）要删除节点的右孩子的左孩子没有右孩子：操作与上一致
- 要删除节点的右孩子有右孩子：操作与上一致要删除节点的右孩子没有右孩子：操作与上一致
def remove(self,element):
#删除前先查找是否存在该节点
print("删除节点前的查找结果：",end=" ")
test=self.search(element,self.root)
# print(self.search(element,tree_root ))#这仅仅用于测试是否返回了节点
p=test
# print(p)
if p==None:
print("删除失败！，该树内不存在要删除的元素！")
#要删除的节点没有孩子（p是叶子节点）
elif p.lchild==None and p.rchild==None:#要删除的节点是叶子节点
if not p.parent: #要删除的节点是根节点
self.root=None
self.remove_test(element)
else:
if p==p.parent.lchild:#p是p.parent的左孩子
p.parent.lchild=None
p.parent=None
elif p==p.parent.rchild:#p是p.parent的右孩子
p.parent.rchild=None
p.parent=None
self.remove_test(element)
#要删除元素有2个孩子
elif p.lchild !=None and p.rchild !=None: #要删除元素有2个孩子
# if not p.parent or p.parent :#要删除的节点是根节点
min_child=p.rchild#p的右孩子
while min_child.lchild:#min_child的左孩子不为空，则说明还有左孩子，右子树最小的元素一定是右子树的左子树的最后一个元素
min_child=min_child.lchild #移动位置就是将左孩子付给min，将右孩子的左孩子付给min_child
if p.rchild.lchild :#如果要删除节点的右孩子有左孩子
if min_child.rchild:#要删除节点的右孩子存在最小左孩子，最小左孩子存在右孩子
p.data=min_child.data
min_child.rchild.parent=min_child.parent
min_child.parent.lchild=min_child.rchild
else:#要删除节点的右孩子存在最小左孩子，最小左孩子不存在右孩子
p.data=min_child.data
min_child.parent.lchild=None
min_child.parent=None
self.remove_test(element)
elif not p.rchild.lchild :#要删除的节点的右孩子没有左孩子
if not p.rchild.rchild:#要删除节点的右孩子没有右孩子
p.data=min_child.data
min_child.parent.rchild=None
min_child.parent=None
elif p.rchild.rchild:#有右孩子
p.data=min_child.data
min_child.parent.rchild=min_child.rchild
min_child.rchild.parent=min_child.parent
self.remove_test(element)
#要删除元素有一个孩子
# elif p.lchild !=None or p.rchild !=None:
else:
if not p.parent:#情况1：要删除元素是根节点
if p.lchild !=None and p.rchild ==None: #要删除节点只有左孩子
self.root=p.lchild
p.lchild.parent=None
elif p.lchild ==None and p.rchild !=None: #要删除节点只有右孩子
self.root=p.rchild
p.rchild.parent=None
self.remove_test(element)
elif p.parent.lchild !=None and p==p.parent.lchild: #p是parent的左孩子
if p.lchild !=None and p.rchild ==None: #要删除节点只有左孩子
p.parent.lchild=p.lchild
p.lchild.parent=p.parent
elif p.lchild ==None and p.rchild !=None:# 要删除节点只有右孩子
p.parent.lchild=p.rchild
p.rchild.parent=p.parent
self.remove_test(element)
elif p.parent.rchild !=None and p==p.parent.rchild: #p是parent的右孩子
if p.lchild !=None and p.rchild ==None: #要删除节点只有左孩子
p.parent.rchild=p.lchild
p.lchild.parent=p.parent
elif p.lchild ==None and p.rchild !=None:# 要删除节点只有右孩子
p.parent.rchild=p.rchild
p.rchild.parent=p.parent
self.remove_test(element)
4.中序遍历
中序遍历的顺序是：左根右 ，其中二叉搜索树的中序遍历一定是有序序列
中序遍历输出顺序的操作：
- 先输出左孩子：根不为空，那么将根的左左孩子赋值传递给递归函数，进行递归循环输出，一开始的root是树根，但是到后面就是根的左孩子，或者是它们的左左左孩子等等的，当root的左孩子为空时，退出左孩子的递归循环，那么进行输出当前左孩子为空的根节点，然后一次倒回输出左孩子，这里的左孩子就是左边小左子树的根，最后也就是通过输出根来输出左孩子，因为结束的递归循环的左孩子是空，那么输出的就是他的父亲，相对于那个空的左孩子而言其输出的结果就是根，大树根和右孩子也是同理输出。
def in_order(self,root):#中序遍历
if root:
self.in_order(root.lchild)
print(root.data,end=",")
self.in_order(root.rchild)
5.层次遍历
层次遍历就是由顶层逐渐向下层输出
层次遍历就是使用了队列queue,同时队列也可以说是列表形成的，比列表高级一点儿.
首先要创建一个队列，也就是列表，然后将树根存放进队列中，层次遍历就是根节点进队，访问到的节点如果存在孩子，它的孩子全部进队，访问的元素出队，直到将队列的所有元素访问完（就是队列为空时候就结束），当队列为空时说明了该树的所有节点已经访问完。
每次都是弹出队列中的第一个元素，因为上一个元素弹出后，下一个元素就变成队列中的第一个元素了，所以使用queue.pop(0)代表弹出第一一个元素队列中，层次遍历就是按照queue.pop(0)的弹出顺序输出在孩子进队之前，要先判断孩子是否为空，不为空则进队
层次遍历过程图
层次遍历代码
def level_order(self,element):#层次遍历
node=Node(element)
queue = [self.root]
if self.root ==None:
return
else:
while queue :
cur_node=queue.pop(0)
print(cur_node.data,end=",")
if cur_node.lchild !=None:
queue.append(cur_node.lchild)
if cur_node.rchild !=None:
queue.append(cur_node.rchild)
