完全二叉树的叶子节点数公式
发布网友
发布时间：2024-09-05 11:06
共1个回答
热心网友
时间：2024-10-18 05:14
设叶子节点数为n0， 度为1的节点数为n1， 度为2的节点数为n2， 总节点为n
当n为奇数时 n0= (n+1)/2
当n为偶数 n0= n/2
证明
(度为2的节点有2个分支， 度为1结点有1个分支， 度为0的节点有0个分支)
总分支数=2*n2 + n1
另外分支数 = n0 + n1 + n2 - 1 (每个结点上面对应一个分支，除了根节点上面没有分支)
因此 2*n2 + n1 = n0 + n1 + n2 - 1 得 n0 = n2 + 1
假设n为完全二叉树的结点总数， 则有 n=n0+n1+n2(公式2)
结合公式 1和2 有 n0=(n-n1+1)/2
又因为 n1 = 0 或者 n1 = 1 只有这两种情况(完全二叉树的性质呀--只有一个分支的节点要么有， 要么没有， 剩下的全是两个分支的节点和0分支的叶子节点)
当n为奇数时(即度为1的节点为0个) n0= (n+1)/2
当n为偶数(即度为1的节点为1个) n0= n/2
n1，n2，都可以求了吧。
特殊类型
1、满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
2、完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。
3、完全二叉树的特点是叶子结点只可能出现在层序最大的两层上，并且某个结点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。
相关术语
1、结点：包含一个数据元素及若干指向子树分支的信息。
2、结点的度：一个结点拥有子树的数目称为结点的度。
3、叶子结点：也称为终端结点，没有子树的结点或者度为零的结点。
4、结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层。
5、树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度。
