Двоичное дерево поиска delete

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

Вы должны передать ссылку на узел Т:

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.

И, кстати, вы просачиваете память.