为什么这样写二叉查找树的删除操作是错误的呢？

Question

这样写的二叉查找树的删除操作中，当删除节点左右子树都存在时，为什么这样写只是删除了左子树的最右结点，却没有把左子树的最右结点放到删除位置上去呢？

```c++
.h

#ifndef TREE_SORT_H_H_INCLUDED
#define TREE_SORT_H_H_INCLUDED

#include <iostream>
#include <algorithm>

using namespace std;

typedef struct Tree
{
    int weight;
    struct Tree* left,*right;
}Tree,*pTree;

void initTree(pTree& pT,int w)
{
    pT=new Tree;

    if(pT==NULL)
    {
        cout<<"内存分配失败！"<<endl;
        return;
    }

    pT->weight=w;
    pT->left=pT->right=NULL;
}

void buildTree(pTree& pT,int w)
{
    if(!pT)
        initTree(pT,w);
    else if(w<pT->weight)
        buildTree(pT->left,w);
    else if(w>pT->weight)
        buildTree(pT->right,w);
}

void createTree(pTree& pT,int w[],int n)
{
    for(int i=0;i<n;i++)
        buildTree(pT,w[i]);
}

void dfs(pTree pT,int x)
{
    if(pT==NULL)
        return;

    if(x==0) cout<<pT<<" "<<pT->weight<<" ";
    dfs(pT->left,x);

    if(x==1) cout<<pT<<" "<<pT->weight<<" ";
    dfs(pT->right,x);

    if(x==2) cout<<pT<<" "<<pT->weight<<" ";
}

void deleteTree(pTree& pT,int w)
{
    pTree p=pT,q=pT,f=NULL;

    //找到删除节点
    while(p && p->weight!=w)
    {
        //f为删除节点的直接前驱
        f=p;
        q=p;

        if(p->weight>w)
            p=p->left;

        if(p->weight<w)
            p=p->right;
    }

    if(p==NULL)
    {
        cout<<"删除元素在二叉搜索树中不存在！"<<endl;
        return;
    }

    pTree t=p;

    //当该结点左右子树都存在的时候，则寻找左子树的最右结点取代该删除结点
    if(p->left && p->right)
    {
        //必须从删除结点的左子树开始找起！
        pTree l=p->left;
        while(l->right!=NULL)
        {
            //更新t来记录最右结点的前驱节点
            t=l;
            l=l->right;
        }

        p=l;
//        if(q->left==p)
//        {
//            q->left=l;
//            q->left->left=p->left;
//            q->left->right=p->right;
//        }
//        else
//        {
//             q->right=l;
//             q->right->left=p->left;
//             q->right->right=p->right;
//        }

        cout<<"p="<<p<<endl;
        cout<<"l="<<l<<endl;


        //判断左子树的最右节点直接前驱是否为该删除节点
        //若不为该删除节点，则将最右结点的左子树接到该直接前驱的右边
        //若为该删除节点，则直接将左右节点的左子树接到最右结点直接前驱的左边
        if(t!=p)
            t->right=l->left;
        else
            t->left=l->left;

        cout<<"左右子树都存在，操作完成！"<<endl;

        delete l;
        return;
    }
    //当该结点无左子树，则直接将右子树接过来
    else if(p->left==NULL)
    {
        cout<<"左子树不存在，直接将右子树接到该删除节点！"<<endl;
        p=p->right;
    }
    //当该结点无右子树，则直接将左子树接过来
    else if(p->right==NULL)
    {
        cout<<"右子树不存在，直接将左子树接到该删除节点！"<<endl;
        p=p->left;
    }

    if(f==NULL)
        pT=p;
    else if(t==f->right)
        f->right=p;
    else
        f->left=p;

    //不应该删除p，因为p已经是接完之后的结点
    //delete p;

    //删除t纯属是为了释放内存
    delete t;
}
#endif // TREE_SORT_H_H_INCLUDED

.c

#include <iostream>
#include "tree_sort_h.h"

using namespace std;

int main()
{
    cout<<"请输入需要输入的节点总数："<<endl;

    int n;
    cin>>n;

    int val[10]={89,99,90,14,68,98,97,100,19,79};
//    int val[100];
//    for(int i=0;i<n;i++)
//    {
//        cout<<"请输入该节点的数据为："<<endl;
//        cin>>val[i];
//    }

    pTree pT=NULL;
    createTree(pT,val,n);

    cout<<"创建二叉搜索树后的遍历为："<<endl;
    for(int i=0;i<3;i++)
    {
        dfs(pT,i);
        cout<<endl;
    }

    //deleteTree(pT,90);
    deleteTree(pT,99);
    //deleteTree(pT,1000);

    cout<<"删除操作后的二叉搜索树为："<<endl;
    for(int i=0;i<3;i++)
    {
        dfs(pT,i);
        cout<<endl;
    }

    return 0;
}

Answer 1

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7774148
• 这篇博客你也可以参考下：详解二叉搜索树的查找、插入、删除操作（数据结构）
• 这篇博客也不错, 你可以看下详解二叉搜索树的查找、插入、删除操作（数据结构）