Konstruieren Sie einen binären Baum, so dass die Post-Order-Traversal das sortierte Ergebnis geben sollte

Question

Ich weiß, dass In-Reihenfolge-Traversal (Besuch links, Besuch Wurzel, rechts) auf einem binären Suchbaum sortierte Ergebnisse gibt. Aber ich muss einen Nachbestellungsdurchlauf (BESUCH LINKS, BESUCH RECHTS, BESUCH WURZEL) in einem Binärbaum durchführen und das Ergebnis sollte mir sortierte Werte geben.

Um das zu erreichen, wie soll ich meinen Binärbaum konstruieren?

Answer 1

Da der Stamm zuletzt besucht wurde, muss er das größte Element enthalten. Da der linke Teilbaum vor dem rechten Teilbaum aufgerufen wird, müssen alle Elemente im linken Teilbaum kleiner sein als alle Elemente im rechten Teilbaum.

Um einen Baum wie diesen zu erstellen, können Sie folgendermaßen vorgehen: Wenn Sie ein Element einfügen, das größer als der Stamm ist, wird dieses Element zum neuen Stamm. Wenn Sie ein Element einfügen, das kleiner als das Stammverzeichnis aber größer als das Stammverzeichnis des linken Teilbaums ist, fügen Sie es in den rechten Teilbaum ein. Andernfalls fügen Sie es in den linken Teilbaum ein.

Answer 2

Sie müssen die folgenden an jedem Knoten des Baumes gewährleisten:

• Wert am Knoten sollte als alle Werte in der linken Unterbaum und rechten Teilbaum größer sein.
• Die Werte im linken Teilbaum sollten weniger als die Werte im rechten Teilbaum sein.

Answer 3

Dieses Unterprogramm wird für die Insertion in dem Baum wo Baumstruktur

struct tree 

{ 

int data; 
tree * left; 
tree *right; 

tree(int n) // constructor 

{ 
     data = n; 
     left = right = NULL; 
    } 
}; 

Der Algorithmus ist:
1. Wenn Baum leer ist Einsatz neuen Knoten.
2. Wenn die Daten des neuen Knotens größer sind als die Daten des Root-Knotens, erstellen Sie den neuen Knoten
Root of Tree.
3. Andernfalls fügen Sie einen neuen Knoten in den linken Teilbaum des Baums ein.

Answer 4

Die currently accepted answer gibt einen guten Online-Algorithmus. Eine etwas einfachere Lösung --- die nicht online ist und daher möglicherweise betrügt --- besteht darin, eine sortierte verkettete Liste in den Elternzeigern zu speichern.

Mit anderen Worten: Sortieren Sie die Daten; Setzen Sie das größte Element in den Stamm, machen Sie einen seiner Teilbäume leer und erstellen Sie rekursiv einen nachgeordneten sortierten Baum der verbleibenden n-1 Elemente in den anderen Teilbaum.

Der Baum wird die Höhe n haben, das einzelne Blatt ist der Kopf der Liste und die Wurzel ist das am weitesten unten liegende Element. Wenn Sie durch den Baum von Blatt zu Wurzel gehen, werden die Elemente eine zunehmende Sequenz bilden, und dieser Pfad wird genau einer Nachorder-Traversierung entsprechen.

Answer 5

Deletion

• wenn Blatt, dann löschen Sie regelmäßig
• wenn es nur einen Sohn verbinden Sohn zu Vater
• sonst hat, löschen Sie die Wurzel, ersetzen Sie es mit dem rechten Sohn, schließen Sie dann links Unter -Baum zum ganz linken Scheitelpunkt im rechten Teilbaum.

zum Beispiel:

7               6 
/\              /\ 
    3 6    =========DELETING 7 ============>   4 5 
/\/\             / 
1 2 4 5             3 
                  /\ 
                  1 2