数据结构考研分类复习真题 第六章 树和二叉树 (三)[17]

数据结构考研分类复习真题 第六章 树和二叉树 (三)[17]  

　　 ．下述是一个由二叉树的前序序列和中序序列构造该二叉树的算法 其中 数组A[ n]存放前序序列 数组B[ n]存放中序序列 s为根结点指针 i j为树s的前序序列在A[ n]中的开始位置和结束位置 x y为树s的中序序列在B[ n]中的开始位置和结束位置 所生成的二叉树采用二叉链表存储结构 其结点的形式为(lchild data rchild) 请在算法的空框中填入适当语句 使其成为一个完整的算法

　　PROCEDURE creatBT(i j x y: integer; VAR s: link);　　VAR  k L: integer;　　BEGIN s:= NIL;　　IF( )_____THEN　　BEGIN new (s); s^ data:=a[i]; k:=x;　　WHILE( )_______DO  k:=k+ ;　　L:= ( )_______;　　IF k=x THEN s^ lchild:=NIL; ELSE( )_______;　　IF k=y THEN s^ rchild:=NIL; ELSE( )_______ 　　END　　END;【西安交通大学 五 ( 分)】

　　 ．已知中序遍历bt所指二叉树算法如下 s为存储二叉树结点指针的工作栈 请在划线处填入一条所缺语句

　　PROC inorder (bt:bitreptr);　　inistack(s); ( )_______;　　WHILE NOT empty(s)  DO　　[WHILE gettop(s)<>NIL DO push(s gettop(s)↑ lchild);  ( )_______;　　IF NOT empty(s) THEN  [visit (gettop(s)^); p:=pop(s); ( )_______ ] ]　　ENDP;{inorder}【北京轻工业学院 一 ( 分)】