事业单位考试计算机基础知识：满二叉树知识点
满二叉树和完全二叉树是二叉树的两种特殊情形。满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。
满二叉树的特点：
每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。
例题
证明：对于任意满二叉树，其分枝数B=2(n0-1)，其中n0为叶子结点数。
【解答】因为在满二叉树中没有度为1的结点，所以有：n=n0+n2
设B为树中分枝数，则n=B+1所以
B=n0+n2-1
再由二叉树性质：n0=n2+1代入上式有：
B=n0+n0-1-1=2(n0-1)
页:
[1]