数据结构树与⼆叉树常⽤计算公式
在⼆叉树的理论推导以及⼀些⾼频类型题中，我们经常需要计算⼆叉树的总结点数，某⼀层的结点数以及已知结点数反推树的⾼度，本⽂围绕这⼏个⾼频知识点，归纳总结以下公式。
公式
（1）⾮空⼆叉树叶⼦结点数 = 度为2的结点数 + 1 即，N0=N2+1
（2）⾮空⼆叉树上第K层⾄多有2k−1个结点（K≥1）
（3）⾼度为H的⼆叉树⾄多有2H−1 个结点（H≥1）
（4）具有N个（N>0）结点的完全⼆叉树的⾼度为⌈log2(N+1)⌉或⌊log2N⌋+1
（5）对完全⼆叉树按从上到下、从左到右的顺序依次编号1,2，...，N，则有以下关系：
①当i>1 时，结点i的双亲结点编号为⌊i/2⌋，即当i为偶数时，其双亲结点的编号为i/2 ，它是双亲结点的左孩⼦；当i为奇数时，其双亲结点的编号为 (i−1)/2 ，它是双亲结点的右孩⼦。
②当 2i≤N时，结点i的左孩⼦编号为 2i，否则⽆左孩⼦。
③当 2i+1≤N时，结点i的右孩⼦编号为 2i+1 ，否则⽆右孩⼦。
二叉树公式
④结点i所在层次（深度）为⌊log2i⌋+1 。（设根结点为第1层）
经典例题
**408考研-2011-4** 若⼀棵完全⼆叉树有768个结点，则⼆叉树中叶结点的个数是_____。
A.257
B.258
C.384
D.385
解法1
根据完全⼆叉树的性质，最后⼀个分⽀结点的序号为⌊n/2⌋=⌊768/2⌋=384 ，故叶⼦结点的个数为 768−384=384
解法2
由⼆叉树的性质N=N0+N1+N2和N0=N2+1 可知
N=2N0−1+N1，2N0−1+N1=768
显然，N1=1，2N0=768，则N0=384
解法3
完全⼆叉树的叶⼦结点只可能出现在最下两层，由题可计算完全⼆叉树的⾼度为10。
第10层的叶⼦结点数为 768−(29−1)=257
第10层的叶⼦结点在第9层共有⌈257/2⌉=129 个⽗节点
第9层的叶⼦结点数为 (29−1)−129=127
则叶⼦结点总数为 257+127=384
Processing math: 100%

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。