先用归纳的方法找出完全二叉树中度为1的结点个数n与总结
点数N的关系。下面给出结点数N=1，2，3，4⋯的完全二叉树 如下图：
N=1 n1=0
N=1 n2=1
N=1 n3=0
N=1 n4=1
通过观察不难发现度为1的结点个数n1=0，1，0，1．． 即：当N为奇数时n1=0；当N为偶数时n1=1-------------------------------（1） 二叉树总结点数N可以表示为：N=n0+n1+n2------------------------------（2） 且N=二叉树分支数+1 二叉树分支数=0*n0+1*n1+2*n2， 故N=(0*n0+1*n1+2*n2)+1--------------------------------------------------------(3) 由(2)(3)式，可得：n0=n2+1-----------------------------------------------------(4) 由(2)(4)式，可得：N=n0+n1+(n0-1) ------------------------------------------(5) 综合(1)(5)，得如下结论： 当N为奇数时，N =n0+0+(n0-1)，n0=(N奇+1)/2；
[N/2]
[N/2]
N
[N-1]
N
N为偶数
N为奇数
谢
谢观看

(2) 其余结点分为不相交的两个子集： L——根的左子树 R——根的右子树 与一般树的不同： • 每个结点的度≤ 2； • 子树有左、右之分，不能互换
例如： B E L F A C G R
完全二叉树的定义
定义：二叉树中除最后一层外，其余层均满； 最后层或为满，或缺少右边若干连续结点： • 除最后一层，第 i层有2i-1个结点； • 叶子只可能出现在最后两层； • 若结点右子树深度为d ，左子树深度为d或 d+1 理想平衡树 ——除最后一层外，其余层满；最后一层点分 布任意；
当N为偶数时，N =n0+1+(n0-1)，n0=N偶/2。
思路2：
将完全二叉树的结点按层序(从上到下，从左到右)从1开始编号，
则N个结点的完全二叉树中，最后一个结点的编号为N。根据完 全二叉树的性质，编号为N的结点的父结点编号为[N/2]（[N/2] 表示的是N/2的整数部分） 如下图： 结论： 叶结点个数为总结点数减 去分支结点个数，而最后 结点的父结点为最末一个 分支结点，所以叶结点个 数n0=N-[N/2]。
1 1
2
4 5 6
3
7
2 4 5 6
3
满二叉树
完全二叉树
完全二叉树的性质
① 有n 个结点的完全二叉树， 其深度为：⌊log2n⌋+1 或为 ⌊log2(n+1)⌋ 证明：由性质2，若完全二叉树深度为h，应有：
(深度h-1的满二叉树结点数) < n ≤(深度h的满二叉树结点数)
即：2h-1-1 < n ≤ 2h-1 或： 2h-1≤ n < 2h ② 对完全二叉树中n个结点从上到下，每层从左到右
完全二叉树总结点数与叶结点数关 系分析
学号：140120010224
班级：软件工程八班
姓名：邢继芳
目录
1
二叉树的定义
2
3 4
完全二叉树的定义
完全二叉树的性质
问题分析
二叉树的定义
定义： 二叉树( Binary Tree)是 n (n ≥0)个结点的有限集，
它或为空，或满足： (1) 有一个特定的结点——根结点；
从0开始顺序编号，则有：
a. 若2i≤ n，则 i的左孩子序号为 2i，否则 i为叶子； b. 若2i+1≤ n，则 i的右孩子序号为 2i+1，否则 i无右孩子； c. 若结点编号 i >0，则其双亲序号为 ⌊i/2⌋。 d. 若结点编号 i =1，则结点i为二叉树的根，无双亲。
问题分析
思路1：