完全二叉树标准（详细图解）

冷不防 2023-10-02 09:53 14阅读 0赞

标准

完全二叉树是效率很高的数据结构。众所周知，**完全二叉树是由满二叉树而引出来的**。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

**特点：**  
(1)所有的叶结点都出现在第k层或k-l层（层次最大的两层）  
(2)对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+l。

我想这个概念大部分人都能理解或者早已通彻，但是完全二叉树分分为**国际标准**以及**国内标准**两部分。

首先，**国内的完全二叉树**的定义：  
1.叶子节点都在最后一层或者倒数第二层  
2.叶子节点都向左聚拢

**图解：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2_size_16_color_FFFFFF_t_70 1]

像这两种图，国内的标准是可以的，只要叶子节点有一个的时候就要靠左就完全OK了。

但是，举个例子来说：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2_size_16_color_FFFFFF_t_70 2]  
这种情况就不符合第一个，B属于叶子节点，但是已经在倒数第三层。所以就不是完全二叉树。

**或者：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2_size_16_color_FFFFFF_t_70 3]  
这个时候，很明显B属于节点，c是叶子节点，但是在右边，不是向左聚拢，所以不属于完全二叉树的概念。

既然说了国内的，那么国际上的完全二叉树又是怎样的了？

**国际完全二叉树**的定义：  
1.叶子节点都在最后一层或者倒数第二层  
2.如果有叶子节点，就必然有**两个叶子节点**

**图解：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2_size_16_color_FFFFFF_t_70 4]  
这种情况在是符合完全二叉树的标准了，那么有人就有疑问了，国际二叉树的标准是否适用于国内标准，毋庸置疑，当然是可以，只不过国内的完全二叉树如果有叶子节点，也可以只是一个**叶子节点向左聚拢（国内标准）**，而另一个是**两个叶子节点（国际标准）**。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200223155409901.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200223153729761.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200223154207868.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200223154421401.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020022315470694.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2,size_16,color_FFFFFF,t_70