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

标准

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

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

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

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

图解：

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

但是，举个例子来说：

这种情况就不符合第一个，B属于叶子节点，但是已经在倒数第三层。所以就不是完全二叉树。

或者：

这个时候，很明显B属于节点，c是叶子节点，但是在右边，不是向左聚拢，所以不属于完全二叉树的概念。

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

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

图解：

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