二叉树和完全二叉树的二叉树定义特征完全二叉树定义特征例题
二叉树的定义
对于一棵二叉树，如果所有分支节点都有左、右孩子的节点，并且叶节点聚集在二叉树的最底层，则该二叉树被称为满二叉树。 如下图所示，被二叉树覆盖。
用户可以对充满二叉树的节点进行层序编号，承诺编号从树根1开始，按照层数从小到大、同层从左到右的顺序进行，图中各节点旁边的数字是该节点的编号。
二叉树也可以根据节点的数量和树的高度的关系来定义，可以从一棵高度为h且有2h-1个结点的二叉树称为满二叉树。
特点、叶子结点都在最下一层
、只有度为0和度为2的结点
、包含n个节点的二叉树的高度为log2(n1 )，叶的节点数为n2(n ) (over ) 2n1。
度2的节点数为N2 {2}over 2n
完全二叉树的定义在二叉树中，最大只有最下面的2段节点的度可以小于2，如果最下面的段的叶节点按顺序排列在该段的最左边的位置，则将这样的二叉树称为完全二叉树。 下图是完全二叉树。 同样可以对完全二叉树的各节点进行层序编号。 编号方法与完全二叉树相同，图中各节点旁边的数字是该节点的编号。
二叉树是完全二叉树的一个特殊例子，完全二叉树与同高度二叉树对应节点的层序号相同。 上图所示的完全二叉树与等高二叉树相比，在最下段的右侧缺少4个节点。
特征、叶片节点只出现在最底层的二层。
、最底层叶片节点均按顺序排列在该层最左边位置
、如果有度1的节点，则可能只有一个，该节点最多只能有左孩子，没有右孩子
、按层序编号后，若某节点(编号为I )为叶节点或仅为左子时，编号大于I的节点均为叶节点。
补充性质：
一、对完全二叉树中层序编号为i的结点（1in，n1，n为结点总数）有：
、如果In2{n}over{2}2n，即2in，则编号I的节点为分支节点，否则为叶节点。
、当n为奇数时，单分支节点(度为1的节点)个数为0，该树各分支节点均为双分支节点。 下图就是这种情况。 这里，n=11，分支节点1~5都是双重分支节点，其他是叶节点
、n为偶数时，单分支节点数为1个。 该单分支节点是编号最大的分支节点，编号为 n 2 {n} over {2} 2n 。
、如果编号为i的节点有左子节点，则左子的编号为2i； 如果右边孩子的节点位于编号i的节点中，则右边孩子的编号为2i+1； 如果父母存在于编号为i的节点中，则父母节点的编号为 i 2 {i} over {2} 2i 。
二、具有n个（n0）结点的完全二叉树的高度为log2(n+1)或log2 n+1=0
例题1棵完全二叉树中如果有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的结点表示为n2，度为0的结点表示为n0，总结点数表示为n，可知n=n0+n2 ， 由二叉树的性质：非空二叉树上叶子结点数(n0)等于双分支节点数(n2)+1，可知n0=n2+1。综合两个等式 n=n0+n2和n0=n2+1得出：127=n0+n2和n0=n2+1。解二元一次方程，最终解得：n0=64。选B
一棵满二叉树共有64个叶子结点，则其结点个数为（）。
A. 64
B. 65
C. 127
D. 128
解析：满二叉树中只有度为0和度为2的结点，将度为2的结点表示为n2，度为0的结点表示为n0，总结点数表示为n，可知n=n0+n2 ， 由二叉树的性质：非空二叉树上叶子结点数(n0)等于双分支节点数(n2)+1，可知n0=n2+1。综合两个等式 n=n0+n2和n0=n2+1得出：n=64+n2和64=n2+1。解二元一次方程，最终解得：n=127。选C