满二叉树

　　一个二叉树，如果每一个层的节点数都达到最大值，即所有内部节点都有两个子节点·最底一层是叶子节点，则这个二叉树就是满二叉树。也可以这样定义：除了叶子节点外每一个节点都有左右子树，且叶子节点都处在最底层的二叉树。一般地，把满二叉树的拓扑图画成等腰三角形，如下图所示。

　　我们知道拓扑图是可以变形而不影响它表达的内容，下面的拓扑图也可以表示满二叉树。

　　根据满二叉树的定义，除了叶子外，其它节点都有左右树，也就是说，它的直接后继是它的2倍。根据树的子树不相交的特性，可得满二叉树相邻层之间的数量关系：

节点数＝２×上一层节点数。

可见，满二叉树节点数是倍增数列：

1,2,4,8,16,32,...。

　　满二叉树有以下特性：

　　①深度和最大层数相同，设为h；

　　②叶子数是2^(h-1)；

　　③第k层的节点数是2^(k一1)；

　　④总节点数是2^h-1(2的h次方减1)；

　　⑤总节点数一定是奇数；

　　⑥树高h=log2(n+1)（n是节点总数）。

　　满二叉树的常用方法包括：添加、遍历、查找、删除等，查找和删除方法与二叉排序树方法接近，只不过多了一个为空判断。

　　满二叉树的构建

　　满二叉树与二叉排序树的区别在于：如果添加的新节点在新的一层上，就必须把本层的其他叶子节点全部添加完全。即：用空节点填充其余叶子节点。在遍历时，也需要判断节点是有数据的节点还是空节点。

　　程序算法分析如下：

　　(1)添加：按二叉排序树的查找顺序，加一个判空条件。如果发现节点为空，直接将数据覆盖即可。如果需要添加新的叶子节点，则需要将整层叶子节点添加完全。满二叉树中添加新节点的算法图解如下图所示。

　　(2)遍历：遍历方式类似于二叉排序树，只是要加一个节点是否为空的判断。

　　程序代码：

　　运行结果：

　　练习１：把按层遍历添加到上例中，测试。

　　判断一棵二叉树是不是满二叉树

　　解题思路分析：满二叉树的每一层的节点数必须是2^(k一1)个节点(k是层数)，如下图所示。

　　可见，这是满二叉树的必要条件；又由于2^(k-1)=2×2^(k-2)（k>1），即下一层的节点数是上一层节点数的2倍，得非叶子节点都有左右子树。因此判断是否是满二叉树的算法逻辑可采用层节点计数的方式，把每层节点计数，如果有任一层节点数小于2(k一1)个节点，此树就不是满二叉树，否则就是满二又树。以下图

所示的二叉排序树作为判断树形，用程序判断这是否是一棵满二又树。为了更加直观，使用按层遍历显示。

　　程序代码：

　　运行结果：

　　递归解题思路：满二叉树的所有叶子节点左右子树都无并且在同一层，其它节点左右子树都有。用一递归函数，输入根节点和深度1，运行后就可以判定二叉树是不是满二叉树。

　　程序代码：

　　运行结果：

　　练习２：满二叉树的最大深度和最小深度相等，并等于层数n，节点总数是2^n-1。用求最大深度和最小深度的方法编程判定上例。

　　满二叉树的节点删除

　　满二叉树的节点删除方法与二叉排序树的节点删除差不多，不同的地方是：满二叉树不能单个移除节点，只能在叶节点全部为空后才整层移除。

　　程序代码：

　　运行结果：

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

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

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

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

参考资料：

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