一、为什么说“满二叉树也是完全二叉树”

因为国内早期教材中，满二叉树一般指 perfect binary tree，所以会有满二叉树是完全二叉树的一个特例的说法。类似的情况可能还有树的深度的定义，有的根结点从0开始计数，有的从1开始计数。

满二叉树(Full Binary Tree):

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

一颗树深度为h，最大层数为k，深度与最大层数相同，k=h;

它的叶子数是： 2^h　　第k层的结点数是： 2^(k-1)　　总结点数是： 2^k-1 (2的k次方减一)　　总节点数一定是奇数。

                                             0

                                     /               \

                                  1                   2

                              /      \            /       \

                            3        4         5           6

                          /  \    /   \     /    \       /   \

                        7    8  9     10  11     12    13     14

完全二叉树(Complete Binary Tree):

完全二叉树：完全二叉树的节点数是任意的，从形式上讲它是个缺失的的三角形，但所缺失的部分一定是右下角某个连续的部

分，最后那一行可能不是完整的，对于k层的完全二叉树，节点数的范围2^ (k – 1) -1 < N< 2^k – 1;

设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，

这就是完全二叉树。

                                              0

                                     /               \

                                  1                   2

                              /      \            /       \

                            3        4         5           6

                          /  \    /   \     /   

                        7    8  9     10  11

延伸阅读：

二、完全二叉树判定

1>如果树为空，则直接返回错

2>如果树不为空：层序遍历二叉树

2.1>如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；

2.1>如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；

2.2>如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空，且则该节点之后的队列中的结点都为叶子节点，该树才是完全二叉树，否则就不是完全二叉树。

上一篇

C无锁(lockfree)数据结构与有锁数据结构相比，速度，性能等有何区别?

下一篇

为什么C#的.NET库不默认提供「优先队列」容器?