Binärer Baum aufbauen

[masterholdy]

class Aufgabe5 {
private:
    typedef struct Knoten {
        Knoten *parent;
        Knoten *left;
        Knoten *right;
        int schluesselWort;
        std::string value;
        Knoten(int schluesselWort, std::string value) : parent(NULL),left(NULL),right(NULL),schluesselWort(schluesselWort),value(value) {}
        int key() {
            return schluesselWort;
        }
    } Knoten;
public:
    Knoten* root;
    Aufgabe5():root(0) {}
    void insert(int schluesselWort, std::string value) {
        Knoten* z = new Knoten(schluesselWort,value); /* zeiger auf zu einfügendes obj */
        Knoten* y; /* zeiger auf vorh. obj */
        Knoten* x = root; /* zeiger auf akt. obj */
        cout << "\n-[";
        while(x) { /* parent knoten für z suchen */
            y = x;
            if(schluesselWort < x->key()) {
                x = x->left;
            } else {
                x = x->right;
            }
            cout << "x";
        }
        cout << "]-\n";
        z->parent = y;
        if(!y) { /* wenn y == NULL => leerer Baum => z = root */
            root = z;
        } else if (z->key() < y->key()) {
            y->left = z;
        } else {
            y->right =  z;
        }
    }
    Knoten* min() {
        Knoten* tmp = root;
        while(tmp->left) {
            tmp = tmp->left;
        }
        return tmp;
    }

    Knoten* max() {
        Knoten* tmp = root;
        while(tmp->right) {
            tmp = tmp->right;
        }
        return tmp;
    }
    bool is_Empty() {
        return !root;
    }

};

Aufgabe5 a;
    for(unsigned int i = 0; i < 10; ++i){
        a.insert(i, "test"+i);
    }

Output:

-[]-

-[]-

-[]-

-[]-

-[]-

-[]-

-[]-

-[]-

-[]-

-[]-

Process returned 0 (0x0)   execution time : 0.010 s
Press any key to continue.

Mit Zeile:
zeile 21 -[ zeile 29 x zeile 21 ]-
Wollte ich gucken wie oft die Whileschleife aufgerufen wird, dass die Schleife im ersten Durchgang nicht aufgerufen wird ist ja klar, aber beim hinzufügen von weiteren Objekten muss die Schleife doch min. 1 mal durchlaufen werden?
Könnt ihr mir einen Tipp geben was ich falsch mache?
Das Programm läuft soweit ordentlich durch, probiere ich min / max zu benutzen oder auf ein Element zuzugreifen crasht alles, deswegen meine Vermutung ich habe beim Struct irgendetwas falsch gemacht, Tipps?

MFG

[manni66]

Knoten* y; /* zeiger auf vorh. obj */

Der Kommentar lügt: y ist ungültig. Nach kurzem überfliegen des Codes denke ich, das ändert sich auch nie.

typedef struct Knoten {

Dein Lernmaterial stammt aus der C-Steinzeit.

[masterholdy]

zeile 23 wird y zugewiesen
wie würde man es den in c++ style machen?

[manni66]

masterholdy schrieb:

zeile 23 wird y zugewiesen

Der Baum ist leer, füge den ersten Knoten ein.

wie würde man es den in c++ style machen?

Ohne typedef wie bei der äußeren Klasse.

[masterholdy]

class Knoten {
public:
    Knoten *parent;
    Knoten *left;
    Knoten *right;
    int schluesselWort;
    std::string value;
    Knoten(int schluesselWort, std::string value) : parent(NULL),left(NULL),right(NULL),schluesselWort(schluesselWort),value(value) {}
    int key() {
        return schluesselWort;
    }
};

void insert(int schluesselWort, std::string value) {
        Knoten* z = new Knoten(schluesselWort,value); /* zeiger auf zu einfügendes obj */
        if(!this->root) {
            this->root = z;
        }
        Knoten* y; /* zeiger auf vorh. obj */
        Knoten* x = this->root; /* zeiger auf akt. obj */
        cout << "\n-[";
        while(x) { /* parent knoten für z suchen */
            y = x;
            if(schluesselWort < x->key()) {
                x = x->left;
            } else {
                x = x->right;
            }
            cout << "x";
        }
        cout << "]-\n";
        z->parent = y;
        if(!y) { /* wenn y == NULL => leerer Baum => z = root */
            this->root = z;
        } else if (z->key() < y->key()) {
            y->left = z;
        } else {
            y->right =  z;
        }
    }

jetzt wird alles mit x zugespammt
aber ich sehe keinen punkt in der while schleife der zu einer endlosschleife führen könnte wenn jeder neue knoter left / right == null hat und somit ja x zu irgendeinen zeitpunkt null werden muss == die schleife beendet wird

[Th69]

Hast du keinen Debugger, mit dem du Schritt für Schritt durch das Programm gehen kannst?

Überlege mal, was du mit dem ersten Knoten machst (wenn root == NULL ist)...

[masterholdy]

aw ja ich sehe es if(!root){..} else{rest...}

ich gucke mir später mal den rest an, wenn noch was ist soll ich dann ein neuen thread erstellen? oder wann wird dieser geclosed?