drzewo BST - usuwanie elementu

Odpowiedz Nowy wątek
2015-01-12 12:58
0

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;
}

Pozostało 580 znaków

2015-01-12 13:40
0

Mści się bezsensowne nazewnictwo zmiennych.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2015-01-12 13:41
0

A konkretnie?

Pozostało 580 znaków

2015-01-12 13:43
0

Jak konkretniej? Co wiersz to bezsensowna nazwa:

lisc *drzewo::usuwanie(lisc *pomoc){
    lisc *y=pomoc->parent; //rodzic usuwanego wezla
    lisc *z;

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2015-01-12 13:43
0
pastelowe napisał(a):

A konkretnie?

A konkretnie x, y, z. Nie wiadomo co jest czym.

edytowany 1x, ostatnio: Sarrus, 2015-01-12 13:43

Pozostało 580 znaków

2015-01-12 14:05
0

Nie wgłębiłem się w ten program, bo tak jak poprzednicy mówią, czytanie go to udręka, ale na pierwszy rzut oka:

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;
}

1) Wyciek pamięci. Masz pomoc = new lisc, a gdzie masz delete pomoc, np. gdy x == NULL?
2) pomoc to zdaje się jakiś liść totalnie niepowiązany z drzewem, więc jaki sens ma usuwanie(pomoc)?

Pozostało 580 znaków

2015-01-13 00:19
0

Dzieki za wszystko odpowiedzi, ale srednio mi sie przydaly prawde mowiac. Ma ktos moze przejrzysty kod na implementacje tego algorytmu?

Pozostało 580 znaków

2015-01-13 00:43
1

Wystarczy narysować na kartce i masz:

void drzewo::replace(lisc *parent,lisc *child,lisc *node)
  {
   if(node) node->parent=parent;
   if(!parent) korzen=node;
   else if(parent->left==child) parent->left=node;
   else /*if(parent->right==child)*/ parent->right=node;
  }

lisc *drzewo::usuwanie(lisc *node)
  {
   lisc *parent=node->parent,*lf=node->left,*rt=node->right;
   if(!lf) replace(parent,node,rt);
   else if(!rt) replace(parent,node,lf);
   else 
     {
      for(lisc *tmp=rt;tmp->left;) tmp=tmp->left;
      swap(node->liczba,tmp->liczba);
      replace(tmp->parent,tmp,tmp->rt);
      node=tmp;
     }
   delete tmp;
  }

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
edytowany 1x, ostatnio: _13th_Dragon, 2015-01-13 01:25

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0