二叉搜索树的插入和删除

短命女 2023-02-15 15:55 6阅读 0赞

1、什么是二叉搜索树  
若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；  
若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；  
它的左、右子树也分别为二叉排序树。  
![在这里插入图片描述][20200606173840580.bmp_pic_center]  
2、插入节点  
二叉搜索数如何插入节点呢，我们来看看二叉搜索树的性质，  
首先二叉搜索树无重复值；如果插入值已经存在，则不插入。  
二叉搜索数根节点大于左子树所有节点，小于右子树所有节点，插入值如果大于根节点值，则插入右子树；插入值如果小于根节点值，则插入左子树。  
如果根节点为空，那么创建节点，根节点为插入节点

例：现在想插图55，首先和根节点50比较，比50大，再插入右子树，右子树和70比较，比70小，插入到60的子树，和60比较比60小，和60的左子树比较，左子树为空，那么创建节点，此时60的左节点就是55的节点

如上分析我们可以得到一个递归插入函数，二叉搜索树的创建就可以通过插入方法创建。

int intsertNode(TreeNode**p, const int val)
    {
        
        // 如果根节点为空，那么创建节点，根节点为插入节点
        if (NULL == (*p))
        {
        
            (*p) = new  TreeNode(val);
            return 1;
        }
        // 插入值小于根节点，则插入左子树
        if (val < (*p)->value)
        {
        
            int ok = intsertNode(&((*p)->left), val);
            // 反向握手 让新的节点的parent连上母亲
            if (1 == ok && (NULL != (*p)->left))
            {
        
                (*p)->left->parent = (*p);
            }
        }
        // 插入值大于根节点，则插入左子树
        else if (val >  (*p)->value)
        {
        
            int ok = intsertNode(&((*p)->right), val);
            if (1 == ok && (NULL != (*p)->right))
            {
        
                (*p)->right->parent = (*p);
            }
        }
        // 如果插入值已经存在，则不插入。
        else
        {
        
            printf("\n value %d Already have one ", val);
        }
        return 0;
    }

现在生成一个如上图所示的二叉树

int main(int argc, char *argv[])
    {
        
       TreeNode *p8;
        p8 = NULL;
        intsertNode(&p8, 50);
        intsertNode(&p8, 30);
        intsertNode(&p8, 20);
        intsertNode(&p8, 70);
        intsertNode(&p8, 60);
        intsertNode(&p8, 80);
        printNode(p8);
        return 0;
    }
    /* 打印前序和中序得到的遍历结果
    pre:50,30,20,70,60,80,	mid:20,30,50,60,70,80,
    */

3、二叉搜索树的删除  
若删除的节点无左子树，右子树，直接删除。（如下图，此时删除20，直接删除）  
![在这里插入图片描述][20200606174728362.bmp_pic_center]  
若删除的节点只有左子树，那么左子树的根节点连上要删除节点的母亲；（如上图，删除30）

若删除的节点只有右子树，那么右子树的根节点连上要删除节点的母亲；（如下图删除30）  
![在这里插入图片描述][20200606175115470.bmp_pic_center]  
若要删除的界面有左子树，又有右子树（如上图，删除50），那么有两种方式删除：  
①左子树的最大值nodeX，与根节点的值互换（只是值互换），删除nodeX，此时nodeX可能有左子树，则按照如上删除节点只有左子树的方式删除。  
②右子树的最大值nodeY，与根节点的值互换（只是值互换），删除nodeY，此时nodeY可能有右子树，则按照如上删除节点只有右子树的方式删除。  
如上总结出，一个递归方式实现

// 查找二叉树最大节点
    TreeNode* finMax(TreeNode* p)
    {
        
        if (NULL == p)
        {
        
            return NULL;
        }
        if (NULL == p->right)
        {
        
            return p;
        }
        else
        {
        
            return finMax(p->right);
        }
    }
    
    
    // 爷爷和孙子拉手
    void changeClidParent(TreeNode* parentNode, TreeNode* mySelf, TreeNode* childNode)
    {
        
        if (parentNode)
        {
        
            //  删除节点是母节点的左子树
            if (parentNode->left == mySelf)
            {
        
                parentNode->left =  childNode;
            }
            //  删除节点是母节点的右子树
            else if (parentNode->right == mySelf)
            {
        
                parentNode->right =  childNode;
            }
            // 左子树方向握上删除节点的母节点
            if (childNode)
            {
        
                childNode->parent = parentNode;
            }
        }
        // 如果没有父节点
        else
        {
        
            if (childNode)
            {
        
                mySelf = childNode;
                mySelf->parent = NULL;
            }
        }
    }
    
    
    int deleteValue(TreeNode**p, const int val)
    {
        
        if (NULL == (*p))
        {
        
            printf("\n%d not find ", val);
            return 0;
        }
        if (val > (*p)->value)
        {
        
            deleteValue(&((*p)->right), val);
        }
        else if (val < (*p)->value)
        {
        
            deleteValue(&((*p)->left), val);
        }
        else if (val == (*p)->value)
        {
        
            // 删除的节点无左子树，右子树
            if ((NULL == (*p)->left) && (NULL == (*p)->right))
            {
        
                TreeNode* deleteNode = (*p);
                TreeNode* parentNode = (*p)->parent;
                changeClidParent(parentNode, deleteNode, NULL);
                delete (*p);
                (*p) = NULL;
                printf("\tdelete:%d", val);
            }
            // 删除的节点只有左子树
            else if ((NULL != (*p)->left) && (NULL == (*p)->right))
            {
        
                TreeNode* deleteNode = (*p);
                TreeNode* parentNode = (*p)->parent;
                TreeNode* leftNode = (*p)->left;
                changeClidParent(parentNode, deleteNode, leftNode);
                delete deleteNode;
                deleteNode = NULL;
                printf("\tdelete:%d", val);
                return 1;
            }
            // 删除的节点只有右子树
            else if ((NULL == (*p)->left) && (NULL != (*p)->right))
            {
        
                TreeNode* deleteNode = (*p);
                TreeNode* parentNode = (*p)->parent;
                TreeNode* rightNode = (*p)->right;
                changeClidParent(parentNode, deleteNode, rightNode);
                delete deleteNode;
                deleteNode = NULL;
                printf("\tdelete:%d", val);
                return 1;
            }
            // 删除的节点有左子树、右子树 次方案为从左子树选择最大值删除
            else if ((NULL != (*p)->left) && (NULL != (*p)->right))
            {
        
                TreeNode* deleteNode = (*p);
                TreeNode* maxNode = finMax((*p)->left);
                deleteNode->value = maxNode->value;
                maxNode->value = val;
                deleteValue((&maxNode), val);
            }
        }
        return 0;
    }

[20200606173840580.bmp_pic_center]: https://img-blog.csdnimg.cn/20200606173840580.bmp#pic_center
[20200606174728362.bmp_pic_center]: https://img-blog.csdnimg.cn/20200606174728362.bmp#pic_center
[20200606175115470.bmp_pic_center]: https://img-blog.csdnimg.cn/20200606175115470.bmp#pic_center