Binärsuchbaum insert implementieren



  • Ich versuche gerade, in meinem Binärsuchbaum (struct Tree) die insert-Funktion hinzuzufügen, bekomme es aber nicht hin, dass er stoppt, wenn der letzte Knoten ein Nullpointer ist (also welcher letzendlich durch den key ersetzt werden soll) und bekomme dadurch "unendlich" neue Klammern.
    Kann mir bitte jemand sagen, was ich falsch mache?

    #include <iostream>
    #include <cassert>
    
    int livingTrees = 0;
    struct Tree {
        Tree* left;
        int key;
        Tree* right;
        Tree(Tree* l, int k, Tree* r) : left(l), key(k), right(r) {
            ++livingTrees;
        }
        ~Tree() {
            delete left; delete right;
            --livingTrees;
        }
    };
    
    std::ostream& operator<<(std::ostream& out, const Tree* T) {
        if (!T)
            return out << "-";
        else
            return out << "(" << T->left << "," << T->key << "," << T->right << ")";
    }
    
    bool lookup(const Tree* T, const int key) {
    
        std::cout << "Lookup!" << std::endl;
    
        if (T == NULL || T->key == NULL)
        {
            return false;
        }
        
        if (key == T->key)
        {
            return true;
        } else if (key < T->key)
        {
            lookup(T->left, key);
        } else if (key > T->key)
        {
            lookup(T->right, key);
        }
    }
    
    Tree* insert(Tree* T, const int key) {
     
        if (livingTrees == 0) {
            Tree* T = new Tree{nullptr,key,nullptr};
            return T;
        }
    
        if (key == T->key)      // ==
        {
            return T;
        }
    
        if (key < T->key)        // <
        {
            if (T->left == nullptr)
            {
                Tree* M = new Tree{nullptr,key,nullptr};
                T->left = M;
                delete M; M = nullptr;
                return T;
            } else if (T->left != NULL) {
                insert(T->left, key);
            }
    
        }
        
        if (key > T->key)        //>
        {
            if (T->right == nullptr)
            {
                Tree* M = new Tree{nullptr,key,nullptr};
                T->right = M;
                delete M; M = nullptr;
                return T;
             } else if (T->right != NULL) {
                insert(T->right, key);
            }
            
        }
    }
    
    int main() {
        char c; int key;
        Tree* T = nullptr;
        while(std::cin >> c >> key) {
            if (c == 'l')
            {
                std::cout << lookup(T,key);
            } else if (c == 'i')
            {
                T = insert(T, key);
                std::cout << T << std::endl;
            }
        }
        delete T; T = nullptr;
        assert(livingTrees == 0);
    }
    


  • Das ist C mit cout. Wie lernst du C++?



  • This post is deleted!


  • @manni66 Das Struct, der operator und die main Funktion sind alles so wie sie da stehen von der Uni bereitgestellt, ich soll lediglich insert und lookup integrieren und den rest unberührt lassen.



  • YAIT (yet another incompetent techer)

    Du solltest bei deinem Compiler dringend Warnungen einschalten. Sowohl lookup als auch insert liefern nicht in allen Zweigen einen Wert zurück. Vieleicht ist das schon der Fehler.



  • @Wurstwasser701 sagte in Binärsuchbaum insert implementieren:

            Tree* M = new Tree{nullptr,key,nullptr};
            T->left = M;
            delete M; M = nullptr;
            return T;
    
            Tree* M = new Tree{nullptr,key,nullptr};
            T->right = M;
            delete M; M = nullptr;
            return T;
    

    Was hast du denn da vor?



  • @manni66
    Woran machst du das fest, dass das C ist? Das ist vielleicht nicht unbedingt modernes C++, aber C? Ich sehe da nix was auf C hinweist.



  • Erstens
    @axels hat ja hier schon den nagel auf den Kopf getroffen:

            Tree* M = new Tree{nullptr,key,nullptr};
            T->right = M;
            delete M; M = nullptr;
    

    @TE: ich erkläre dir mal kurz was du hier genau machst.
    Du erzeugt einen neuen Knoten und speicherst dessen Adresse in M.
    Dann legst du diese Adresse in T->right ab. Bis hierher ist noch alles gut.
    Jetzt löschst du den neuen Knoten wieder. T->right hat jetzt eine Adresse an der aber "nichts" mehr zu finden ist. Sprich, der erstbeste Zugriff auf diese Adresse ( T->right) macht "bumm".

    Auf Deutsch:
    Du baust ein Haus.
    Du sagst deinen Kumpels: "hier wohne ich, kommt vorbei wenn ihr bock habt".
    Dann sprengst du das Haus in die Luft.
    Und dann kommen irgendwann deine Kumpels vorbei und denken sich: "will der uns verarschen?".
    😃

    Zweitens

    Tree* T = new Tree{nullptr,key,nullptr};
    

    Die Konstruktor-Aufrufe von "Tree" werden von dir immer nur in dieser Form verwendet. "nullptr". D.h. "left" und "right" sind immer 0, sprich, sie existieren noch nicht. Wozu dann diese Parameter im Konstruktor? Setze "left" und "right" doch im Konstruktor standardmäßig auf "nullptr" und spar dir die beiden Konstruktorparameter.

    Drittens
    Gönne dir für "Tree" ruhig mal eine Klasse statt eines struct. Mache einige Member "private", baue dir dazu operatoren, die du brauchst und ein paar "public" Methoden, die notwendig sind.

    Viertens
    Im moderneren C++ würde man keine Roh-Pointer mehr nehmen ( "Tree*" ). Ich würde her vermutlich einen std::unique_ptr<Tree> einsetzen.

    Das sieht dann beispielhaft so aus ( angepasst ):

    struct Tree
    {
        std::unique_ptr<Tree> right = nullptr, left = nullptr;
        ...
    }
    ...
    T->right = std::make_unique<Tree> ( key );
    

    In dem Fall sparst du dir das "delete" und kannst auf diese Art aufräumen:

    T->right = nullptr;
    T->left = nullptr;
    

    Fünftens
    Bäume bedeuten meist Rekursion.
    Suche dir zum Verständnis der Rekursion erstmal ein leichteres Beispiel.



  • @It0101 sagte in Binärsuchbaum insert implementieren:

    @manni66
    Woran machst du das fest, dass das C ist? Das ist vielleicht nicht unbedingt modernes C++, aber C? Ich sehe da nix was auf C hinweist.

    T = insert(T, key); würdest du so etwas in C++ machen?



  • @manni66 sagte in Binärsuchbaum insert implementieren:

    @It0101 sagte in Binärsuchbaum insert implementieren:

    @manni66
    Woran machst du das fest, dass das C ist? Das ist vielleicht nicht unbedingt modernes C++, aber C? Ich sehe da nix was auf C hinweist.

    T = insert(T, key); würdest du so etwas in C++ machen?

    Sicherlich nicht. ich hätte ne Klasse dazu mit ner passenden Methode. Aber in C würde ich auch weder std::cout, noch streamoperatoren noch new und delete einsetzen. 😉

    Ist auch Wurscht. In jedem Fall ist es ausbaufähig 🙂


  • Mod

    @It0101 sagte in Binärsuchbaum insert implementieren:

    @manni66
    Woran machst du das fest, dass das C ist? Das ist vielleicht nicht unbedingt modernes C++, aber C? Ich sehe da nix was auf C hinweist.

    Es ist halt der typische Stil, wie man in (schlechtem!) C an die Sache ran gehen würde und nutzt (bis auf den einen überladenen Operator) kein einziges C++-Feature. Es ist sogar ein struct statt einer class! Würde man alle Ausgaben mit printf ersetzen und new mit malloc, hätte man ein compilierbares C-Programm. Der new-malloc Austausch ist dabei fast ein 1:1-Tausch. Die Ausgaben umzuschreiben ist ein bisschen Arbeit und meist der Grund, wieso diese C-Kurse so oft cout benutzen, weil's halt angenehmer zu nutzen ist.

    Ich stimme aber zu, dass dies kein sonderlich gutes Beispiel für C mit cout ist, weil der überladene Operator wenigstens ein Anfang von C++ ist. Ich mag auch allgemein die Implikation nicht, dass C allgemein nach schlechtem Frickelcode aussieht. Echtes, gutes C sieht ganz anders aus. Es ist eher ein Fall von "ein hinreichend inkompetenter Entwickler kann in jeder Sprache schlechten Frickelcode schreiben". @Wurstwasser701 : Das richtet sich gegen deinen Lehrer, nicht gegen dich.



  • Von dem ganzen "das ist C mit cout" hat aber keiner was. Der TE lernt nix und den Verantwortlichen Lehrer/Ausbilder könnt ihr auch nicht in eine dunkle Seitengasse zerren, auch wenn er es verdient hätte.



  • @It0101 sagte in Binärsuchbaum insert implementieren:

    Von dem ganzen "das ist C mit cout" hat aber keiner was.

    Und das steht da einfach nur so?



  • @manni66 sagte in Binärsuchbaum insert implementieren:

    @It0101 sagte in Binärsuchbaum insert implementieren:

    Von dem ganzen "das ist C mit cout" hat aber keiner was.

    Und das steht da einfach nur so?

    Nein natürlich nicht. Aber gerade die Anfänger muss man etwas mehr an die Hand nehmen, wenn man wirklich helfen will.


  • Mod

    Ist schwierig, jemandem in einem Forenbeitrag C++ beizubringen 🙂

    Man kann zwar eine Binärbaumimplemnentierung in C++ zeigen, aber die versteht der C-mit-cout-Anfänger ja nicht, weil er kein C++ spricht.

    Daher weißt man den Anfänger darauf hin, dass er mit einem anderen Lehrer/Lehrbuch besser bedient wäre. Mit "Das ist C mit cout und dein Lehrer ist doof" erfolgt das natürlich reichlich indirekt und setzt viel Eigeninitiative voraus. Besser wäre eine längere Erklärung "Dein Lehrer lehrt veraltete Paradigmen, […bla bla bla…], besser bedient wärst du mit Büchern aus dieser Lsite: […bla bla bla…]". Hat man halt selten Zeit für und müsste sich daher einen Mustertext zurecht legen, daher kommt so oft bloß ein "Das ist C mit cout und dein Lehrer ist doof".


Log in to reply