完全二叉树（Complete Binary Tree）的特性

2022-01-06  本文已影响0人  AnyunBo

在上一篇文章《二叉树（Binary Tree）类型特点》中我们了解了二叉树的一些常见类型和特点，这篇我们专注说下完全二叉树的特性。

附图1

tree_four.jpg

完全二叉树特性：

假设高度为h（ h ≥ 1 ）的完全二叉树，那么至少有\color{red}{2^h}\color{red}{^-}\color{red}{^1}个节点；最多有\color{red}{2^h}\color{red}{-}\color{red}{1}个节点；总节点数量为n 则 \color{red}{2^h}\color{red}{^-}\color{red}{^1} ≤ \color{red}{n} < \color{red}{2^h} , \color{red}{h-1} ≤ \color{red}{\log}_\color{red}{2}\color{red}{n} < \color{red}{h} ，伪代码：h = floor ( \color{red}{\log}_\color{red}{2}\color{red}{n} ) + \color{red}{1} , floor () 是向下取整的意思

以「附图一」为列推导：
只少有\color{red}{2^h}\color{red}{^-}\color{red}{^1}个节点：
\color{red}{2^h}\color{red}{^-}\color{red}{^1} = \color{red}{2^0} + \color{red}{2^1} + \color{red}{2^2} + …… + \color{red}{2^h}\color{red}{^-}\color{red}{^2} + \color{red}{1}
最多有\color{red}{2^h}\color{red}{-}\color{red}{1}个节点:
\color{red}{2^h}\color{red}{-}\color{red}{1} = \color{red}{2^0} + \color{red}{2^1} + \color{red}{2^2} + …… + \color{red}{2^h}\color{red}{^-}\color{red}{^1} , 即满二叉树 。
总节点数量为n ,\color{red}{2^h}\color{red}{^-}\color{red}{^1} ≤ \color{red}{n} < \color{red}{2^h} , \color{red}{h-1} ≤ \color{red}{\log}_\color{red}{2}\color{red}{n} < \color{red}{h}; 推导过程：
假如 \color{red}{\log}_\color{red}{2}\color{red}{n} = 4.8 ，则h= 5 ; \color{red}{\log}_\color{red}{2}\color{red}{n} = 5.2 , h= 6 ； \color{red}{\log}_\color{red}{2}\color{red}{n}= 6.0 ，h= 7; 由此可得：h = \color{red}{\log}_\color{red}{2}\color{red}{n} 向下取整 +\color{red}{1} 的结果
向下取整(floor) 和 向上取整（ceiling） 是不遵循四舍五入原则的

日常开发中的 除法默认都是向下取整的。以 Java 为例

int a = 5 / 2 ;
// 结果为2 ；不是2.5

一颗有n (n > 0 )个节点的完全二叉树 , 从上到下、从左到右对节点从1开始编号, 对任意第i个节点 ：

一颗有n (n > 0 )个节点的完全二叉树 , 从上到下、从左到右对节点从0开始编号, 对任意第i个节点 ：

假设有一颗完全二叉树的 总结点数量为 \color{red}{N} ，则他有多少个叶子节点

假设： 叶子节点数量为：\color{red}{n}_\color{red}{0} ； 度为1 的节点数量为\color{red}{n}_\color{red}{1}； 度为2 的节点数量为\color{red}{n}_\color{red}{2} ；
总节点数量为 \color{red}{N} = \color{red}{n}_\color{red}{0} + \color{red}{n}_\color{red}{1} +\color{red}{n}_\color{red}{2} ，且 \color{red}{n}_\color{red}{0} = \color{red}{n}_\color{red}{2} +\color{red}{1} ； 则：\color{red}{N} = \color{red}{2}\color{red}{n}_\color{red}{0} +\color{red}{n}_\color{red}{1} - \color{red}{1}
完全二叉树中 度为1的节点要么为0， 要么为1 ；所以：
（1）当\color{red}{n}_\color{red}{1} = 1 时； \color{red}{N} = \color{red}{2}\color{red}{n}_\color{red}{0} ，\color{red}{N} 必为偶数 ；
叶子节点数量为： \color{red}{n}_\color{red}{0} = \color{red}{\frac{N}{2} }；
非叶子节点数量： \color{red}{n}_\color{red}{1} + \color{red}{n}_\color{red}{2} = \color{red}{\frac{N}{2} }
（2）当\color{red}{n}_\color{red}{1} = 0 时； \color{red}{N} = \color{red}{2}\color{red}{n}_\color{red}{0} ，\color{red}{N} 必为奇数 ；
叶子节点数量为： \color{red}{n}_\color{red}{0} = \color{red}{\frac{N+1}{2} }；
非叶子节点数量： \color{red}{n}_\color{red}{1} + \color{red}{n}_\color{red}{2} = \color{red}{\frac{N-1}{2} }
由此可得：
总结点数量为 \color{red}{N} ，
第一种方式：
\color{red}{N}是偶数 ，叶子节点数量为： \color{red}{n}_\color{red}{0} = \color{red}{\frac{N}{2} }；
\color{red}{N}是奇数 ，叶子节点数量为： \color{red}{n}_\color{red}{0} = \color{red}{\frac{N+1}{2} }；
则叶子节点数量为： \color{red}{n}_\color{red}{0} = floor( \color{red}{\frac{N+1}{2} } ) ；floor( )是向下取整，
非叶子节点数量为： \color{red}{n}_\color{red}{1} + \color{red}{n}_\color{red}{2} = floor( \color{red}{\frac{N}{2} } ) ；floor() 是向下取整
代码中：

n0 = (n+ 1 )/ 2

或

n0 = n+ 1 >> 1

第二种方式：
叶子节点数量为： \color{red}{n}_\color{red}{0} = ceiling( \color{red}{\frac{N}{2} } ) ；ceiling() 是向上取整
非叶子节点数量为： \color{red}{n}_\color{red}{1} + \color{red}{n}_\color{red}{2} = ceiling( \color{red}{\frac{N-1}{2} } ) ；ceiling() 是向上取整

在国外的一些教材中对一些特殊的二叉树会有一些不同的名字，下面简单的说明一下：

完满二叉树 （Full Binary Tree）

所有非叶子节点的度都为2 ； 也就是国内说的 “ 真二叉树”

完美二叉树 （Perfect Binary Tree）

所有非叶子节点的度都为2 ，且所有的叶子节点都在最后一层； 也就是国内说的 “ 满二叉树”

完全二叉树 （Complete Binary Tree）

和国内的定义是一样的

上一篇 下一篇

猜你喜欢

热点阅读