给定数据列表的二叉树中的级别数

Question

考虑一下，下面是二叉树层序遍历的结果。

例如：1,2,3,4,5,6,7,8

但是，我遇到了一个问题，例如，对于给定的数据列表，如何计算二叉树中的总层数。

我想像 Sqrt(8) 并对其执行 Math.Round 会产生结果.

但我怀疑，我错了。

我可以知道，什么是最完美的。

提前致谢...

Answer 1

如果按广度优先顺序用索引标记节点，则无需任何遍历即可在 O(1) 时间内计算级别。因此，如果您正在进行多个查询，则可以执行 O(N) BFT 并在 O(1) 时间内回答每个查询。

等级公式为：

level = floor(log(index + 1))

其中log以2为底

这篇link对你有帮助How can I calculate the level of a node in a perfect binary tree from its depth-first order index?

Answer 2

一棵完全二叉树的高度最大为O(logN)。其中 N 是您在树中填充的节点数。

请注意，由于实际高度可能因某些加法或比例因子而异，因此需要大 O 表示法。

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

Answer 3

在一般情况下，具有 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 个，您可以对其上限施加更强的限制。对于complete或full二叉树，层数总是1 + floor(log_2(n))，因为树的形状只取决于n.

Answer 4

级别索引值可以从0或1开始。

如果您正在计算从 0 开始 的级别索引（即根在 级别 0），则

#no.of levels = floor(log_2(n))

如果您正在计算从 从 1 开始的级别索引（即根在 级别 1），那么

#no.of levels = 1 + floor(log_2(n))

给定数据列表的二叉树中的级别数

Number of levels in Binary Tree given the list of datas

binary-tree

data-structures