Python 实现二叉搜索树插入、查找、删除结点算法

旧城等待， 2022-05-18 00:10 177阅读 0赞

二叉搜索树(Binary Search Tree)，又称为“二叉排序树”、“二叉查找树”。定义为：该树的每个结点都有一个作为搜索依据的关键码。对任意结点而言，其左子树（如果存在）上的每个结点的关键码均小于该结点的关键码，其右子树（如果存在）上的所有结点的关键码都大于该结点的关键码。

其中，根据二叉搜索树的定义，二叉树结点之间的关系可以通过结点间的位置关系来得到，常用的算法是分割式查找，查找结点的平均长度![ASL = \\frac\{1\}\{n\}\\left ( n\_\{1\}+ n\_\{2\}+\\cdots + n\_\{n\}\\right )][ASL _ _frac_1_n_left _ n_1_ n_2_cdots _ n_n_right]；

插入操作时，新插入的结点总是叶子结点，首先查找插入结点的父亲结点，再判断左右子树；

删除操作时，由于结点位置的不同，使得删除结点操作比较复杂，有多种情况需要考虑，主要包含三种：删除叶子结点、删除只有一个孩子的结点、删除左右孩子都有的结点，其中删除左右孩子都有的结点时，使用合并操作，查找被删除结点p的左子树中最右值最大的结点r，将结点r的右子树指向结点p的右子树的根，然后用结点p的左子树的根代替被删除的结点p，最后删除结点p。

例如：

![70][]

代码如下

import queue
    '''
    二叉树结点
    '''  
    
    class TreeNode:
        def __init__(self,val=None,left=None,right=None):
            self.val = val
            self.left = left
            self.right = right
        def settag(self,tag=None):
            self.tag = tag
    '''
    插入结点
    '''
    def InsertNode(root,treenode):
        tmp = root
        if(root is None):
            root = treenode
        while(tmp is not None):
            if(treenode.val == tmp.val):
                break
            elif(treenode.val < tmp.val):
                if(tmp.left is None):
                    tmp.left = treenode
                else: tmp = tmp.left
            else:
                if(tmp.right is None):
                    tmp.right = treenode
                else: tmp = tmp.right
        return root
    
    '''
    查找结点
    '''
    def search(root,key):
        tmp = root
        while(tmp is not None and key != tmp.val):
            if(key < tmp.val):
                tmp = search(tmp.left, key)
            else:
                tmp = search(tmp.right, key)
        return tmp
    
    '''
    获取结点的父亲结点
    '''
    def getparent(root,treenode):
        tmp = root
        if(root == treenode): return None
        while(tmp is not None):
            if(tmp.right == treenode or tmp.left == treenode):
                return tmp
            elif(treenode.val < tmp.val):
                tmp = tmp.left
            else:
                tmp = tmp.right
        return None
    '''
    合并删除结点
    '''
    def mergedeletenode(root,treenode):
        tmp = treenode
        parentnode = getparent(root, tmp)
        if(parentnode is not None):
            if(treenode.right is None and treenode.left is None):
                if(parentnode.right == treenode): parentnode.right = None
                else: parentnode.left = None
            elif(treenode.right is not None and treenode.left is None):
                if(parentnode.right == treenode): parentnode.right = tmp.right
                else: parentnode.left = tmp.right
            elif(treenode.right is None and treenode.left is not None):
                if(parentnode.right == treenode): parentnode.right = tmp.left
                else: parentnode.left = tmp.left
            else:
                tmp = treenode.left
                while(tmp.right!=None):
                    tmp = tmp.right
                tmp.right = treenode.right
                if(parentnode.right == treenode): parentnode.right = treenode.left
                else: parentnode.left = treenode.left 
        else:#删除根节点
            if(treenode.right is None and treenode.left is None):
                root = None
            elif(treenode.right is not None and treenode.left is None):
                root = tmp.right
            elif(treenode.right is None and treenode.left is not None):
                root = tmp.left       
            else:
                tmp = tmp.left
                while(tmp.right is not None):
                    tmp = tmp.right
                tmp.right = treenode.right
                root = treenode.left
        return root

测试代码

if __name__=='__main__':
        nodes = [5,1,7,4,6,9,8]
        root = None
        for i in range(len(nodes)):
            node = TreeNode(nodes[i])
            root = InsertNode(root, node)
        PreOrderWithoutRecursion(root)
        print()
        InOrderWithoutRecursion(root)
        print()
        tmp = search(root, 5)
        print(tmp.val)
        root = mergedeletenode(root, tmp)
        PreOrderWithoutRecursion(root)
        print()
        InOrderWithoutRecursion(root)

输出结果

5 1 4 7 6 9 8 
    1 4 5 6 7 8 9 
    5
    1 4 7 6 9 8 
    1 4 6 7 8 9

[ASL _ _frac_1_n_left _ n_1_ n_2_cdots _ n_n_right]: https://private.codecogs.com/gif.latex?ASL%20%3D%20%5Cfrac%7B1%7D%7Bn%7D%5Cleft%20%28%20n_%7B1%7D&plus;%20n_%7B2%7D&plus;%5Ccdots%20&plus;%20n_%7Bn%7D%5Cright%20%29
[70]: /images/20220518/7d9127f81dd447e2a4d421950c07c145.png