满二叉树的特点如下：叶子结点都在最下一层。只有度为0和度为2的结点。含n个结点的满二叉树的高度为1og2(n+1)，叶子结点个数为Ln/2]+1度为2的结点个数为Ln/2]。n=15h=1og2(n+1)=4101415111312MA6/35
满二叉树的特点如下： 叶子结点都在最下一层。 只有度为0和度为2的结点。 含n个结点的满二叉树的高度为log2(n+1)，叶子结点个数为n/2+1， 度为2的结点个数为n/2。 A B D H I E J K C F L M G N O 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15 n=15 h=log2(n+1)=4 6/35
若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。同样可以对完全二叉树中每个结点进行层序编号，编号的方法同满二叉树相同，图中每个结点外边的数字为对该结点的编号。1011L7/35
若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下 面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉 树称为完全二叉树。 同样可以对完全二叉树中每个结点进行层序编号，编号的方法同满二 叉树相同，图中每个结点外边的数字为对该结点的编号。 A B D H I E J K C F G 1 2 4 8 9 5 10 11 3 6 7 7/35
完全二叉树的特点如下：叶子结点只可能出现在最下面两层中。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。如果有度为1的结点，只可能有一个，且该结点只有左孩子而无右孩子；按层序编号后，一旦出现某结点（其编号为）为叶子结点或只有左孩子则编号大于的结点均为叶子结点。108/35
完全二叉树的特点如下： 叶子结点只可能出现在最下面两层中。 对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。 如果有度为1的结点，只可能有一个，且该结点只有左孩子而无右孩子； 按层序编号后，一旦出现某结点（其编号为i）为叶子结点或只有左孩子， 则编号大于i的结点均为叶子结点。 A B D H I E J K C F G 1 2 4 8 9 5 10 11 3 6 7 8/35
二叉树性质7.2.2性质1非空二叉树上叶结点数等于双分支结点数加1。即ng=n2+1。证明：总结点数n=ne+ni+n2。一个度为1的结点贡献1个度，一个度为2的结点贡献2个度，所以总的度数=n1+2n2。总的度数=总分支数=n-1。则ni+2n2=ng+ni+n2-1,求出ng=n2+1。在二叉树中计算结点时常用的关系式有：①所有结点的度之和归纳=n-1②所有结点的度之和=n1+2n2③n=ne+ni+n2。9/35
性质1 非空二叉树上叶结点数等于双分支结点数加1。即n0=n2+1。 总结点数n=n0+n1+n2。 一个度为1的结点贡献1个度，一个度为2的结点贡献2个度， 所以总的度数=n1+2n2。 总的度数=总分支数=n-1。 则n1+2n2=n0+n1+n2-1，求出n0=n2+1。 证明： 在二叉树中计算结点时常用的关系式有：①所有结点的度之和 =n-1 ②所有结点的度之和＝n1＋2n2 ③n=n0+n1+n2。 归纳 9/35
性质2 非空二叉树上第i层上至多有2i-1个结点，这里应有≥1。由树的性质2可推出。性质3 高度为h的二叉树至多有2h-1个结点（h≥1）。由树的性质3可推出。18/35
性质2 非空二叉树上第i层上至多有2 i-1个结点，这里应有i≥1。 由树的性质2可推出。 性质3 高度为h的二叉树至多有2 h-1个结点（h≥1）。 由树的性质3可推出。 10/35