2011年计算机二级考试公共基础知识冲刺复习笔记（19）

文章作者 100test 发表时间 2011:03:18 18:47:56
来源 100Test.Com百考试题网

　　Point5：二叉树

　　出题趋势

考试日期	05-4	05-9	06-4	06-9	07-3	07-9	08-4	08-9	09-3	09-9	10-3	10-9
出题次数	1	1	2	1	3	2	1	1	1	1	1	1

　　考点精讲

　　1、树

　　树是一种简单的非线性结构，所有元素之间具有明显的层次特性。

　　在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后

　　-62-件的结点称为叶子结点。

　　在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。树的最大层次称为树的深度。

　　2、二叉树：度为2的树就是二叉树。

　　(1)二叉树的特点：①非空二叉树只有一个根结点；②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

　　3、二叉树的性质

　　(1)在二叉树中，第i层的结点总数不超过2i-1(i≥1)。

　　(2)深度为h的二叉树总计最多有2h-1个结点(h≥1)，最少有h个结点。

　　(3)对于任意一棵二叉树，如果其叶子结点数为N0，而度数为2的结点总数为N2，则N0=N2 1，即叶子数总比度为2的节点数多1。

　　(4)具有n个结点的完全二叉树的深度为int(log2n) 1。

　　(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：

　　若k为结点编号，则如果k