在上篇文章中，我们学习了二叉树的基本链式结构以及建树和遍历相关的操作。今天我们学习的则是一些二叉树相关的概念以及二叉树的一种变形形式。
完全二叉树
什么叫完全二叉树呢？在说到完全二叉树之前，我们先说另外一个名词：“满二叉树”。像我们之前文章中演示过的那个二叉树，就是一颗“满二叉树”。在这颗树中，所有的结点都有两个孩子结点，没有哪个结点是只有一个孩子结点的，并且所有最底层的叶子结点都在同一层，这种树就称为“满二叉树”，也称为“完美二叉树”。
是不是非常漂亮的一颗树？没错，这种二叉树非常地完美，它没有多余的结点，也没有缺少的结点，非常的漂亮。但是，在现实中，完美的东西是很稀少的，人生总会有一点缺憾嘛。我们尽量不要让自己有太多的缺憾，但也总不能过上没有一丝缺憾的人生。所以，我们允许叶结点出现在最下层和次下层，而且最下层的叶结点集中在树的左部，也就是叶结点只能有左子树，那么，这样的一颗略带缺憾的树就叫做“完全二叉树”。不要担心它不完美，因为这样略带缺憾的人生才是完整的嘛，所以“完全二叉树”是一种理想的树结构。
从定义中，我们可以看出，一颗“满二叉树”，必定是一颗“完全二叉树”，而一颗叶子结点都在一层的并且所有结点都有左右孩子结点的“完全二叉树”也就是一颗”满二叉树“。
为什么要讲”满二叉树“和”完全二叉树“呢？当然是为了我们接下来的内容做铺垫。因为”满二叉树“是最符合二叉树性质的一颗树。还记得树系列的第一篇文章中介绍过的二叉树的那五个性质吗？当时我们就是以那颗”满二叉树来源gao($daima.com搞@代@#码网“为例进行讲解的。而其中的 性质5 ，就是我们学习使用顺序结构存储二叉树的基础。
二叉树的顺序存储
通过”满二叉树“的概念，以及二叉树的 性质5 我们就可以实现使用一个数组来存储顺序结构的实现。
$treeList = ['', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O'];
相信大家不陌生吧，在上篇文章中，我们就是通过这个数组来建立链树的，而这个数组其实就是一个线性存储的二叉树。我们通过对比二叉树的 性质5 来看一下。
-
A 结点的下标是 1 ，它是我们的树根。它的子结点是 B 和 C ，对应的下标分别是 2 和 3 ，也就是 1 2 和 1 2 + 1 。
-
同理，我们再选取一个结点 F 。它的下标是 6 ，所以它的左孩子结点的下标是 6 2 = 12 ，对应的是 L ；它的右孩子结点是 6 2 + 1 = 13 ，对应的是 M 。
-
反过来看，一个结点的父结点就是 i / 2 。我们看下 K 结点的下标是 11 ，它的父结点就是 11 / 2 ，舍去小数点是下标 5 的位置，也就是结点 E ；结点 J 的下标是 10 ，它的父结点是 10 / 2 ，也是下标为 5 的 E 结点。
这下想以大家就明白了用数组是如何表示一颗二叉树结构了吧。而且数组这种结构更加的一维，更能体现出对于树的操作就是二维化一维的一种表示，也就是非线性转线性，这样才能让我们方便地操作这些数据。
转载请注明原文链接：什么是完全二叉树和线索二叉树？它们的顺序存储结构又是什么样的？
