数据结构2001

一． 输入一个正整数序列（53，17，12，66，58，70，87，25，56，60），。试完成下列

各题。

（1） 按次序构造一棵二叉排序BS。

（2） 依此二叉排序，如何得到一个从大到小的有序序列？ （3） 画出此二叉排序树中删除“66”后的树的结构。

二． 已知待排序的序列为（503，87，512，61，908，170，897，275，653，462），试

完成下列各题。

（1） 根据以上序列建立一个堆（画出第一步和最后堆的结果图），希望先输出最小值。 （2） 输出最小值后，如何得到次小值。（并画出相应结果图）

三． 下列是先序遍历二叉树的非递归子序，请阅读子程序C语言与PASCAL语言过程

功能完全相同，任选其一），填充空格，使其成为完整的算法。 C语言函数： Void example(b) Btree b; { btree*stack[20],*p int top; if (bl=null) { top=1; stack[top]=b; while (top>0) { p=stack[top]; top-; printf(“%d”,p->data); if (p->rchild!=null) { __________(1)____________; _______________(2)___________________; } if (p->lchild!=null) { __________(3)__________; _______________(4)_____________________; } } } } PASCAL语言过程

Procedure example(b:btree); Var stack:array[1..20] of btree; Top:integer; P:btree; Begin If b<>nil Then begin Top:=1; Stack[top]:=b; While top>0 do Begin P:=stack[top]; Top:=top-1; Write(p^.data); If p^.rchild<>nil then Begin __________(1)_____________; ___________(2)___________________; end; if p^,lch<>nil then begin _________(3)_____________; ____________(4)__________________; end; end; end; end;