[C++]drzewo binarne

[kasztanowy_jim]

witam, mam problem z drzewem binarnym. Napisalem funkcje dodajaca kolejny wezel do takiego drzewa i chchcialem ja przetestowac, ale niestety program wysypuje sie - co ciekawe tylko wtedy, kiedy chce dodac liczbe mniejsza niz ta znajdujaca sie w korzeniu - jesli dodaje wieksza to wszystko jest ok. Niestety nie moge znaleŹĆ bledu, bede zobowiaznay za pomoc

 

 

class wezel {
     private:
             wezel *lewy;   //wskaznik na lewy wezel (mniejszy)
             wezel *prawy;  //wskaznik na prawy wezel (wiekszy)
             wezel *rodzic; //wskaznik na rodzica
             int wartosc;   //wartosc
             friend class drzewo;
     public:
             void Wyzeruj() { lewy=prawy=NULL;} ;  
             int Wez() {return wartosc;};           
     };

class drzewo {
     private: 

             wezel *korzen;  //wskaznik na korzen drzewa
             int licznik;        //zlicza ilosc elementow
     public:
            void Wyzeruj();
            int Dodaj(const int a);
            wezel* ZwrocKorzen() { return korzen;} ;
            void druk(wezel*t,int h);
     };

//konstuktor drzewa  
void drzewo:: Wyzeruj()
{
        korzen = NULL;
        licznik = 0;
}


int drzewo:: Dodaj(const int a)
{
    wezel *nowy;
    nowy = new wezel;
    nowy -> wartosc = a;
    nowy -> lewy = NULL;
    nowy -> prawy = NULL;
    nowy -> rodzic = NULL;
    //nowy->Wyzeruj();
    if (licznik==0)
    {
       //gdy licznik jest zerem wstawiany wezel bezie korzeniem
       //wiec jego rodzic to nulll
       korzen = nowy;
       licznik++;    
       return 0;
    }
    else
    {   /*wskazik miejsce bedzie przebiegal sciezke w dol drzewa, na poczatku
        wskazuje na korzen*/
        wezel *miejsce = korzen;
        /*rodzic miejsce wskazuje a rodzica miejsca, czyli poczatkowo na NULL*/
        wezel *rodzic_miejsca;
        //petla wykonuje sie dopoki miejsce nie jest wskaznikiem na zero 
        while(miejsce != NULL)
        {

              cout<<miejsce->wartosc<<endl;
              rodzic_miejsca = miejsce;
              if(a <  miejsce->wartosc)
              {
                   cout<<"AA"<<endl;
                   miejsce = miejsce ->lewy;
                   cout<<"BB"<<endl;
              }
              if (a > miejsce->wartosc)
              {
                    miejsce = miejsce ->prawy;
              }

        }
        cout <<rodzic_miejsca->wartosc<<endl;
        if ( a < rodzic_miejsca->wartosc)
        { 
             cout<<"1 !"<<endl;
             rodzic_miejsca->lewy = nowy;
             nowy -> rodzic = rodzic_miejsca;
             licznik++;
             return 0;
        }
        if ( a > rodzic_miejsca->wartosc)
        {
             rodzic_miejsca->prawy = nowy;
             nowy -> rodzic = rodzic_miejsca;
             licznik++;
             return 0;
        }
    }
    //jesli funkcja zwroci -1, to znaczy ze wezel o wartosci ktora chcemy dodac
    //znajduje sie juz na drzewie
   // return -1; 
}

[mateusz midor]

Czesc,

w sumie dwa drobne bledy poprawilem i dziala

Oto kod - poprawki opatrzone komentarzem "TUTAJ"

class wezel {

     private:
             wezel *lewy;   //wskaznik na lewy wezel (mniejszy)
             wezel *prawy;  //wskaznik na prawy wezel (wiekszy)
             wezel *rodzic; //wskaznik na rodzica
             int wartosc;   //wartosc
             friend class drzewo;
     public:
             void Wyzeruj() { lewy=prawy=NULL;} 
             int Wez() {return wartosc;}
};

class drzewo {
     private:
             wezel *korzen;  //wskaznik na korzen drzewa
             int licznik;        //zlicza ilosc elementow
     public:
            void Wyzeruj();
            int Dodaj(const int a);
            wezel* ZwrocKorzen() { return korzen;} 
            void druk(wezel*t,int h);
     };

//konstuktor drzewa  
void drzewo::Wyzeruj()
{
        korzen = NULL;
        licznik = 0;
}

int drzewo::Dodaj(const int a)
{
    wezel *nowy;
    nowy = new wezel();
    nowy -> wartosc = a;
    nowy -> lewy = NULL;
    nowy -> prawy = NULL;
    nowy -> rodzic = NULL;

    //nowy->Wyzeruj();
    if (licznik==0)
    {
       //gdy licznik jest zerem wstawiany wezel bezie korzeniem
       //wiec jego rodzic to nulll
       korzen = nowy;
       licznik++;
       return 0;
    }
    else
    {   /*wskazik miejsce bedzie przebiegal sciezke w dol drzewa, na poczatku
        wskazuje na korzen*/
        wezel *miejsce = korzen;
        /*rodzic miejsce wskazuje a rodzica miejsca, czyli poczatkowo na NULL*/
        wezel *rodzic_miejsca;
        //petla wykonuje sie dopoki miejsce nie jest wskaznikiem na zero
        while(miejsce != NULL)
        {

              cout<<miejsce->wartosc<<endl;
              rodzic_miejsca = miejsce;
              if(a <  miejsce->wartosc)
              {
                   cout<<"AA"<<endl;
                   miejsce = miejsce ->lewy;
                   cout<<"BB"<<endl;
              } else // TUTAJ zeby dalej nie sprawdzal (jeski a < miejsce->wartosc, to wskaznik miejsce ma juz wartosc NULL i stad byl ten blad)
              if (a > miejsce->wartosc)
              {
                    miejsce = miejsce ->prawy;
              }
                          else // TUTAJ - zeby nie wpadl w nieskonczana petle
                                       break;
        }
        cout <<rodzic_miejsca->wartosc<<endl;
        if ( a < rodzic_miejsca->wartosc)
        {
             cout<<"1 !"<<endl;
             rodzic_miejsca->lewy = nowy;
             nowy -> rodzic = rodzic_miejsca;
             licznik++;
             return 0;
        }
        if ( a > rodzic_miejsca->wartosc)
        {
             rodzic_miejsca->prawy = nowy;
             nowy -> rodzic = rodzic_miejsca;
             licznik++;
             return 0;
        }
    }
    //jesli funkcja zwroci -1, to znaczy ze wezel o wartosci ktora chcemy dodac
    //znajduje sie juz na drzewie
   // return -1;
}
int main(int argc, char *argv[])
{
 drzewo Drzewo;
       Drzewo.Wyzeruj();
       Drzewo.Dodaj(5);
       Drzewo.Dodaj(13);
       Drzewo.Dodaj(63);
       Drzewo.Dodaj(7);
       Drzewo.Dodaj(2);

 return EXIT_SUCCESS;
}

 

Milej zabawy z drzewami,

Pozdrawiam!

 

PS. blad do strzalu znalazl mi Valgrind (http://valgrind.org/docs/manual/QuickStart.html).

Niedlugo na moim blogu wrzuce krotki tutorial do tego narzedzia. Zapraszam!