H5W3
当前位置:H5W3 > 其他技术问题 > 正文

数据结构 | 树与二叉树常用计算公式数据结构 | 平衡二叉树与平衡因子2020每日学习8h打卡

在二叉树的理论推导以及一些高频类型题中,我们经常需要计算二叉树的总结点数,某一层的结点数以及已知结点数反推树的高度,本文围绕这几个高频知识点,归纳总结以下公式。

公式

(1)非空二叉树叶子结点数 = 度为2的结点数 + 1 即,$ N_0 = N_2 + 1 $

(2)非空二叉树上第K层至多有$ 2^{k-1} $ 个结点($ K \ge 1 $)

(3)高度为H的二叉树至多有$ 2^H – 1 $ 个结点($ H \ge 1 $)

(4)具有N个($ N > 0 $)结点的完全二叉树的高度为 $ \lceil log_2{(N+1)} \rceil $ 或 $ \lfloor log_2{N} \rfloor + 1 $

(5)对完全二叉树按从上到下、从左到右的顺序依次编号1,2,…,N,则有以下关系:

① 当 $ i > 1 $ 时,结点 $ i $ 的双亲结点编号为 $ \lfloor i/2 \rfloor $ ,即当 $ i $ 为偶数时,其双亲结点的编号为 $ i/2 $ ,它是双亲结点的左孩子;当 $ i $ 为奇数时,其双亲结点的编号为 $ (i-1)/2 $ ,它是双亲结点的右孩子。

② 当 $ 2i \le N $ 时,结点i的左孩子编号为 $ 2i $ ,否则无左孩子。

③ 当 $ 2i+1 \le N $ 时,结点i的右孩子编号为 $ 2i+1 $ ,否则无右孩子。

④ 结点 $ i $ 所在层次(深度)为 $ \lfloor log_2{i} \rfloor +1 $ 。(设根结点为第1层)

经典例题

**408考研-2011-4** 若一棵完全二叉树有768个结点,则二叉树中叶结点的个数是_____。
A.257            B.258            C.384            D.385

解法1

根据完全二叉树的性质,最后一个分支结点的序号为 $ \lfloor n/2 \rfloor = \lfloor 768/2 \rfloor = 384 $ ,故叶子结点的个数为 $ 768 – 384 = 384 $

解法2

由二叉树的性质 $ N = N_0 + N_1 + N_2 $ 和 $ N_0 = N_2 + 1 $ 可知

$ N = 2N_0 – 1 + N_1 , 2N_0 – 1 + N_1 = 768 $

显然,$ N_1 = 1 , 2N_0 = 768 ,则 N_0 = 384 $

解法3

完全二叉树的叶子结点只可能出现在最下两层,由题可计算完全二叉树的高度为10。

第10层的叶子结点数为 $ 768 – (2^9-1) = 257 $

第10层的叶子结点在第9层共有 $ \lceil 257/2 \rceil = 129 $ 个父节点

第9层的叶子结点数为 $ (2^9 – 1) – 129 = 127 $

则叶子结点总数为 $ 257 + 127 = 384 $

本文地址:H5W3 » 数据结构 | 树与二叉树常用计算公式数据结构 | 平衡二叉树与平衡因子2020每日学习8h打卡