高校问答一人我骂马蓉:二叉树的处理(Pascal或C均可,使用字符串处理)
来源：百度文库 编辑：高校问答 时间：2024/05/03 03:39:20
假定一棵二叉树一个结点用一个字符描述，现在给出中序和按层遍历的字符串，求该树的先序遍历字符串。
【输入】
输入文件flist.in共两行，每行是由字母组成的字符串（一行的每个字符都是唯一的），分别表示二叉树的中序遍历和按层遍历的序列。
【输出】
输出文件flist.out就一行，表示二叉树的先序序列。
【样例】
flist.in
DBEAC
ABCDE
flist.out
ABDEC
请不要乱回答案........
var q,zh,h,g,z,y:string[8];
function getroot(p:string[8]):string[8]; {根据中序和后序确定当前处理树的根}
var i,j:byte;fin,fout:text;
begin
if length(p)=1 then begin getroot:=p; exit end
else begin
for i:=length(h) downto 1 do
for j:=1 to length(p) do
if h[i]=p[j] then begin
getroot:=h[i];
exit;
end;
end;
end;
procedure work(g,z,y:string[8]);
var root,left,right:string[8];
begin
write(fout,g);{第一步：输出根}
if length(z)-1>0 then begin
root:=getroot(z);
left:=copy(z,1,pos(root,z)-1);
right:=copy(z,pos(root,z)+1,length(z)-pos(root,z));
work(root,left,right); {第二步：递归处理左子树}
end else write(fout,z);
if length(y)-1>0 then begin
root:=getroot(y);
left:=copy(y,1,pos(root,y)-1);
right:=copy(y,pos(root,y)+1,length(y)-pos(root,y));
work(root,left,right);{第三步：递归处理右子树}
end else write(fout,y);
end;
begin
assign(fin,'first.in');
assign(fout,'first.out');
reset(fin);
rewrite(fout);
readln(fin,zh);
readln(fin,h);
g:=getroot(zh);
z:=copy(zh,1,pos(g,zh)-1);
y:=copy(zh,pos(g,zh)+1,length(zh)-pos(g,zh));
work(g,z,y);
readln;
close(fin);
close(fout);
end.