一、二叉搜索树定义
二叉搜索树(Binary Search Tree)，又名二叉排序树(Binary Sort Tree)。
二叉搜索树是具有有以下性质的二叉树：
- 若左子树不为空，则左子树上所有节点的值均小于或等于它的根节点的值。
- 若右子树不为空，则右子树上所有节点的值均大于或等于它的根节点的值。
- 左、右子树也分别为二叉搜索树。
二、二叉搜索树的操作
2.1、结点创建
class Node(object):
"""节点类"""
def __init__(self, elem=-1, lchild=None, rchild=None,parent=None):
self.elem = elem
self.lchild = lchild
self.rchild = rchild
self.parent = parent
2.2、树的创建
class BTree(object):
def __init__(self):
self.root = None
def insert(self,node,val):
'''为树添加结点: 递归'''
if self.root is None:
self.root = Node(val)
return
if node is None:
node = Node(val)
return node
if val < node.elem:
node.lchild = self.insert(node.lchild,val)
node.lchild.parent = node
elif val > node.elem:
node.rchild = self.insert(node.rchild,val)
node.rchild.parent = node
return node
def insert_no_rec(self,val):
'''为树添加结点: 非递归'''
p = self.root
if not p: #空树
self.root = Node(val)
return
while True:
if val < p.elem:
if p.lchild:
p = p.lchild
else: #左孩子不存在
p.lchild = Node(val)
p.lchild.parent = p
return
elif val > p.elem:
if p.rchild:
p = p.rchild
else: #右孩子不存在
p.rchild = Node(val)
p.rchild.parent = p
return
else:
return
2.3、遍历
（即二叉树遍历，代码参考我博客：数据结构与算法笔记（十四）—— 二叉树）
2.4、查找
def search(self,val):
p = self.root
while p:
if p.elem <val:
p = p.rchild
elif p.elem > val:
p = p.rchild
else:
return True
return False
测试：
print(tree.search(20)) #结果：False
print(tree.search(13)) #结果：True
2.5、删除
二叉查找树的删除操作分为三种情况：
① 要删除的节点是叶子节点：直接删除
代码：
def delNode_1(self,node):
'''情况1：node是叶子结点（即无左子树又无右子树）'''
if not node.parent: #没有父节点说明是根节点
self.root = None
elif node == node.parent.lchild: #node是它父亲的左孩子
node.parent.lchild = None
else: #node是它父亲的右孩子
node.parent.rchild = None
② 要删除的节点只有一个孩子：将此节点的父亲与孩子连接，然后删除该节点
代码：
def delNode_21(self,node):
'''情况2：node只有一个左孩子（只有左子树）'''
if not node.parent: #没有父节点说明是根节点
self.root = node.lchild
elif node == node.parent.lchild: #node是它父亲的左孩子
node.parent.lchild = node.lchild
node.lchild.parent = node.parent
else: #node是它父亲的右孩子
node.parent.rchild = node.lchild
node.lchild.parent = node.parent
def delNode_22(self,node):
'''情况2：node只有一个右孩子（只有右子树）'''
if not node.parent: #没有父节点说明是根节点
self.root = node.rchild
elif node == node.parent.lchild: #node是它父亲的左孩子
node.parent.lchild = node.rchild
node.rchild.parent = node.parent
else: #node是它父亲的右孩子
node.parent.rchild = node.rchild
node.rchild.parent = node.parent
③ 要删节点既有左子树也有右子树：找到该节点右子树中最小值节点，使用该节点代替待删除节点，然后在右子树中删除最小值节点。
代码：
def defNode_3(self,node):
'''情况3：既有左孩子又有右孩子'''
min_node = node.rchild
while min_node.lchild:
min_node = min_node.lchild
node.data = min_node.elem
# 删除min_node
if min_node.rchild:
self.delNode_22(min_node)
else:
self.delNode_1(min_node)
删除结点完整代码：
def delNode(self,val):
'''删除二叉搜索树中值为val的点'''
if not self.root:
return False
_,node = self.search(val)
if not node:
return False
if not node.lchild and not node.rchild: #1.叶子结点
self.delNode_1(node)
elif not node.rchild: #2.1 只有一个左孩子
self.delNode_21(node)
elif not node.lchild: #2.3 只有一个右孩子
self.delNode_22(node)
else: #3.两个孩子都有
self.defNode_3(node)
测试：
tree.preorder(tree.root) #结果：13 14 94 33 25 82 59 65
tree.delNode(13)
tree.preorder(tree.root) #结果：14 94 33 25 82 59 65
完整代码
class Node(object):
"""节点类"""
def __init__(self, elem=-1, lchild=None, rchild=None,parent=None):
self.elem = elem
self.lchild = lchild
self.rchild = rchild
self.parent = parent
class BTree(object):
def __init__(self):
self.root = None
def insert(self,node,val):
'''为树添加结点: 递归'''
if self.root is None:
self.root = Node(val)
return
if node is None:
node = Node(val)
return node
if val < node.elem:
node.lchild = self.insert(node.lchild,val)
node.lchild.parent = node
elif val > node.elem:
node.rchild = self.insert(node.rchild,val)
node.rchild.parent = node
return node
def insert_no_rec(self,val):
'''为树添加结点: 非递归'''
p = self.root
if not p: #空树
self.root = Node(val)
return
while True:
if val < p.elem:
if p.lchild:
p = p.lchild
else: #左孩子不存在
p.lchild = Node(val)
p.lchild.parent = p
return
elif val > p.elem:
if p.rchild:
p = p.rchild
else: #右孩子不存在
p.rchild = Node(val)
p.rchild.parent = p
return
else:
return
def search(self,val):
p = self.root
while p:
if p.elem <val:
p = p.rchild
elif p.elem > val:
p = p.rchild
else:
return True,p
return False
def preorder(self,node):
'''先序遍历'''
if node is None:
return
print(node.elem, end=' ')
self.preorder(node.lchild)
self.preorder(node.rchild)
def delNode_1(self,node):
'''情况1：node是叶子结点（即无左子树又无右子树）'''
if not node.parent: #没有父节点说明是根节点
self.root = None
elif node == node.parent.lchild: #node是它父亲的左孩子
node.parent.lchild = None
else: #node是它父亲的右孩子
node.parent.rchild = None
def delNode_21(self,node):
'''情况2：node只有一个左孩子（只有左子树）'''
if not node.parent: #没有父节点说明是根节点
self.root = node.lchild
elif node == node.parent.lchild: #node是它父亲的左孩子
node.parent.lchild = node.lchild
node.lchild.parent = node.parent
else: #node是它父亲的右孩子
node.parent.rchild = node.lchild
node.lchild.parent = node.parent
def delNode_22(self,node):
'''情况2：node只有一个右孩子（只有右子树）'''
if not node.parent: #没有父节点说明是根节点
self.root = node.rchild
elif node == node.parent.lchild: #node是它父亲的左孩子
node.parent.lchild = node.rchild
node.rchild.parent = node.parent
else: #node是它父亲的右孩子
node.parent.rchild = node.rchild
node.rchild.parent = node.parent
def defNode_3(self,node):
'''情况3：既有左孩子又有右孩子'''
min_node = node.rchild
while min_node.lchild:
min_node = min_node.elem
node.data = min_node.elem
# 删除min_node
if min_node.rchild:
self.delNode_22(min_node)
else:
self.delNode_1(min_node)
def delNode(self,val):
'''删除二叉搜索树中值为val的点'''
if not self.root:
return False
_,node = self.search(val)
if not node:
return False
if not node.lchild and not node.rchild: #1.叶子结点
self.delNode_1(node)
elif not node.rchild: #2.1 只有一个左孩子
self.delNode_21(node)
elif not node.lchild: #2.3 只有一个右孩子
self.delNode_22(node)
else: #3.两个孩子都有
self.defNode_3(node)
if __name__ == '__main__':
li = [13,14,94,33,82,25,59,94,65]
tree = BTree()
#=========添加结点=============
for i in li:
tree.insert(tree.root,i)
tree.preorder(tree.root)
print('')
#=========查找元素=============
# print(tree.search(14))
#=========删除结点=============
tree.delNode(13)
print('')
tree.preorder(tree.root)