Drzewo binarne
Logowanie
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zapomniałem hasła
» Forum » Programowanie » [C, C++] Szukam pomocy

Drzewo binarne

Ostatnio zmodyfikowano 2017-03-27 20:50
Autor Wiadomość
blankow
Temat założony przez niniejszego użytkownika
Drzewo binarne
» 2017-03-26 23:40:58
Mam problem z drzewem binarnym. Probuje je zbudowac, lecz po odwolaniu sie do "pierwszego" (przynajmniej tak mi sie wydaje) elemntu, drukuje ostatni...
Czy moglby ktos wskazac luki w moim rozumowaniu+ wytlumaczyc co robie zle?



C/C++
#include <iostream>
#include <vector>
using namespace std;

struct wezel
{
    int dane;
    wezel * lewy_syn; //wskaznik na lewego syna
    wezel * prawy_syn; // wskaznik na praweg syna
};

void stworz_drzewo( wezel *& ojciec, wezel *& pomoc );
void stworz_tablice( vector < int > & kontener );

int main()
{
    wezel * korzen = NULL;
    wezel * pomoc;
    stworz_drzewo( korzen, pomoc );
   
    cout << pomoc->dane; // dlaczego nie pokazuje pierwszego elementu tylko ostatni?
   
    return 0;
}

void stworz_drzewo( wezel *& ojciec, wezel *& pomoc )
{
    vector < int > kontener;
    stworz_tablice( kontener );
   
    int rozmiar_kontenera = kontener.size();
   
    ojciec = new wezel; // wskaznik strukturalny = nowy wezel
   
    ojciec->dane = kontener[ 0 ]; // wypelniam
    ojciec->lewy_syn = NULL;
    ojciec->prawy_syn = NULL;
   
    pomoc = ojciec; // wskaznik pomoc = wskaznik ojciec
   
    for( int i = 0; i < rozmiar_kontenera - 1; i++ )
    {
        if( kontener[ i ] <= kontener[ i + 1 ] )
        {
            ojciec->lewy_syn = new wezel; // wskaznik lewy syn wskazuje na nowy wezel
           
            ojciec->dane = kontener[ i + 1 ]; // wypelniam
            ojciec->lewy_syn = NULL;
            ojciec->prawy_syn = NULL;
        }
       
        else
        {
            ojciec->prawy_syn = new wezel; // analogicznie
           
            ojciec->dane = kontener[ i + 1 ];
            ojciec->lewy_syn = NULL;
            ojciec->prawy_syn = NULL;
        }
    }
}
void stworz_tablice( vector < int > & kontener )
{
    int ile_liczb, i = 0, bufor;
    cout << "Ile liczb chcesz wprowadzic? "; cin >> ile_liczb;
    cout << "Wypelnij tablice danymi: " << endl;
   
    while( i < ile_liczb )
    {
        cin >> bufor;
        kontener.push_back( bufor );
        i++;
    }
}
P-159455
1aam2am1
» 2017-03-26 23:56:45
C/C++
for( int i = 0; i < rozmiar_kontenera - 1; i++ )
{
    if( kontener[ i ] <= kontener[ i + 1 ] )
    {
        ojciec->lewy_syn = new wezel; // wskaznik lewy syn wskazuje na nowy wezel
       
        ojciec->dane = kontener[ i + 1 ]; // wypelniam
        ojciec->lewy_syn = NULL;
        ojciec->prawy_syn = NULL;
    }
   
    else
    {
        ojciec->prawy_syn = new wezel; // analogicznie
       
        ojciec->dane = kontener[ i + 1 ];
        ojciec->lewy_syn = NULL;
        ojciec->prawy_syn = NULL;
    }
}
Tu masz same błędy.
Dlaczego ciągle tworzysz nowe węzły i dodajesz dane do ojca zamiast do lewego lub prawego węzła?

PS.
Zamiast tego if stwórz funkcję dodającą element do już istniejącego drzewa.
P-159456
blankow
Temat założony przez niniejszego użytkownika
» 2017-03-27 09:43:47
No bo przeciez lewy/prawy syn to tylko wskazniki, trzeba go przeciez podpiac do nowej struktury, ktora najpierw trzeba zaalokowac.

EDIT: Poprawilem  troszke po swojemu (bardzo mi zalezy na wykonaniu iteracyjnym-wtedy duzo lepiej rozumiem problem, a i zazwyczaj jest efektywniej od rek)

C/C++
#include <iostream>
#include <vector>
using namespace std;

struct wezel
{
    int dane;
    wezel * lewy_syn; //wskaznik na lewego syna
    wezel * prawy_syn; // wskaznik na praweg syna
};

void stworz_drzewo( wezel *& ojciec, wezel *& pomoc );
void stworz_tablice( vector < int > & kontener );
void dodaj_wezel( wezel *& ojciec, int wartosc_z_tablcy );

int main()
{
    wezel * korzen = NULL;
    wezel * pomoc;
    stworz_drzewo( korzen, pomoc );
   
    cout << pomoc->dane; // dlaczego nie pokazuje pierwszego elementu tylko ostatni?
   
    return 0;
}

