Количество уровней в двоичном дереве с учетом списка данных

Question

Давайте рассмотрим, что следующим является результат обхода порядка двоичного дерева.

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

Но, у меня есть вопрос, как, с данным списком данных, как вычислить общее количество уровней в двоичное дерево.

Я думал, что некоторые вещи, как, Sqrt (8) и делать Math.Round к ней, даст результат.

Но я сомневаюсь, что я ошибаюсь.

Могу ли я знать, что идеально подходит для этого.

Заранее спасибо ...

Answer 1

В общем случае, бинарное дерево с узлами n будет иметь по крайней мере 1 + floor(log_2(n)) уровней. Например, вы можете поместить 7 узлов на 3 уровня, но 8 узлов будут занимать не менее 4 уровней независимо от того, что.

Также в общем случае верхний предел равен n уровням в случае вырожденного двоичного дерева (которое выглядит как связанный список, свисающий с корня). Рассмотрим ваш пример, где обход уровня (также известный как обход ширины) - 1 2 3 4 5 6 7 8. В этом возможны следующие случаи, наряду с все между ними:

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

Есть particular types of binary trees, для которых вы можете поставить сильные ограничения на верхний предел. Для полный или полный двоичных деревьев, количество уровней всегда 1 + floor(log_2(n)), так как форма дерева зависит только от n.

Answer 2

Если вы маркировать узлы с индексом в ширину-первых для того, вы можете вычислить уровень без обхода в O (1) время. Поэтому, если вы выполняете несколько запросов, вы можете сделать O (N) BFT и получить каждый запрос в течение O (1).

Формула уровне:

level = floor(log(index + 1)) 

Если бревно к основанию 2

Эта ссылка поможет вам How can I calculate the level of a node in a perfect binary tree from its depth-first order index?

Answer 3

Высота полного бинарного дерева до O(logN) , Где N - количество узлов, которые вы заполняете деревом.

Обратите внимание, что запись Big O требуется из-за того, что фактическая высота может варьироваться в зависимости от коэффициента добавления или масштабирования.

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