Anzahl der Ebenen in Binary Tree angesichts der Liste der Daten

Question

Betrachten wir, dass das Folgende die Resultierende des Level Order Traversal des Binary Tree ist.

Ex: 1,2,3,4,5,6,7,8

Aber, ich habe eine Frage wie, mit der gegebenen Liste von Daten, wie die Gesamtzahl der Ebenen in der berechnen Binärbaum.

dachte ich soetwas wie, Sqrt (8) und die Math.Round, um es zu tun, wird das Ergebnis ergeben.

Aber ich bezweifle das, ich liege falsch.

Darf ich wissen, was das perfekt ist, das zu tun.

Vielen Dank im Voraus ...

Answer 1

Im allgemeinen Fall, ein binärer Baum mit n Knoten mindestens 1 + floor(log_2(n)) Ebenen haben. Zum Beispiel können Sie 7 Knoten auf 3 Ebenen anpassen, aber 8 Knoten benötigen mindestens 4 Ebenen.

Auch im allgemeinen Fall ist die Obergrenze n Ebenen im Falle eines degenerierten Binärbaums (der wie eine verkettete Liste aussieht, die von der Wurzel herabhängt). Stellen Sie sich Ihr Beispiel vor, bei dem die Travertierung der Ebenenreihenfolge (auch als "Breath-First Traversal" bezeichnet) 1 2 3 4 5 6 7 8 ist. Folgende Fälle sind möglich, zusammen mit allem, was dazwischen:

 1    1 
    /\    \ 
    / \    2 
    2  3    \ 
/\ /\    3 
    4 5 6 7    \ 
/      4 
8       \ 
          5 
    (4 levels)     \ 
           6 
           \ 
           7 
            \ 
            8 
         (8 levels) 

Es gibt particular types of binary trees, für die Sie stärkere Einschränkungen für die obere Grenze setzen können. Für komplette oder volle binäre Bäume, die Anzahl der Ebenen ist immer 1 + floor(log_2(n)), weil die Form des Baumes nur von n abhängt.

Answer 2

Wenn Sie die Knoten mit einem Index in Breiten erster Ordnung beschriften Sie die Ebene ohne Traversal in O (1) Zeit berechnen kann. Wenn Sie also mehrere Abfragen ausführen, können Sie eine O (N) -BFT ausführen und jede Abfrage in O (1) -Zeit beantworten.

für das Niveau Die Formel lautet:

level = floor(log(index + 1)) 

Wo das Protokoll an die Basis 2

Dieser Link hilft Ihnen How can I calculate the level of a node in a perfect binary tree from its depth-first order index?

Answer 3

Die Höhe eines vollständigen binären Baum bis zu O(logN) ist . Dabei ist N die Anzahl der Knoten, die Sie im Baum ausfüllen.

Beachten Sie, dass Big O-Notation aufgrund der Tatsache erforderlich ist, dass die tatsächliche Höhe durch eine Addition oder Skalierungsfaktor variiert.

https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html