事业单位考试计算机基础知识：二叉树的基本特性(1)

事业单位招聘网

性质1：
    在二叉树的第i层上至多有2i-1个结点。(i≥1)
    证明：用归纳法证明之
    ①i=1时，只有一个根结点，2i-1=20=1是对的;
    ②假设对所有j(1≤jj-1个结点
    那么，第i-1层至多有2i-2个结点
    又二叉树每个结点的度至多为2
    所以第i层上最大结点数是第i-1层的2倍，即2×2i-2=2i-1
    故命题得证
    例题
    试求有n个叶结点的非满的完全二叉树的高度?
    【解析】设完全二叉树中叶子结点数为n，则根据完全二叉树的性质，度为2的结点数是n-1，而完全二叉树中，度为1的结点数至多为1，所以具有n个叶子结点的完全二叉树结点数是n+(n-1)+1=2n或2n-1(有或无度为1的结点)。由于具有2n(或2n-1)个结点的完全二叉树的深度是
[log2(2n)]+1([log2(2n-1)]+1，即[log2n]+1,故n个叶结点的非满的完全二叉树的高度是[log2n]+1。(最下层结点数>=2)。