完全二叉树

　　所谓完全二叉树，就是“不完全的满二叉树”。在满二叉树的构建或插入过程，当需要增加一层时，整层都要填满，然而下一层的元素数量是上一层的２倍，很多情况右树中的节点根本就没用过。这样完全二叉树就应运而生了，最底层的叶子填到非空节点为止。

　　对于深度为k的，有n个结点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1~n的节点一一对应时，称为完全二叉树。

　　二叉树必须符合：

　　(1)所有的叶节点都出现在第k层或k-1层（层次最大的两层）。

　　(2)对于任意节点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+1，简言之就是最底层的任意节点，它的左侧和上一层的节点必须是满的，如下图所示。

　　完全二叉树的最下层最右侧的叶子节点以上所有层和左侧必须是满的，右侧可以为空。如果这一点是这一层的最后一个节点，那么这就是满二叉树了。可见，满二叉树是完全二叉树的一个特例，也可以认为完全二叉树是“没满的满二叉树”。

　　完全二叉树的插人

　　如何构建完全二叉树实际是完全二叉树的插入的问题。与满二叉树的插入相似，不过要遵循最右侧叶子节点左侧和以上所有层节点必须满配这一原则。当有空节点时用数据直接覆盖；当没有空节点时，把上层没满的地方补满再插入新节点，然后补满新节点层的左侧。如下图所示，普通排序树和完全二叉树的插入3时的对比。

　　完全二叉树的插入操作算法逻辑如下：

　　(1)如果还没有根节点，插入根节点，否则按下面的步骤操作。

　　(2)如果插入节点数值小于当前节点数值，检查该层是否已满，否则补满，下行判断左子节点。

　　(3)如果插入节点数值大于当前节点数值，检查该层是否已满，否则补满，下行判断右子节点。

　　(4)如果插入节点数值等于当前节点数值，啥也不做，返回。

　　(5)如果当前节点是空节点，直接把数据覆盖进去，完成。

　　(6)如果当前节点不是空节点，但需要使用的左或右指针为空，把新节点连接到该节点后补齐它的左侧节点。

　　下面看完全二叉树插入新节点的算法图解。欲在完全二叉树中插入新值3，如下图所示。

　　程序代码（按层遍历代码隐藏了，在后一节中）：

　　运行结果：

　　查看完全二叉树

　　除了按层遍历，完全二叉树的遍历方式与满二叉树相同。直接使用二叉树的按层遍历方法也没有问题，由于完全二叉树允许最底层最右元素后空着，程序可能要空转。为了避免空转，修改按层遍历方法。

　　程序代码：

　　练习１：编程创建一个完全二叉树，把列表[6,7,3,5,9,8,4]添加进去，然后中序遍历和按层遍历。

　　判断一棵二叉树是不是完全二叉树

　　判断一棵二叉树是不是满二叉树和判断一棵树是不是完全二叉树的解题思路有相近。

　　解题思路：完全二叉树的判断是，最底层的叶子节点以上的树结构必须是一棵满二叉树；最底层最大叶子节点的左侧必须是满配，如下图所示。

　　算法逻辑：声明一个空位标志位sflag，然后做逐层判断，当发现某一层有空位时，判断该层后续和下一层是否还有节点。如果有，就不是完全二叉树；如果没有，则是完全二叉树。用代码直接构建一棵二叉排序树，树形如下图所示，

然后用上述逻辑判断其是不是一棵完全二叉树。

　　程序代码：

　　运行结果：

　　练习题２：一棵二叉树由数据[6,2,7,5,3]构成，在这个列表中补充数据后重新构造一棵二叉树，层数不变，最底层最后一个元素数值和位置都不变的完全二叉树。编写程序，验证你的结果。

　　完全二叉树节点删除
　　完全二叉树既然是没满的满二叉树，那它的节点删除与满二叉树就大同小异了。唯一不同的是如果底层有效数据节点后的空数据节点要删除。
　　程序代码：

　　运行结果：

　　
　　练习题３：把上例的删除顺序颠倒过来，最后的结果一样吗？编程测试一下。

　　学思营编程课堂基于蓝桥STEM86平台https://www.stem86.com，开展学编程三部曲：

Scratch（三年级以前）>>>Python（四年级以后）>>>C++（七年级以后）教育实验活动，任何人可以免费参加，打开https://xuesiying.stem86.com网页注册进入课堂，也可关注本公众号留言。

更多课程请打开“学思营”同步网站：

http://www.5xstar.com/doc.html

参考资料：

１、《Python算法图解》何韬编著　清华大学出版社