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

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

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

　　TYPE pointer=^tnodetp;　　tnodetp=RECORD data: char; llink rlink: pointer END;　　linkstack=^linknodet;　　linknodet=RECORD data:pointer next;linkstack END;　　PROC unknown (VAR t:pointer);　　VAR  p temp pointer;　　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  p temp: 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; 【北方交通大学 三 ( 分)】