數據結構考研分類復習真題 第六章 樹和二叉樹 (三)[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; 【北方交通大學 三 (分)】

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23475.html