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

．下面使用类pascal语言写的对二叉树进行操作的算法请仔细阅读

TYPE pointer=^tnodetp;

tnodetp=RECORD data: char; llinkrlink: pointerEND;

linkstack=^linknodet;

linknodet=RECORD data:pointer next;linkstackEND;

PROC unknown (VAR t:pointer);

VAR ptemppointer;

BEGIN p:=t;

IF p<> NIL THEN

[temp:=p^llink p^llink:=p^rlink;p^rlink:=temp;

unknown(p^llink); unknown(p^rlink); ]

END;

① 指出该算法完成了什么功能

② 用栈将以上算法改为非递归算法unknown其中有若干语句或条件空缺请在空缺处填写上适当的语句或条件

PROC inistack(VAR s:linkstack);

()_______; s^next:=NIL;

ENDP;

FUNC empty (s:linkstack):boolean;

IF ()_______THEN empty:=true ELSE empty:=false;

ENDF;

FUNC gettop(s:linkstack):pointer;

gettop:= ()_______;

ENDF;

FUNC pop(VAR s:linkstack)pointer;

VAR p:linkstack;

pop:=s^next^data; p:=s^next; ()_______()_______;

ENDF;

PROC push (VAR s:linkstack;x:pointer);

VAR p:linkstack;

new(p); p^data:=x; ()_______; s^next:=p;

ENDP;

PROC unknown(VAR t:pointer);

VAR ptemp: pointer; finish: boolean;

BEGIN

inistack(s); finish:=false; p:=t;

REPEAT

WHILE p<> NIL DO

[temp:=p^llink; p^llink:=p^rlink; p^rlink:=temp;

()_______; p:=p^llink;];

IF ()_______THEN [p:=gettop(s);temp;=pop(s);] ELSE ()_______

UNTIL ()______

ENDP; 【北方交通大学 三 (分)】

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