计算机公共基础2.doc

顶
1

2

4

2
5

6

1

底
6

1

队尾

2

1
队头

1. 树
l 基本术语
① 根结点：没有前件的结点，只有一个。如结点A
② 叶子结点：没有后件的结点。如结点C、D、E、F
③ 结点的度：一个结点所拥有的后件个数。如结点B的度为3，叶子结点D的度为0
④ 树的度：所有结点中的最大的度。如下图所示的树的度为3
⑤ 树的深度：树的最大层次。如下图所示的树的深度为3
F
E
D
C
B
A

前序ABDECF 中序 DBEAFC 后序 DEBFCA
2. 二叉树
l 特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
l 基本性质：
（1）在二叉树的第k层上，最多有2k-1(k≥1)个结点；
（2）深度为m的二叉树最多有2m-1个结点；
1+2+4+8+-----+2m-1 1(1-2m)/(1-2)=
（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；
n0 + n1+n2=0*n0 + 1*n1 +2*n2+1
n0=n2+1
例1：（2011-3-03）某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为(假设根结点在第1层) （Ｄ）
A)3 　 B)4 　　　 C)6 D)7
【解析】二叉树性质3：度为0的结点个数总比度为2的结点多一个。叶子结点只有1个，所以度为2的结点没有，即度为1的结点6个，深度为7，所以选D。
例2：（2010-9-03）一棵二叉树有10个度为1的结点，7个度为2的结点，则该二叉树共有 25 个结点。
【解析】该二叉树中的叶子结点数为7+1=8个，度为1、2、0的结点数分别为10、7、8，则结点总数为10+7+8=25。
（4）具有n个结点的二叉树，其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分；2m-1=n
l 满二叉树：指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。
l 完全二叉树：指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。具有n个结点的完全二叉树的深度为[log2n]+1。
l 二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。
3. 二叉树的遍历
l 前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树
l 中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树
l 后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点

例1：（2011-3-02）一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为 DEBFCA 。
D
C
B
A

F
E

【解析】根据前序遍历结果可知：A为根节点，B为A的左子树，根据中序遍历结果可知：D为B的左子树，E是B的右子树，F、C是A的右子树，结合前序遍历结果可知，C是A的右子树，F是C的左子树。故后序遍历为DEBFCA。
4．E-R图表示实体、属性和实体之间的联系。
Sno
Ssex
Cno
Cname
Sname
SC
student
course

用矩形表示实体集，如实体集学生（student）、课程（course）。
用椭圆形表示属性，如学生有属性：学号（Sno）、姓名（Sname）、性别(Ssex)。
用菱形表示联系，如学生与课程间的联系SC。
5. 关系运算