本文共 755 字，大约阅读时间需要 2 分钟。

原文地址：

我们已经在第一章中介绍了二叉树，在这一章，介绍一下二叉树的特性。

1）一个二叉树中第$l$层的节点最大数目为

2l−1

$2^{l-1}$。

这里的“层”指的是从根节点到指定节点的路径上的节点数。根在第1层。

这个可以通过归纳法证明。

对于根，$l=1$，节点数$=2^{1-1}=1$ 假设在$l$层的最大节点数为$2^{l-1}$ 因为在二叉树中每个节点最多有两个孩子节点，下一层将会又两倍的节点，比如：$2*2^{l-1}$

2）一个高度为$h$的二叉树的节点的最大数为

2h−1

$2^h-1$

这里的高度指的是一个树根节点到叶子节点的节点数目最多的路径。一个叶子节点的高度认为是1.

这个结果可以从上面的第二点推出。如果没一层的节点数都是最大的，那么这个树就有最多的节点数。所以一个高度为$h$的二叉树的最大节点数是

1+2+4+..+2h−1

$1+2+4+..+2^{h-1}$。这是一个有n项的简单的等比数列，这个数列的和是$2^h-1$。

在一些书籍中，叶子节点的层数认为是0。如果按照这个约定，那么上面的公式就写为$2^{h+1}-1$。

3）一个二叉树有N个节点，那么这个二叉树的最小可能树高或者是最小层数可能是$\lceil\log_2(N+1)\rceil$

这可以直接从上面的第二点得出。如果我们考虑叶子节点的层数为0，那么上述式子的最小可能的高度是$\lceil\log_2(N+1)\rceil-1$

4）有L个叶子节点的二叉树至少有$\lceil\log_2L\rceil+1$层

当每层都填满的时候，那么这个二叉树就有最大的叶子节点数。假设所有的叶子节点都在l层，那么下面的式子就是L层的叶子节点的数：

$L <= 2l-1$ [来自第一点]

$log_2L <= l-1$

$l >= ⌈ Log_2L ⌉ + 1$

5）在二叉树中，叶子节点的数目总是比有两个孩子的节点的数目多1

L = T + 1在这里 L = 叶子节点的数目      T = 有两个孩子的内部节点数目

转载地址：http://zkhii.baihongyu.com/