数据结构错题本

二叉树

有关二叉树的数学知识

二叉树每层节点数

二叉树中每层的节点数都是其上一行的两倍:1 2 4 …

因此每层的节点数为首项为 1 公比为 2 的等比数列的通项公式:

满二叉树节点总数

二叉树中每层的节点数为:1 2 4 …

是一个公比不等于 1 的等比数列,由等比数列的求和公式

得满二叉树的节点总数:

其中 n 为二叉树层数。

例题一个完全二叉树节点数为200,则其叶子结点个数为?

常规解法:$2^n - 1 <= 200$ ,将 1 移到等式右边两边同时取对数得到 $log_2{128} < n = log_2{201} < log_2{256}$,推出 8 < n < 10,所以 n = 9。

因为是完全二叉树,因此前 8 层一定是满的,于是第九层节点数等于 $200 - (2^8 - 1) = 73$,完全二叉树中叶子节点一定是按顺序排列的,因此第八层中有 33 个节点有叶子节点,$2^{8 - 1} - 37 = 27$,所以总共有$73 + 27 = 100$ 个叶子节点。

根据二叉树的性质:完全二叉树除最后一层,其他层都是满结点的。所以这里总结点200个,是偶数,可以判断度为1的结点是1个。

根据二叉树性质 $n_0 = n_2 + 1$;叶子结点数量等于度为2的结点数+1

完全二叉树度为1的结点个数要么1,要么0. 叶子结点数为整数,这里也可以推断出度为1的结点个数是1,$n_0 = 100$,所以叶子结点数是100.

总结::完全二叉树,叶子结点数 $n_0 = \lceil{n/2}\rceil$。