void stworz_drzewo( wezel *& ojciec, wezel *& pomoc )
{
    vector < int > kontener;
    stworz_tablice( kontener );
   
    int rozmiar_kontenera = kontener.size();
   
    ojciec = new wezel; // wskaznik strukturalny = nowy wezel
   
    ojciec->dane = kontener[ 0 ]; // wypelniam
    ojciec->lewy_syn = NULL;
    ojciec->prawy_syn = NULL;
   
    pomoc = ojciec; // wskaznik pomoc = wskaznik ojciec
   
    for( int i = 0; i < rozmiar_kontenera - 1; i++ )
    {
        dodaj_wezel( ojciec, kontener[ i + 1 ] );
    }
}
void stworz_tablice( vector < int > & kontener )
{
    int ile_liczb, i = 0, bufor;
    cout << "Ile liczb chcesz wprowadzic? "; cin >> ile_liczb;
    cout << "Wypelnij tablice danymi: " << endl;
   
    while( i < ile_liczb )
    {
        cin >> bufor;
        kontener.push_back( bufor );
        i++;
    }
}
void dodaj_wezel( wezel *& ojciec, int wartosc_z_tablicy )
{
    if( ojciec->dane <= wartosc_z_tablicy )
    {
        wezel * nowy = new wezel;
        ojciec->lewy_syn = nowy;
        nowy->dane = wartosc_z_tablicy;
        nowy->lewy_syn = NULL;
        nowy->prawy_syn = NULL;
    }
   
    else
    {
        wezel * nowy = new wezel;
        ojciec->prawy_syn = nowy;
        nowy->dane = wartosc_z_tablicy;
        nowy->lewy_syn = NULL;
        nowy->prawy_syn = NULL;
    }
}

[ \c pp ]
P-159467
1aam2am1
» 2017-03-27 10:24:24
Co się stanie gdy lewy lub prawy będzie już zajęty? Zostanie nadpisany. Musisz to zmienić na pętlę. Która idzie po ścieżce drzewa i wstawia w odpowiednie miejsce dopiero gdy ono będzie pustre.
P-159468
blankow
Temat założony przez niniejszego użytkownika
» 2017-03-27 12:16:16
Masz racje. Juz dopisalem sobie te funkcje poprawnie, jak bede mial dostep do komputera to przekleje z telefonu do programu, wstawie kod i zamykam.

Spojrzalby ktos czy napewno jest ok?

C/C++
#include <iostream>
#include <vector>
using namespace std;

struct wezel
{
    int dane;
    wezel * lewy_syn; //wskaznik na lewego syna
    wezel * prawy_syn; // wskaznik na praweg syna
};

void stworz_drzewo( wezel *& ojciec, wezel *& pomoc );
void stworz_tablice( vector < int > & kontener );
void dodaj_wezel( wezel *& ojciec, int wartosc_z_tablcy );

int main()
{
    wezel * korzen = NULL;
    wezel * pomoc;
    stworz_drzewo( korzen, pomoc );
   
    cout << pomoc->dane; // dlaczego nie pokazuje pierwszego elementu tylko ostatni?
   
    return 0;
}

void stworz_drzewo( wezel *& ojciec, wezel *& pomoc )
{
    vector < int > kontener;
    stworz_tablice( kontener );
   
    int rozmiar_tablicy = kontener.size();
   
    ojciec->dane = kontener[ 0 ];
    ojciec->lewy_syn = NULL;
    ojciec->prawy_syn = NULL;
   
    for( int i = 1; i < rozmiar_tablicy; i++ )
    {
        dodaj_wezel( ojciec, kontener[ i ] );
    }
   
}
void stworz_tablice( vector < int > & kontener )
{
    int ile_liczb, i = 0, bufor;
    cout << "Ile liczb chcesz wprowadzic? "; cin >> ile_liczb;
    cout << "Wypelnij tablice danymi: " << endl;
   
    while( i < ile_liczb )
    {
        cin >> bufor;
        kontener.push_back( bufor );
        i++;
    }
}
void dodaj_wezel( wezel *& ojciec, int wartosc_z_tablicy )
{
    wezel * nowy;
    nowy = ojciec;
    nowy = new wezel;
   
    while( nowy )
    {
        if( wartosc_z_tablicy <= nowy->dane ) { nowy = nowy->lewy_syn; }
        else { nowy = nowy->prawy_syn; }
    }
   
    nowy->dane = wartosc_z_tablicy;
    nowy->lewy_syn = NULL;
    nowy->prawy_syn = NULL;
}

[ \c pp ]
P-159470
1aam2am1
» 2017-03-27 20:50:32
NIE.
Alokujesz pamięć.
Potem jeździsz po drzewie.
A na koniec wpisujesz wartości do NULL.
NIE.

C/C++
void dodaj_wezel( wezel * ojciec, int wartosc_z_tablicy )
{
    wezel * nowy;
    nowy = new wezel;
   
    nowy->dane = wartosc_z_tablicy;
    nowy->lewy_syn = NULL;
    nowy->prawy_syn = NULL;
   
    while( ojciec )
    {
        if( wartosc_z_tablicy <= ojciec->dane )
        {
            if( ojciec->lewy_syn ) { ojciec = ojciec->lewy_syn; } else { ojciec->lewy_syn = nowy; break; }
        }
        else
        {
            if( ojciec->prawy_syn ) { ojciec = ojciec->prawy_syn; } else { ojciec->prawy_syn = nowy; break; }
        }
    }
}
Jakoś tak.
P-159488
« 1 »
  Strona 1 z 1  
» Forum » Programowanie » [C, C++] Szukam pomocy
© Wszelkie prawa zastrzeżone 2005-2024