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

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

PROCEDURE creatBT(ijxy: integer; VAR s: link);

VAR kL: 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(sgettop(s)↑lchild); ()_______;

IF NOT empty(s) THEN [visit (gettop(s)^); p:=pop(s); ()_______ ] ]

ENDP;{inorder}【北京轻工业学院 一 (分)】

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []