计算机基础知识：二叉树的基本特性（1）

中公

2014公共基础知识题库|行政能力测试复习资料|2014年申论热点
【导语】在事业单位考试中，计算机专业知识的复习向来是考生复习备考阶段的一大重点，其中新都事业单位考试网为计算机基础知识的复习为考生提供知识点梳理，帮助考生备考!
性质1：
在二叉树的第i层上至多有2i-1个结点。(i≥1)
证明：用归纳法证明之
①i=1时，只有一个根结点，2i-1=20=1是对的;
②假设对所有j(1≤j[i]j-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）。
以上是新都事业单位考试网为考生梳理计算机基础知识点，供大家学习识记!
更多精彩内容，请访问事业单位招聘考试网！