事业单位考试计算机基础知识：满二叉树知识点

事业单位招聘网

满二叉树和完全二叉树是二叉树的两种特殊情形。
    满二叉树：一棵深度为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)