Python实现二叉搜索树-查找树-排序树【通俗易懂】

二叉搜索树定义

父亲节点的左孩纸小于父亲节点，右孩纸大于父亲节点

从别人博客拉了一张图

复杂度分析

1、查询时间复杂度为 O(log2 n)~O(n)。
时间复杂度和二分法类似，因为二叉树就是用到了二分的思想

最坏情况会退化成一条链

这时的复杂度为O(n)

代码实现

1、初始化类
用python的列表来实现树形结构 方便点 size为树的元素大小
传入size要可能大，因为用数组来模仿树形结构有很多空的元素，数组模仿出来的是一颗满二叉树
比如0的节点孩纸为1 2
1 --->3 4
2 --->5 6
0 1 2 3 4 5 6 7 8 是按层来遍历树的

所以如果父亲节点的位置为n 则左孩纸为n*2+1

右孩纸就在左孩纸边上n*2+2

    def __init__(self,size):
        self.tree=[None]*size    #没有元素的都为None

    def __len__(self):
        return len(self.tree)

    def __str__(self):
        return str(self.tree)

2、插入元素

    def insert(self,v,root=0):
        if self.tree[root]==None:
            self.tree[root] = v
        elif v>self.tree[root]:  #大于父亲就插入到父亲的右树 反之左
            self.insert(v,root*2+2)  
        else:
            self.insert(v,root*2+1)

3、判断元素是否存在【二分查询】

    def isExist(self,v,root=0):   #目标元素大于父亲 往右边找 小于父亲往左边找
        while self.tree[root]!=None:   
            if self.tree[root]==v:  
                return True
            if self.tree[root]>v:  
                root=root*2+1
            else:
                root = root*2+2
        return False

4、查找最小值【就是查找最左边的元素】
这个操作主要是用于删除元素用
属于内置操作

    def _findMin(self,root=0):  #找最左边的
        if self.tree[root*2+1]==None:
            return root
        return self._findMin(root*2+1)

5、删除操作【最复杂】

分三种情况考虑：

1、待删除的节点无孩纸节点：直接删除即可

2、待删除的节点有两个孩纸节点：需要和当前节点右子树中最小的节点互换位置再删除，因为待删除节点右树最小的节点就是最接近当前节点的点，这样巧合满足二叉树的规则

3、待删除节点仅仅有一个孩纸：
将这个节点与那个孩纸互换再讲删除的节点转移到孩纸节点,进行下沉
【因为万一孩纸节点下面还有树的话就要进行递归删除了】
建议自己画一画试一试

    def delete(self,x,root=0):  #x代表删除的元素值
        if x<self.tree[root]:  #在左边
            self.delete(x,root*2+1)
        elif x>self.tree[root]:
            self.delete(x,root*2+2)

        else:
            if self.tree[root*2+1]!=None and self.tree[root*2+2]!=None: #左右孩子都不为空
                m = self._findMin(root*2+2)  #寻找右边最小的
                self.tree[root],self.tree[m] = self.tree[m],self.tree[root]
                self.delete(x,root*2+2) #递归删除
            elif self.tree[root*2+1]==None and self.tree[root*2+2]==None: 
                self.tree[root] = None #左右孩子都为空 直接删除
            else: #只有一个孩纸
                if self.tree[root*2+1]==None:  #左边为空 和右边节点换位置
                    m = self._findMin(root*2+2)
                    self.tree[root],self.tree[m] = self.tree[m],self.tree[root]
                    self.delete(x,m) #直接删除 这里没有递归
                else:  #右边为空
                    m = self._findMin(root * 2 + 1)
                    self.tree[root], self.tree[m] = self.tree[m], self.tree[root]
                    self.delete(x,m) #直接删除

6、中序遍历【这样巧好是升序排列】

右-->中---->左

这颗树的中序遍历结果为
ACBDFHEMG

    def Order(self,root=0):
        if self.tree[root]==None:
            return
        self.Order(root*2+1)
        print(self.tree[root])
        self.Order(root*2+2)

7、测试样例

tree = searchTree(100)

tree.insert(2)
tree.insert(5)
tree.insert(1)
tree.insert(20)
tree.insert(9)
tree.insert(10)
tree.Order()
print("====")
tree.delete(5)
tree.delete(2)
tree.Order()

1
2
5
9
10
20
====
1
9
10
20

8、完整代码

class searchTree():
    def __init__(self,size):
        self.tree=[None]*size

    def __len__(self):
        return len(self.tree)

    def __str__(self):
        return str(self.tree)


    def _findMin(self,root=0):  #找最左边的
        if self.tree[root*2+1]==None:
            return root
        return self._findMin(root*2+1)

    def insert(self,v,root=0):
        if self.tree[root]==None:
            self.tree[root] = v
        elif v>self.tree[root]:
            self.insert(v,root*2+2)
        else:
            self.insert(v,root*2+1)

    def delete(self,x,root=0):
        if x<self.tree[root]:  #在左边
            self.delete(x,root*2+1)
        elif x>self.tree[root]:
            self.delete(x,root*2+2)

        else:
            if self.tree[root*2+1]!=None and self.tree[root*2+2]!=None: #左右孩子都不为空
                m = self._findMin(root*2+2)  #寻找右边最小的
                self.tree[root],self.tree[m] = self.tree[m],self.tree[root]
                self.delete(x,root*2+2)
            elif self.tree[root*2+1]==None and self.tree[root*2+2]==None:
                self.tree[root] = None
            else:
                if self.tree[root*2+1]==None:  #左边为空 和右边节点换位置
                    # print(self.tree[(root*2+2)*2+1])
                    m = self._findMin(root*2+2)
                    self.tree[root],self.tree[m] = self.tree[m],self.tree[root]
                    self.delete(x,m)
                else:  #右边为空
                    m = self._findMin(root * 2 + 1)
                    self.tree[root], self.tree[m] = self.tree[m], self.tree[root]
                    self.delete(x,m)

    def isExist(self,v,root=0):
        while self.tree[root]!=None:
            if self.tree[root]==v:
                return True
            if self.tree[root]>v:
                root=root*2+1
            else:
                root = root*2+2
        return False

    def Order(self,root=0):
        if self.tree[root]==None:
            return
        self.Order(root*2+1)
        print(self.tree[root])
        self.Order(root*2+2)

tree = searchTree(100)

tree.insert(2)
tree.insert(5)
tree.insert(1)
tree.insert(20)
tree.insert(9)
tree.insert(10)
tree.Order()
print("====")
tree.delete(5)
tree.delete(2)
tree.Order()
# tree.tree