数据结构之二叉排序树（Python实现建立、查找、删除）

什么是二叉排序树？

        二叉排序树（BST）又称二叉搜索树，是这样一棵二叉树，若左子树不空，则左子树上所有结点均小于根结点，若右子树不空，则右子树上所有结点均大于根结点其左、右子树也是二叉排序树。（或为空树）（关于什么是二叉树，可以看我的另一篇博客：树和二叉树）

BST的插入（建立）

下面写的很清楚了：

classBTNode:def__init__(self, data, left, right):
        self.data= data
        self.left= left
        self.right= rightclassBST:def__init__(self, root):
        self.root= root# 插入definsertNode(self, data, btnode):# 结点不存在ifnot btnode:
            btnode= BTNode(data,None,None)else:# 值大于当前结点值if data> btnode.data:# 如果结点右子树存在，递归遍历右子树if btnode.right:
                    self.insertNode(data, btnode.right)return# 如果结点右子树不存在，data成为右子树结点else:
                    btnode.right= BTNode(data,None,None)else:# 如果结点左子树存在，递归遍历左子树if btnode.left:
                    self.insertNode(data, btnode.left)return# 如果结点左子树不存在，data成为左子树结点else:
                    btnode.left= BTNode(data,None,None)

BST的查找

思路：

1. 若二叉树为空，则找不到；
2. 先与根比较，相等则找到，否则若小于根则在左子树上继续查找，否则在右子树上继续查找。

classBTNode:def__init__(self, data, left, right):
        self.data= data
        self.left= left
        self.right= rightclassBST:def__init__(self, root):
        self.root= root# 查找defBSTfind(self, data, root):# 没找到ifnot root:returnFalse# 找到if root.data== data:returnTrue# 递归左子树elif root.data> data:
            self.BSTfind(data, root.left)# 递归右子树else:
            self.BSTfind(data, root.right)

BST的删除

BST的结点删除主要有三种情况：

1. 删除叶结点：
   直接删除即可
   

2. 要删除的结点左子树或右子树为空：
   将左子树或右子树接到父结点上
   

3. 要删除的结点左子树和右子树不为空：
   借左子树上最大的结点替换被删除的结点，然后删除左子树最大结点。
   

classBTNode:def__init__(self, data, left, right):
        self.data= data
        self.left= left
        self.right= rightclassBST:def__init__(self, root):
        self.root= root# 删除defdelete(self, data, root):ifnot root:return
        curNode= root# 记录要删结点的父结点
        fuNode=Nonewhile curNodeand curNode.data!= data:
            fuNode= curNodeif curNode.data> data:
                curNode= curNode.leftelse:
                curNode= curNode.right# 如果要删结点无左右子树ifnot(curNode.rightand curNode.left):if fuNode.left== curNode:
                fuNode.left=Noneelse:
                fuNode.right=None# 如果要删结点有左右子树elif curNode.leftand curNode.right:# 纪录要删结点左子树最大值结点
            maxNode= curNode.leftwhile maxNode.right:
                maxNode= maxNode.right# 最大值结点替换要删结点
            curNode.data= maxNode.data# 删除最大值结点
            self.delete(maxNode, root)else:# 如果要删结点为左孩子if fuNode.left== curNode:if curNode.left:
                    fuNode.left= curNode.leftelse:
                    fuNode.left= curNode.right# 如果要删结点为右孩子else:if curNode.left:
                    fuNode.right= curNode.leftelse:
                    fuNode.right= curNode.right