博客

昨天在看书的时候，突然看到二叉查找树的删除，以前学过，不过学的不仔细，结果研究了一晚上，才把二叉树的删除操作给整出来。

唉，以后看书要仔细啊。。。。。

先说一下如何删除二叉树查找树的节点吧。总共有三种情况

1.被删除的节点是叶子节点，这时候只要把这个节点删除，再把指向这个节点的父节点指针置为空就行

2.被删除的节点有左子树，或者有右子树，而且只有其中一个，那么只要把当前删除节点的父节点指向被删除节点的左子树或者右子树就行。

3.被删除的节点既有左子树而且又有右子树，这时候需要把左子树的最右边的节点或者右子树最左边的节点提到被删除节点的位置，为什么要这样呢，根据二叉查找树的性质，父节点的指针一定比所有左子树的节点值大而且比右子树的节点的值小，为了删除父节点不破坏二叉查找树的平衡性，应当把左子树最大的节点或者右子树最小的节点放在父节点的位置，这样的话才能维护二叉查找树的平衡性。（我是找的右子树的最小节点）

 

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <functional>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
struct node
{
    int value ;
    node * left;
    node * right;
};
typedef node * pnode;
void add(pnode & it,int i)
{

    if (it==nullptr)
    {
        it=new node;
        it->value=i;
        it->left=nullptr;
        it->right=nullptr;
    }
    else
    {
        pnode k=it;
        pnode now=new node;
        now->value=i;
        now->left=nullptr;
        now->right=nullptr;
        while(1)
        {
            if (i<=k->value)
            {
                if (k->left!=nullptr)
                {
                k=k->left;
                }
                else
                {
                k->left=now;
                break;
                }
            }
            else
            {
                if (k->right!=nullptr)
                {
                    k=k->right;
                }
                else
                {
                    k->right=now;
                    break;
                }
            }
        }
    }
}
void show(pnode it)
{
    queue<pnode>que;
    que.push(it);
    while(que.size())
    {
        pnode x=que.front();
        cout<<x->value<<" ";
        que.pop();
        if (x->left!=nullptr)
        {
            que.push(x->left);
        }
        if (x->right!=nullptr)
        {
            que.push(x->right);
        }
    }
}
void Delete(pnode & it,int val)
{
    pnode k,j=it;
    while(j->value!=val&&j)
    {
        if (val<=j->value)
        {
            k=j;
            j=j->left;
        }
        else
        {
            k=j;
            j=j->right;
        }
    }
    if (j==nullptr)
    {
        cout<<"无该点"<<endl;
        return ;
    }


    if (j->left==nullptr&&j->right==nullptr)//当这是个叶子节点
    {
        if (j==it)//如果删除的节点是根节点，直接删除置空
        {
            delete it;
            it=nullptr;

        }
        else//如果删除的节点不是根节点，把指向删除节点的指针置空
        {
            if (k->left==j)
            {
                k->left=nullptr;
            }
            else
            {
                k->right=nullptr;
            }
            delete j;

        }
    }
    else if (j->left==nullptr||j->right==nullptr)//左子树不为空或者右子树不为空
    {
        if (j->left!=nullptr)//如果是左子树不为空
        {
            if(it==j)
            {
                it=j->left;
            }
            else
            {
                if (k->left==j)
                {
                    k->left=j->left;
                }
                else
                {
                    k->right=j->left;
                }
            }
            delete j;
        }
        else
        {
            if(it==j)
            {
                it=j->right;
            }
            else
            {
                if (k->right==j)
                {
                    k->left=j->right;
                }
                else
                {
                    k->right=j->right;
                }
            }
            delete j;
        }
    }
/*看清楚这时候的删除操作，删除的不是j节点了，
删除的是把值赋给j节点的节点，
因为这时候这个节点已经被提到父节点的位置*/
    else if (j->left!=nullptr&&j->right!=nullptr)//
     {
            pnode pp=j;
            pnode p=j->right;
            while(p->left!=nullptr)
            {
                pp=p;
                p=p->left;
            }
            j->value=p->value;
            if (j==pp)
            {
                j->right=p->right;
            }
            else
            {
                pp->left=p->right;
            }
            delete p;
    }
}
int main()
{
/*我用的测试数据8 7 4 13 16 21 1 18 3 22*/
    pnode a=nullptr;
    int p;
    for (int i=0;i<10;i++)
    {
        cin>>p;
        add(a,p);
    }

    cout<<"删除节点3"<<endl;
    Delete(a,3);
    show(a);
    cout<<endl;
    cout<<"删除节点8"<<endl;
    Delete(a,8);
    show(a);
    cout<<endl;
    cout<<"删除节点24"<<endl;
    Delete(a,24);
    show(a);
    cout<<endl;
}