中科院研究生院2010年专业课数据结构复习资料

1. 试利用栈的基本操作写出二叉树后序遍历的非递归算法。

参考答案：

除了记录每次递归根结点的栈之外，还需要一个记录当前结点遍历状态的栈，如

果处于左子树遍历，状态为 0，否则状态变为 1。

StatusPostOrderTraverse(BiTreeT,Status(*Visit)(ElemTypee))

{

//采用二叉链表存储结构，Visit 是对数据元素操作的应用函数

InitStack(Sroot);

InitStack(Stag);

}else{

Pop(Stag,tag);

if(tag==0){

GetTop(Sroot,p);

Push(Stag,1);



p=p‐>rchild;

}else{

Pop(Sroot,p);

if(!Visit(p))returnERROR;

2.

画出和下列已知访问序列对应的树：

树的先根次序访问序列为：KIMCBDNFHJEALG；

树的后根次序访问序列为：MCIBNHFJDLAGEK。

参考答案：

I

B

E

3. 画出和下列已知访问序列对应的森林：

森林的先序次序访问序列为：JHEFIABLGCKD；

森林的中序次序访问序列为：HJIAFBLECDKG。

参考答案：

J

H

E

F

B L

I

A

G

C

参考答案：

5. 给出下图所示无向带权图，根据该图完成下列各题：

程中各步的状态。

B

5

6

2

1

8

D

1

A

2

D

3

2

1

C

E

1

3

2

C