Binärer Baum: Algorithmus für Einfügen



  • Hallo

    Wir haben in der Schule eine Klasse für einen Binäre Baum geschrieben. Außerdem haben wir eine Klasse Knoten.

    Nun muss ich dem Baum eine Funktion schreiben, die einen Knoten an der richtigen Stelle einfügt, und nur einen Werrt als Argument braucht.

    Knoten.links und Knoten.rechts werden durch den Konstruktor auf null gesetzt.

    Hier die Funktion:

    public void insert(int wert)
            {
                Knoten neu = new Knoten(wert);
                Knoten puffer = wurzel;
    
                while (puffer.links != neu && puffer.rechts != neu && puffer.wert != neu.wert)
                {
                    if (neu.wert < puffer.wert)
                    {
                        if (puffer.links == null)
                            puffer.links = neu;
                        else
                            puffer = puffer.links;
                    }
                    else
                    {
                        if (puffer.rechts == null)
                            puffer.rechts = neu;
                        else
                            puffer = puffer.rechts;
                    }
                }
            }
    

    Genau geht es um meine Bedingung in der while. Ich betrachte links und rechts als "Zeiger" und überprüfe eben ob links oder rechts von dem Knoten, mein neuer Knoten schon ist.
    Außerdem dürfen keine doppelten Werte vorkommen(Diese Bedingung alleine würde eig reichen).

    ABER: Mein Prof. kritisierte mich das dies falsch ist, und ich nur "Glück" habe das es funktioniert. Er konnte es mir leider nicht klar machen, dass es so ist, daher frage ich euch.

    Entschuldigt bitte die Mischung von Deutsch und English im Quellcode.
    Die Denkweise mit den Zeigern bei links und rechts könnte ich mir durch mein häufiges Python programmieren in letzter Zeit angeeignet haben.

    Danke im voraus. mfg naeg



  • Also ich hab dir mal meine Variante des einfügens in einen AVL-Baum gepostet.Vielleicht hilft dir das ja weiter.

    private void IntegrateNewNode(TKey key,TValue value)
            {
                var keyHashCode = key.GetHashCode();
    
                lock (_lockObject)
                {
                    BinaryEntry current = this._root;
                    while (current != null)
                    {
                        if (keyHashCode < current.KeyHashCode)
                        {
                            if (!current.HasLeftChild())
                            {
                                current.LeftChild = new BinaryEntry(key, value);
                                current.LeftChild.Parent = current;
                                return;
                            }
                            else
                            {
                                current = current.LeftChild;
                            }
                        }
                        else
                        {
                            if (!current.HasRightChild())
                            {
                                current.RightChild = new BinaryEntry(key, value);
                                current.RightChild.Parent = current;
                                return;
                            }
                            else
                            {
                                current = current.RightChild;
                            }
                        }
    
                    }
                }
    
            }
    


  • Hab' deinen Code nur überflogen, aber beobachte doch mal den Ausdruck

    puffer.wert != neu.wert
    

    im Debugger.


Log in to reply