Ich bin neu mit dem Konzept, wenn binäre Bäume. Ich habe viele Tage auf eine Frage gestanden. Es ist zu finden, ob ein gegebener Baum ein binärer Baum oder ein vollständig binärer Baum ist oder keiner der beiden.
Ich habe an viele Algorithmen gedacht, aber keiner von ihnen erfüllt jeden einzelnen Fall. Ich habe versucht, Google, aber es gab keine richtige Lösung.
Ich dachte daran, Level-Order-Traversal-Technik zu verwenden, konnte aber nicht herausfinden, wie man ihre Level kennt, nachdem alle Knoten in die Warteschlange eingefügt wurden.
Für den Vollbinärbaum habe ich versucht zu zählen, wenn der Grad aller Knoten 0 oder 2 ist, aber wenn der Baum einen Zwischenknoten mit Grad hat, ist diese Logik ebenfalls falsch.
Ich habe einen Baum mit einer verketteten Liste erstellt, die grundlegende - Links Kind, Rechts Kind Beziehung Weg.
Für den vollständig binären Baum mache ich einen inorder traverl und überprüfe den Grad wenn 0 oder 2, aber es ist falsch, wenn es einen Knoten auf einer früheren Ebene mit Grad 0 gibt, dann wird auch die Ausgabe wahr.
Für den kompletten binären Baum konnte ich nichts passendes finden.
Danke.
Und ich benutze C ++, wenn also die Logik Zeiger verwendet, ist es in Ordnung.
Die Überprüfung auf Full ist einfach:
Durch die Definition hier. Ссылка
Der Baum ist voll, wenn alle Knoten entweder 0 oder zwei Kinder haben.
%Vor% Complete ist etwas härter.
Der einfachste Weg scheint jedoch eine Breite zu sein (von links nach rechts), um den Baum zu durchqueren. An jedem Knoten drücken Sie sowohl links als auch rechts auf die zu durchlaufende Liste (auch wenn sie NULL sind). Nachdem Sie den ersten NULL getroffen haben, sollten nur noch NULL-Objekte gefunden werden. Wenn Sie danach ein Nicht-NULL-Objekt finden, ist es kein kompletter Baum.
Überlege wie folgt:
%Vor% Die Funktionen werden rekursiv aufgerufen, bis sie die Blätter erreichen, bei denen die Tiefe jedes Blattes zurückgegeben wird, dann werden die Tiefen verglichen und wenn sie gleich sind (die Rekursion erreichte dieselbe Tiefe in jedem Teilbaum), wird der Wert der Tiefe zurückgegeben . Daher gibt die Funktion -1 zurück, wenn der Baum nicht voll ist, und ein Wert, der die Tiefe darstellt, wenn sie voll ist.
Der erste Aufruf sollte is_full_tree(root,0)
BEARBEITEN:
Um zu überprüfen, ob ein Baum ein kompletter Binärbaum ist (alle Ebenen haben alle Knoten außer vielleicht der letzte und alle Knoten werden nach links geschoben), daher ist es vollständig, wenn die Tiefe von die Blätter sind gleich, oder die linke ist um 1 größer als die rechte (das Gegenteil hält nicht an), daher modifizieren wir wie folgt:
%Vor% Sie können auch den 2. Algo verallgemeinern, um beide Dinge zu tun. Sie können ein Flag hinzufügen, das als Parameter als Referenz verwendet wird und nur modifiziert wird, wenn das erste else if zu true ausgewertet wird, was bedeutet, dass es ein Elternteil gibt, dessen linke Tiefe um 1 länger ist als seine rechte Tiefe. Daher wird der Algo wieder die Tiefe des Baumes zurückgeben, wenn es ein kompletter Baum ist und sonst -1.
Die Idee des zweiten Algo ist die gleiche wie die des ersten. Der Unterschied ist, dass wir sowohl die Tiefen "max" als auch "min" verfolgen müssen (es gibt nicht so viel wie maximale und minimale Tiefe, aber das ist die Intuition hinter der Idee, die "minimale Tiefe" wäre die Tiefe der tiefster Knoten, der nur 1 (links) Kind hat), der in jedem Teilbaum aufgezeichnet wurde, um einen Baum wie diesen analysieren zu können, zum Beispiel:
%Vor% Wo müssen wir wissen, was in den Teilbäumen passiert ist, wo B und C die Wurzeln sind, wenn wir sie analysieren. An dem Punkt, an dem wir B und C vergleichen, wird B (links) den Paarwert (3,2) haben, wobei die 3 für H , I und J mit der Tiefe von stehen 3 und 2 für den Knoten E , in dem sein rechtes Kind fehlt. C (rechts) hat auch den Wert (3,2), daher ist der Baum unvollständig, da es in beiden Unterbäumen einen "Bruch" gibt, daher sind nicht alle Knoten linksbündig.
Eine Möglichkeit, dies zu tun, könnte in der Tat ein Level Order Traversal sein, wie Sie es vorgeschlagen haben, es als BFS , und drücken Sie auf Ihre Warteschlange Paare von (Ebene, Knoten). Der Baum ist voll, wenn und nur wenn jede Ebene außer der letzten die doppelte Anzahl der Knoten der vorherigen oder 2^level hat.
Sehen Sie sich den folgenden Pseudocode an:
%Vor%Der obige Pseudocode prüft für jede Ebene, ob er genau 2 ^ Level-Knoten hat, und gibt true zurück, ansonsten false - was bedeutet, dass er prüft, ob der Baum voll ist.
Überprüfen, ob es nicht voll ist, aber vollständig erfordert ein bisschen mehr Arbeit für die letzte Ebene - und bleibt für Sie, das Konzept wird sehr ähnlich sein.
Hier ist die einfache Lösung für das Problem mit dem Platz sparenden DFS-Algorithmus im Gegensatz zu BFS-Einsen: -
%Vor%Psuedo-Code: -
%Vor%Code unten für "ist abgeschlossen" - mit einem Kommentar, der die zu entfernende Halblinie zeigt, um nach einem perfekten Binärbaum zu suchen (d. h. einer mit allen Blättern in der gleichen Tiefe). Dies ist kompilierbarer Code mit 3 Testfällen am Ende.
Das algorithmische Bit ist depths() , hier zur Diskussion wiedergegeben: mit zusätzlichen Kommentaren inline und unter (und ohne cout trace).
Um das Konzept zu erklären - betrachten Sie einen Baum (oder einen Teil davon), der so aussieht, wo Kind- / Enkelknoten existieren könnten oder nicht:
%Vor% Der Algorithmus generiert eine "depth" -Nummer für den Weg, bis zu dem die l1 , l2 , r1 und r2 Pfade erreicht werden können. Sagen wir, nur die Knoten mit * s existieren tatsächlich - dh l und l1 existieren, aber l2 nicht - dann wäre l1 's Tiefe 2, aber l2 ' s wäre 1. r existiert gar nicht, dann wäre r1 und r2 0.
Der Algorithmus beobachtet dann: Wenn l1 , l2 , r1 und r2 gleich sind, dann ist der Baum "perfekt". Wenn sie sich unterscheiden, kann es immer noch ein vollständiger Baum sein, aber die Tiefen müssen irgendwo um 1 abnehmen: z.B. wenn die Enkel Blattknoten sind, dann (2, 2, 2, 1) oder (2, 2, 1, 1) oder (2, 1, 1, 1) oder (1, 1, 1, 0) oder (1 , 1, 0, 0) oder (1, 0, 0, 0). Der einfachste Weg, dies zu testen, besteht darin, zu überprüfen, ob l1 >= l2 >= r1 >= r2 && l1 == r2 + 1 - d. H. Es gibt niemals eine Zunahme der Tiefe und die Tiefe der Enden nur 1 auseinander.
Schließlich wird der Algorithmus tief in den Baum zurückgespult, bis er mit einem Knoten mit mindestens einem Kind fertig ist, dann wird die Validierung durchgeführt, dann werden die unteren und oberen Enden des übergreifenden Bereichs (die höchstens 1 auseinander liegen) weitergegeben zur Berücksichtigung der bis zu vier untergeordneten Pfade vom übergeordneten Knoten.
Diese Betrachtung von vier untergeordneten Pfaden gleichzeitig ist etwas ungewöhnlich und kompliziert, aber es erlaubt uns, leicht eine Situation zu erkennen, in der die Tiefe an vier Knoten um mehr als 1 abweicht.
Wenn ich nur zwei Knoten gleichzeitig betrachtet hätte, dann könnte ein Baum mit zwei Schritten nicht ohne eine zusätzliche Variable erkannt werden, die schon Stufen oder Max-Tiefe gesehen hat ... aber wie Vikram's Antwort beweist - die Verwendung einer solchen Variable ist insgesamt einfacher.
Vollständiger Code:
%Vor%