c++ - 二叉搜索树删除

Question

删除功能在此 BST 树中不起作用。
问题 1 它不会像我在代码中给出的那样使删除的节点为空，其次它在 else 条件下变为无限。

#include<iostream>
using namespace std;

struct bstnode{
bstnode *lchild;
int data;
bstnode *rchild;    
};

void creatbst(bstnode *&T,int k){
    if(T=='\0'){
        T=new(bstnode);
        T->data=k;
        T->lchild='\0';
        T->rchild='\0';
    }
    else if(k<T->data){
        creatbst(T->lchild,k);
    }
    else if(k>T->data){
        creatbst(T->rchild,k);
    }
}

bstnode *searchbst(bstnode *T,int k){
    if(T=='\0')
    return ('\0');
    else{

     if(k<T->data)
return searchbst(T->lchild,k);  

    else if(k>T->data)
    return searchbst(T->rchild,k);  

    else
        return T;
    }
}

int nmax(bstnode *T){
    while(T->rchild!='\0'){
        T=T->rchild;
    }
    return (T->data);
}
int nmin(bstnode *T){
    while(T->lchild !='\0'){
        T=T->lchild;
    }
    return (T->data);
}
void printleaf(bstnode *T){
    if(T=='\0'){
    return; 
    }
    else if((T->rchild=='\0')&&(T->lchild=='\0'))
    cout<<T->data<<endl;
    else{
        printleaf(T->lchild);
        printleaf(T->rchild);
    }
}
void printnleaf(bstnode *T){
    if(T=='\0'){
        return;
    }
    else if(T->rchild!='\0' || T->lchild!='\0')
    {cout<<T->data<<endl;;
    printnleaf(T->lchild);
    printnleaf(T->rchild);}
    else{
    return;
    }
}

void ldelete(bstnode *T,int x){
    int y;
    T=searchbst(T,x);

    if((T->lchild=='\0')&&(T->rchild=='\0'))
    T='\0';
    else{
        y=nmax(T->lchild);
        T->data=y;
        ldelete(T,y);
    }
}



int main(){
    bstnode *T;
    bstnode *D;
    T='\0';
    creatbst(T,36);
    creatbst(T,20);
    creatbst(T,75);
    creatbst(T,42);
    creatbst(T,8);
    creatbst(T,31);
    creatbst(T,25);
    creatbst(T,3);
    creatbst(T,80);

    ldelete(T,20);
    printleaf(T);
    printnleaf(T);
    return 0;

}
/*delete function is not working*/

Answer 1

您需要传递对节点 T 的引用：

void ldelete(bstnode*&T,int x){
    int y;
    T=searchbst(T,x);

    if((T->lchild=='\0')&&(T->rchild=='\0'))
    T='\0';
    else{
        y=nmax(T->lchild);
        T->data=y;
        ldelete(T,y);
    }
}

否则，T节点只是在函数中本地更新。[我不相信这足以完全修复您的代码，但它应该可以解决眼前的问题]。

在其他评论中：不要'\0'用于指示空指针值。它是一个 NUL 字符，而不是一个 NULL 指针值，它们是完全不同的——编译器可能会接受两者相同，但对于读者来说，它有很大的不同。

Answer 2

您修改T, 但是T是一个局部变量。T如果要更改调用者传递的变量，则必须作为参考传递。就像你在createbst.

顺便说一句，您正在泄漏内存。