满二叉树

定义

在一棵二叉树中，如果所有分支结点都有左、右孩子结点，并且叶子结点都集中在二叉树的最下层，这样的二叉树称为满二叉树。如下图所示就是一棵满二叉树。
用户可以对满二叉树的结点进行层序编号，约定编号从树根为1开始，按照层数从小到大、同一层从左到右的次序进行，图中每个结点旁的数字为对该结点的编号。
满二叉树也可以从结点个数和树的高度之间的关系来定义，即一棵高度为h且有2^h-1个结点的二叉树称为满二叉树。

特点

①、叶子结点都在最下一层
②、只有度为0和度为2的结点
③、含n个结点的满二叉树的高度为log₂(n+1)，叶子结点个数为⌊ $\frac{n}{2}$⌋+1,
度为2的结点个数为⌊ $\frac{n}{2}$⌋

完全二叉树

定义

若二叉树中最多只有最下面两层的结点的度可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。如下图所示为一棵完全二叉树。同样可以对完全二叉树中的每个结点进行层序编号，编号的方法与满二叉树相同，图中每个结点旁的数字为该结点的编号。

满二叉树是完全二叉树的一种特例，并且完全二叉树与同高度的满二叉树对应结点的层序编号相同。上图所示的完全二叉树与等高度的满二叉树相比，它在最后一层的右边缺少了4个结点。

特点

①、叶子结点只可能出现在最下面两层中。
②、最下一层中的叶子结点都依次排列在该层最左边的位置上
③、如果有度为1的结点，只可能有一个，且该结点最多只有左孩子而无右孩子
④、按层序编号后，一旦出现某结点（其编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点。
补充性质:
一、对完全二叉树中层序编号为i的结点（1≤i≤n，n≥1，n为结点总数）有：
①、若i≤⌊$\frac{n}{2}$⌋，即2i≤n，则编号为i的结点为分支结点，否则为叶子结点。
②、若n为奇数，单分支结点（度为1的结点）个数为0个，这棵树上的每个分支结点都是双分支结点，下图就是这种情况，其中n=11，分支结点1~5都是双分支结点，其它为叶子结点

③、若n为偶数，则单分支结点个数为1个，该单分支结点是编号最大的分支结点，编号为⌊ $\frac{n}{2}$⌋。
④、若编号为 i 的结点有左孩子结点，则左孩子的编号为 2i；若编号为 i的结点有右孩子结点，则右孩子的编号为 2i+1；若编号为 i的结点有双亲结点，其双亲结点的编号为⌊ $\frac{i}{2}$⌋。
二、具有n个（n>0）结点的完全二叉树的高度为⌈log₂(n+1)⌉或⌊log₂ n⌋+1=0

例题

一棵完全二叉树中有501个叶子结点，则至少有（）个结点。
A. 501
B. 502
C. 1001
D. 1002
解析：解这个题要知道二叉树的一个性质：非空二叉树上叶子结点数等于双分支节点数+1。由这个性质可以知道当叶子结点等于501时，双分支结点等于501-1=500。对于完全二叉树而言，它的单分支结点如果存在那么单分支结点数等于1，如果不存在那么单分支结点数等于0。这里由于题目问的是至少有多少个结点，那么应该取单分支结点数为0的情况。所以总结点数=叶子结点数+单分支结点数+双分支结点数=501+0+500=1001。所以答案选C。

一棵完全二叉树中有501个叶子结点，则至多有（）个结点。
A. 501
B. 502
C. 1001
D. 1002
解析：解这个题要知道二叉树的一个性质：非空二叉树上叶子结点数等于双分支节点数+1。由这个性质可以知道当叶子结点等于501时，双分支结点等于501-1=500。对于完全二叉树而言，它的单分支结点如果存在那么单分支结点数等于1，如果不存在那么单分支结点数等于0。这里由于题目问的是至多有多少个结点，那么应该取单分支结点数为1的情况。所以总结点数=叶子结点数+单分支结点数+双分支结点数=501+1+500=1001。所以答案选D。

一棵满二叉树共有64个叶子结点，则其结点个数为（）。
A. 64
B. 65
C. 127
D. 128
解析：根据二叉树的性质，即非空二叉树上叶子结点数等于双分支节点数+1，可以求出：双分支节点=叶子节点-1=64-1=63。又由满二叉树只有度为0和度为2的结点，可知该满二叉树的结点个数为：叶子结点数+双分支结点数=64+63=127。选C

一棵满二叉树中127个结点，其中叶子结点的个数是（）。
A. 63
B. 64
C. 65
D. 不确定
解析：满二叉树中只有度为0和度为2的结点，将度为2的结点表示为n₂，度为0的结点表示为n₀，总结点数表示为n，可知n=n₀+n₂ ， 由二叉树的性质：非空二叉树上叶子结点数(n₀)等于双分支节点数(n₂)+1，可知n₀=n₂+1。综合两个等式 n=n₀+n₂和n₀=n₂+1得出：127=n₀+n₂和n₀=n₂+1。解二元一次方程，最终解得：n₀=64。选B

一棵满二叉树共有64个叶子结点，则其结点个数为（）。
A. 64
B. 65
C. 127
D. 128
解析：满二叉树中只有度为0和度为2的结点，将度为2的结点表示为n₂，度为0的结点表示为n₀，总结点数表示为n，可知n=n₀+n₂ ， 由二叉树的性质：非空二叉树上叶子结点数(n₀)等于双分支节点数(n₂)+1，可知n₀=n₂+1。综合两个等式 n=n₀+n₂和n₀=n₂+1得出：n=64+n₂和64=n₂+1。解二元一次方程，最终解得：n=127。选C

今天的文章满二叉树与完全二叉树的区别_完全二叉树的实现方法分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。