完全二叉树和满二叉树的区别

谁借莪１个温暖的怀抱￠ 2022-07-31 16:05 222阅读 0赞

堆的话一般都是用完全二叉树来实现的，比如大堆和小堆。一个树节点的度数就是这个树节点有多少子节点，和树的深度意义不同。

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适

![Center][]

完全二叉树是效率很高的数据结构，[堆][Link 1]是一种完全二叉树或者近似完全二叉树，所以效率极高，像十分常用的[排序][Link 2]算法、[Dijkstra][]算法、[Prim][]算法等都要用堆才能优化，几乎每次都要考到的[二叉排序树][Link 3]的效率也要借助[平衡][Link 4]性来提高，而平衡性基于完全二叉树。

完全二叉树(Complete Binary Tree)

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

完全二叉树是由 [满二叉树][Link 5]而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。

##       完全二叉树特点[编辑][Link 6] ##

[叶子结点][Link 7]只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1；

出于简便起见,完全二叉树通常采用 [数组][Link 8]而不是 [链表][Link 9]存储,其 [存储结构][Link 10]如下:

var tree:array\[1..n\]of longint;\{n:integer;n>=1\}

对于tree\[i\] *，*有如下特点：

（1）若i为奇数且i>1，那么tree的左兄弟为tree\[i-1\]；

（2）若i为偶数且i<n，那么tree的右兄弟为tree\[i+1\]；

（3）若i>1，tree的双亲为tree\[i div 2\]；

（4）若2\*i<=n，那么tree的左孩子为tree\[2\*i\]；若2\*i+1<=n，那么tree的右孩子为tree\[2\*i+1\]；

（5）若i>n div 2,那么tree\[i\]为 [叶子结点][Link 7]（对应于（3））；

（6）若i<(n-1) div 2.那么tree\[i\]必有两个孩子（对应于（4））。

（7） [满二叉树][Link 5]一定是完全二叉树，完全二叉树不一定是满二叉树。

完全二叉树第i层至多有2^（i-1）个 [节点][Link 11]，共i层的完全二叉树最多有2^i-1个节点。

如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的 [满二叉树][Link 5]中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。

可以根据公式进行推导，假设n0是度为0的结点总数（即 [叶子结点][Link 7]数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0=n2+1，则n= n0+n1+n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=(n+1)/2或n0=n/2。

总结起来，就是 n0=\[n/2\]，其中\[\]表示上取整。可根据完全二叉树的结点总数计算出叶子结点数。

其实满二叉树是完全二叉树的特例，因为满二叉树已经满了，而完全并不代表满。所以形态你也应该想象出来了吧，满指的是出了叶子节点外每个节点都有两个孩子，而完全的含义则是最后一层没有满，并没有满。

下面贴定义：

满二叉树(Full Binary Tree)：

[  ][Link 12] [![3c6d55fbb2fb4316076b82d120a4462309f7d321.jpg][]][Link 12]

除最后一层无任何子 [节点][Link 11] 外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为 [叶子结点][Link 7] ）。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上.

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

它的叶子数是： 2^h

第k层的结点数是： 2^(k-1)

总结点数是： 2^k-1 (2的k次方减一)

总节点数一定是奇数。

完全二叉树(Complete Binary Tree)

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

完全二叉树是由 [满二叉树][Link 5] 而引出来的。对于深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

若一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。

[  ][Link 13]

![Center 1][]

霍夫曼树：每个节点要吗没有子节点，要么有两个子节点

[Center]: /images/20220801/39fbe7eb0ac647368bef757b25b158f4.png
[Link 1]: http://baike.baidu.com/view/249120.htm
[Link 2]: http://baike.baidu.com/view/58783.htm
[Dijkstra]: http://baike.baidu.com/view/809651.htm
[Prim]: http://baike.baidu.com/view/580409.htm
[Link 3]: http://baike.baidu.com/view/647462.htm
[Link 4]: http://baike.baidu.com/view/84756.htm
[Link 5]: http://baike.baidu.com/view/427110.htm
[Link 6]: http://baike.baidu.com/link?url=MPk8rLiVZQWH9YAnLuHHm5bPvKCGNXm1NahI3N8L9WNgxPKAuyk7dBxtn9rwhabfCZTaC0XIjAfc9BTtbvU8s_#
[Link 7]: http://baike.baidu.com/view/2335663.htm
[Link 8]: http://baike.baidu.com/view/209670.htm
[Link 9]: http://baike.baidu.com/view/549479.htm
[Link 10]: http://baike.baidu.com/view/2820182.htm
[Link 11]: http://baike.baidu.com/view/47398.htm
[Link 12]: http://baike.baidu.com/albums/427110/427110/0/0.html#0$3c6d55fbb2fb4316076b82d120a4462309f7d321
[3c6d55fbb2fb4316076b82d120a4462309f7d321.jpg]: /images/20220801/79e08feeb97b4be49c8ec1297cd55235.png
[Link 13]: http://baike.baidu.com/albums/427107/427107/0/0.html#0$b151f8198618367a6f44126e2e738bd4b21ce5b0
[Center 1]: /images/20220801/b3195775a10d494387050bbb30e86368.png