drzewo binarne, tworzenie korzenia (wytłumaczenie roli fragmentu kodu)

pytanie zadane 18 sierpnia 2017 w C i C++ przez Jakub 0 Pasjonat (23,120 p.)
edycja 18 sierpnia 2017 przez Jakub 0

hej, mam pewne pytanie, dodam że rozumiem zasadę działania drzewa i kod jest napisany prze ze mnie . Może zanim dokładnie powiem co mam na myśli podam kod programu (tam jest zaznaczony fragment kodu którego sens tak średnio rozumiem):

#include <iostream> //na wszleki wypadek podałem cały kod
#include <windows.h>
#include <conio.h>
 
using namespace std;
 
struct drzewo { 
    int dane;
    drzewo *lewy_potomek;
    drzewo *prawy_potomek;
};
 
drzewo *korzen = NULL; 
 
void add(int x, drzewo *&rodzic) { //wstaw nowy element
    if(rodzic==NULL) {
        rodzic = new drzewo;
        rodzic->dane = x;
        rodzic->lewy_potomek = NULL;
        rodzic->prawy_potomek = NULL;
        
        /// mam na mysli ten fragment kodu :/ 
        if(korzen==NULL){ //po co to skoru mamy to co jest o gory
        	korzen = rodzic;
		}
		/////////////////////////////////////
		
    } else { 
        if(x>=rodzic->dane) add(x,rodzic->prawy_potomek);
        if(x<rodzic->dane) add(x,rodzic->lewy_potomek);
    }
}

void inOrder(drzewo *rodzic){ //sortoeanie 
     if(rodzic){
     	inOrder(rodzic->lewy_potomek);
        cout<<rodzic->dane<<" ";
        inOrder(rodzic->prawy_potomek);
	 }
}
 
int main() {
 
    while(true) {
        cout<<"---MENU---"<<endl;
        cout<<"1. dodaj"<<endl;
        cout<<"2. sort"<<endl;
        cout<<"----------"<<endl;
 
        char z = getch();
 
        switch(z) {
            case '1': {
                int value;
                cout<<"value: ";
                cin>>value;
                add(value,korzen);
                break;
            }
            case '2': {
                cout<<"sort: ";
                inOrder(korzen);
                getch();
                break;
            }
        }
         
        system("cls");
    }
 
    return 0;
}

generalnie mamy rekurencyjną funkcję wstawiania elementu do struktury... Na początek wskaźnik na korzeń drzewa wskazuje na NULL (bo korzenia jeszcze niema) . Potem w funkcji add dodajemy pierwszy element .I tu doszedłem do problemu ,niby wszystko jest ok, przy pierwszym wywołaniu początkowa wartość wskaźnika na korzeń jest równa NULL i tworzymy nowy element (powinien on się stać korzeniem bo jest wskaźnikiem na niego):

void add(int x, drzewo *&rodzic) { //wstaw nowy element
    if(rodzic==NULL) { //to fragment z funkcja add
        rodzic = new drzewo;
        rodzic->dane = x;
        rodzic->lewy_potomek = NULL;
        rodzic->prawy_potomek = NULL;

jednak po sprawdzeniu działania programu korzeń dalej wskazywał na NULL ,siłą rzeczy dodałem taki warunek:

if(korzen==NULL){ //jezeli korzenia jeszcze "nie ma" (na nic nie wskazuje)
        	korzen = rodzic; //korzen stanie się tym nowo utworzonym obiektem
		}

Czyli jeżeli korzenia jeszcze nie mamy to on staje się tym nowo utworzonym obiektem (korzen=rodzic) . Po co jednak to skoro i tak rodzic jest wskaźnikem na korzeń i jego efekty działania powinny wpłynąć na niego (na korzeń)?? (drzewo *& rodzic -w main-> add(value,korzen))Wiem że pytanie może wydawać się nie jasne ale ciężko go sprecyzować ,jak coś jest nie zrozumiałe to piszcie ,bardzo będę wdzięczny za wszelkie starania i pomoc :)

1 odpowiedź

odpowiedź 18 sierpnia 2017 przez j23 Mędrzec (194,920 p.)

Dobrze kombinujesz. IMO, odwoływanie się do wskaźnika korzen wewnątrz add jest kompletnie zbędne.

komentarz 18 sierpnia 2017 przez Jakub 0 Pasjonat (23,120 p.)

dzięki z odpowiedź , ale jak niby 'napisać rekurencje' bez wskaźnika w nagłówku funkcji ??

if(x>=rodzic->dane) add(x,rodzic->prawy_potomek);
        if(x<rodzic->dane) add(x,rodzic->lewy_potomek);

komentarz 18 sierpnia 2017 przez Jakub 0 Pasjonat (23,120 p.)

*i czemu konieczny jest fragment kodu napisany w pytaniu?

komentarz 18 sierpnia 2017 przez j23 Mędrzec (194,920 p.)

Nie rozumiem pytania. korzen nie musi być globalny i nie musisz się do niego odwoływać z wnętrza add. Tak wystarczy:

int main() 
{
    drzewo *korzen = nullptr; 

    add(666, korzen); // to wywołanie ustawi korzen
    add(777, korzen);
    add(555, korzen);
    add(888, korzen);
    ...
}

komentarz 18 sierpnia 2017 przez Jakub 0 Pasjonat (23,120 p.)

a, dzięki . już to rozumiem :) Co do pytania to może być trochę pogmatwane więc jeszcze raz powiem co mam na myśli ...

drzewo *korzen = nullptr; 
 
    add(666, korzen); // to wywołanie ustawi korzen

jak sam napisałeś to wywołanie ustawi korzeń, powinno się to dziać automatycznie (no bo logiczne że pierwszym pustym elementem w drzewie jest właśnie korzeń),czemu w takim razie funkcja żeby działać po prawnie potrzebuje jeszcze tego warunku ?:

if(korzen==NULL){ //jezeli korzenia jeszcze "nie ma" (na nic nie wskazuje)
            korzen = rodzic; //korzen stanie się tym nowo utworzonym obiektem
        }

jak dalej jest nie zrozumiałe to nie twoja wina ;), ale dzięki za pokazanie lepszej implementacji