Recursivley Test, wenn ein binärer Suchbaum abgeschlossen ist

Question

Vor ein paar Tagen habe ich eine Frage zu diesem selben Projekt gestellt, seitdem hat unsere Gruppe alle unsere Methoden außer einer, die verwendet wird, um festzustellen, ob ein binärer Suchbaum ist Komplett.

Wir verwenden eine Wrapper-Methode und eine Hilfsmethode, um dies rekursiv zu tun.

Wir wissen, dass wir bis Level h-1 des Baumes (h ist Höhe) überprüfen müssen, um sicherzustellen, dass es perfekt ist, dann müssen wir sicherstellen, dass alle Blattknoten auf der letzten Ebene von links gehen ohne Lücken.

Egal was wir versuchen, wir können nicht herausfinden, wie man die verbleibenden Blattknoten rekursiv überprüft, um sicherzustellen, dass sie von links nach rechts aufeinander folgen. Wir können jedoch sicherstellen, dass es bis Level (h-1) perfekt ist.

Könnte uns jemand in die richtige Richtung zeigen, wie man die Blattknoten auf der letzten Ebene rekursiv überprüft, um sicherzustellen, dass sie linksbündig sind?

Soweit ist das Code?

public boolean isComplete() 
{ 
    if (isPerfect(root)) 
     return true;  
    return isComplete(root); 

} 
/** 
* 
* @param node 
* @return 
*/ 
private boolean isComplete(Node node) 
{ 
    if (height(node) > 1) 
    { 
    if (node.left != null && node.right != null && (height(node.left) == height(node.right))) 
     return isComplete(node.left) && isComplete(node.right); 
    else 
     return false; 
    } 

} 

PS alle trivialen Fälle in der isperfect() -Methode, da jeden perfekten Baum behandelt werden, ist ebenfalls komplett

Answer 1

konnte mich mit meinem Professor kommunizieren, und er informierte mof eine O (n), wie es mit nur einem Parameter in der isComplete Methode zu tun, im Vergleich zu einigen hier gegebenen Antworten.

diese Antwort hier ist die beste Antwort für meine ursprüngliche Frage

1. wenn hR> hL der Baum nicht abgeschlossen ist.
2. Wenn hL - HR> 1, ist der Baum nicht vollständig.
3. wenn hR == hL, dann der linke Unterbaum perfekt und der rechte Teilbaum muss
4. ansonsten vollständig sein muss (hL - hR == 1), dann der linke Unterbaum perfekt und der rechte Teilbaum muss es sein muss sei perfekt.

Schritte 3 und 4 rekursiv, wenn der Baum isperfect() und isComplete()

Answer 2

ich erste Note versuchen, den Algorithmus auf Vollständigkeit zu überprüfen und dann auf den Code weitermachen .

Lassen Sie uns dies in einem Pre-Order Traversal Ansatz denken.

• müssen die Anzahl der Knoten in dem Baum
• recurse von der Wurzel, Wurzel als Knotenindex 0
• wenn der Knoten null behandelt, Baum vollständig
• wenn Knotenindex größer ist als (oder gleich) die Anzahl der Knoten in der Struktur, dann ist es nicht abgeschlossen
• recurse auf linken und rechten Teilbaum; Bei dem Traversierungsansatz vor der Bestellung erhält der linke Baum den Index 2*i + 1 und der rechte Baum erhält 2*i + 2.

Ein bisschen Verständnis dafür, warum das funktionieren sollte.

Das folgende ist ein vollständiger Baum [mit Knotenindizes in eckigen Klammern]. Beachten Sie, dass die Knotenindizes im Falle dieses vollständigen Binärbaums strikt kleiner sind als die Anzahl der Knoten im vollständigen Binärbaum.

  1 [0] 
     /\ 
     / \ 
    [1] 2  3 [2] 
    /\ 
    / \ 
[3] 4  5 [4] 

Eine Funktion der Gesamtanzahl von Knoten im Baum

private int totalNodes(Node root) { 
    if (root == null) 
     return 0; 

    return 1 + totalNodes(root.left) + totalNodes(root.right)); 
} 

Nun zurück, die Hülle isComplete() Funktion [mit 0 Parameter, da der Stamm ein Klassenfeld sein] ...

public boolean isComplete() { 
    return isCompleteHelper(root, 0, totalNodes(root)); 
} 

Der isCompleteHelper() ...

private booelan isCompleteHelper(Node root, int indx, int totalNodes) { 

    // empty tree 
    if (root == null)   
     return true; 

    // present index >= number of nodes in tree 
    if (indx >= totalNodes) 
     return false; 

    // recurse 
    return isCompleteHelper(root.left, 2*indx+1, totalNodes) && isCompleteHelper(root.right, 2*indx+2, totalNodes); 
}