Suche in Reihenfolge Nachfolger in binäre Suchbaum Verwenden von Rekursion

Question

Ich muss den In-Order-Nachfolger in einem binären Suchbaum finden. Um zum Beispiel einen Baum mit Format gegeben:

4 
/\ 
2 7 

und einen Suchwert von 2 vorbei, würde das in Ordnung Nachfolger 4.

Relevante Code:

template <typename T, typename Compare=std::less<T>>class BinarySearchTree { 
    private: 
    struct Node { 

     // Default constructor - does nothing 
     Node() {} 

     // Custom constructor provided for convenience 
     Node(const T &datum_in, Node *left_in, Node *right_in) 
     : datum(datum_in), left(left_in), right(right_in) { } 

     T datum; 
     Node *left; 
     Node *right; 
    }; 

Und meine hier Funktion Suche nach dem In-Order-Nachfolger

Nun glaube ich das Problem ist, dass meine Funktion nicht reco ist gnizing, wenn es tatsächlich am gewünschten Knoten ist. Ich denke, dass ich dies in einem zusätzlichen Basisfall oder vielleicht noch einer anderen if-Anweisung am Ende der Funktion überprüfen muss. Ich kann mir jedoch nicht vorstellen, wie ich das machen könnte, ohne einen rekursiven Aufruf des aktuellen Knotens zu machen, aber das würde einfach in der Endlosschleife enden.

Answer 1

Der einfachste Weg ist, einen Elternzeiger hinzuzufügen. Um "weiter" zu kommen, gehe hoch, bis du das Geschwister gefunden hast.

Wenn Sie einen Elternteil nicht oft aus guten Gründen verwenden können (z. B. die Struktur erlaubt doppelte Unterzweige), müssen Sie beim Abstieg einen eigenen Stapel von übergeordneten Objekten behalten. Um das nächste Objekt zu bekommen, wenn wir ein linkes Blatt sind, ist es das Elternteil, wenn wir ein rechtes Blatt sind, dann wenn Eltern ein linkes Blatt ist, ist es das Großelternteil, sonst müssen wir nach oben gehen und prüfen, ob der Großelternteil ein Linker ist Blatt der Urgroßeltern. (Wenn wir die Wurzel treffen, dann war unser Knoten das letzte rechte Blatt).