Witam,
Mam problem z usuwaniem elementu z drzewa BST, zdaje ze pewnie juz mnostwo takich watkow w internecie, niestety zaden nie byl mi pomocny. Chcialem stworzyc wlasny program (jestem zupelnie poczatkujacy w dziedzinie programowania), w celu przygotowania sie na zajecia, dlatego prosze o szybko odpowiedz.
Problem jest nastepujacy: nie mam pojecia czemu, ale przy usuwaniu elementu usuwa sie cale drzewo. Byc moze nie jest to stricte funkcja usuwajaca, niestety drugi dzien nie jestem w stanie zlokalizowac bledu.
Z gory dziekuje za szybka pomoc!
#include<iostream>
using namespace std;
class lisc{
private:
lisc *left, *right, *parent;
int liczba;
public:
lisc():left(NULL), right(NULL), parent(NULL), liczba(0) {}
lisc(int licz):left(NULL), right(NULL), parent(NULL), liczba(licz) {}
~lisc() {}
friend class drzewo;
};
class drzewo{
private:
lisc *korzen;
public:
drzewo():korzen(NULL) {}
~drzewo() {
if(korzen!=NULL){
usun(korzen);
}
}
void usun(lisc *pomoc){
if(pomoc!=NULL){
usun(pomoc->left);
usun(pomoc->right);
delete pomoc;
}
}
void wstaw(int licz);
void inorder(lisc *pomoc);
void wyswietl_in();
lisc *poprzednik(lisc *pomoc);
lisc *szukaj(int licz);
lisc *usuwanie(lisc *pomoc);
void usun_element(int licz);
};
void drzewo::wstaw(int licz){
lisc *w, *p;
w= new lisc; //tworzymy dynamicznie nowy wezel
w->left=w->right=NULL; //zerujemy wskazania synow
w->liczba=licz; //wstawiamy dane
p=korzen; //wyszukujemy miejsce dla w, rozpoczynajac od korzenia
if(p==NULL){
korzen=w; //jesli drzewo jest puste to w staje sie korzeniem
}
else {
while(true){ //petla nieskonczona
if(licz < p->liczba){ //zaleznie od klucza idziemy do prawego lub lewego syna
if(p->left==NULL){ //jesli nie ma lewego syna to wezel nim sie staje
p->left = w;
break;
}
else p=p->left;
}
else {
if(p->right==NULL){
p->right=w;
break;
}
else p=p->right;
}
w->parent = p; //rodzicem wezla w jest zawsze wezel wskazany przez p
}
}
}
void drzewo::inorder(lisc *pomoc){
if(pomoc!=NULL){
inorder(pomoc->left);
cout << pomoc->liczba << endl;
inorder(pomoc->right);
}
}
void drzewo::wyswietl_in(){
if(korzen == NULL){
cout << "Drzewo jest puste. " << endl;
}
else {
cout << "Drzewo inorder: " << endl;
inorder(korzen);
}
}
lisc *drzewo::poprzednik(lisc* pomoc){
if(pomoc->left!=NULL){
pomoc=pomoc->left;
while(pomoc->right!=NULL){
pomoc=pomoc->right;
return pomoc;
}
}
}
lisc *drzewo::szukaj(int licz){
lisc *pomoc=korzen;
while(pomoc!=NULL){
if(pomoc->liczba==licz){
return pomoc;
}
if(pomoc->liczba < licz) pomoc=pomoc->right;
else pomoc=pomoc->left;
}
cout << "Brak elementu w drzewie. " << endl;
return 0;
}
lisc *drzewo::usuwanie(lisc *pomoc){
lisc *y=pomoc->parent; //rodzic usuwanego wezla
lisc *z;
if(pomoc->left!=NULL and pomoc->right!=NULL){ //wezel ma dwojke dzieci
z=usuwanie(poprzednik(pomoc)); //usuwamy poprzednik x i zapamietujemy go w z
z->left=pomoc->left;
z->right=pomoc->right; //wstawiamy pomoc w miejsce z
if(z->left!=NULL){
z->left->parent=z; //ustawiamy z jako rodzica
}
if(z->right!=NULL){
z->right->parent=z;
}
z->parent=y; // ustawiamy y jako rodzica z
if(y==NULL) korzen=z; //jesli z jest korzeniem
else if(y->left==pomoc) y->left=z;
else y->right=z; //jesli z nie jest korzeniem to podpinamy pod odpowiednie dziecko
}
else if(pomoc->left!=NULL or pomoc->right!=NULL){ //jedno dziecko lub wcale
if(pomoc->left!=NULL){ //z staje sie lewym lub prawym potomkiem usuwanego
z=pomoc->left;
}
else {
z=pomoc->right;
}
z->parent=y; //y staje sie rodzicem z
if(y==NULL) korzen=z;
else if(y->left==pomoc) y->left=z;
else y->right=z;
}
else{ //wezel nie ma dzieci
if(y!=NULL){ //czy wezel ma rodzica
if(y->liczba < pomoc->liczba) y->right=NULL; //szukamy wezla do usuniecia
else y->left=NULL;
}
else korzen=NULL;
}
return pomoc;
}
void drzewo::usun_element(int licz){
lisc *pomoc = new lisc(licz);
lisc *x=szukaj(licz);
if(x!=NULL) delete usuwanie(pomoc);
else cout << "Zostala podana zla wartosc. " << endl;
}
int main() {
drzewo sosna;
sosna.wstaw(5);
sosna.wstaw(10);
sosna.wstaw(18);
sosna.wstaw(2);
sosna.wstaw(20);
sosna.wyswietl_in();
sosna.usun_element(18);
sosna.wyswietl_in();
return 0;
}