pascal二叉树遍历问题

来源:百度知道 编辑:UC知道 时间:2024/05/22 14:41:08
已知二叉树的前序与中序遍历,求后序遍历用,请pascal语言。

var sx,sz:string; {算法}
procedure work(sx,sz:string);{sx:先序序列; sz:中序序列}
var l,k:integer;
begin
if sx<>'' then
begin
l:=length(sx);
k:=pos(sx[1],sz); {根在中序序列中的位置}
work(copy(sx,2,k-1),copy(sz,1,k-1)); {递归调用左子树}
work(copy(sx,k+1,l-k),copy(sz,k+1,l-k)); {递归调用右子树}
write(sx[1]); {后序输出根结点}
end;
end;
begin
readln(sx);
readln(sz);
work(sx,sz);
writeln;
end.

我就偷懒一下,求后序遍历
用 Noip2008 阅读程序第4题的原题:

procedure solve
(first:string;spos_f,epos_f:integer;mid:string;spos_m,epos_m:integer);
var i,root_m:integer;
begin
if spos_f > epos_f then exit;
for i:=spos_m to epos_m do
if first[spos_f]=mid[i] then begin
root_m:=i; break; end;
solve(first,spos_f+1,spos_f+(root_m-spos_m),mid,spos_m,root_m-1);

solve(first,spos_f+(root_m-spos_m)+1,epos_f