树的遍历(程序阅读题pascal)

来源:百度知道 编辑:UC知道 时间:2024/06/08 20:38:12
这是2008年noip初赛的一道程序阅读题,我看了答案了,知道是已知前序遍历和中序遍历,要求输出后序遍历,但我看不懂这个程序的过程,请高手帮忙解释一下。如果给出前序和中序,我可以用手工求出后序遍历。就是这个程序的代码看不懂。
先谢谢了~~~~
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,mid,root_m+1,epos_m);
write(first[spos_f]);
end;

var first,mid:string;
len:integer;
begin
readln(len);
readln(first);
readln(mid);
solve(first,1,len,mid,1,len);
writeln;
end.

输入:7
ABDCEGF
BDAGECF
输出:_________________________________

告诉你 我老师的说法:
先学几个单词:

1.root 根
2.middle 中间
3.first 先

再仔细看看,root_m spos_f 是缩写吧

其实有些阅读程序
尽量把代码转换成算法
没必要一步一步跟踪

还有你要多了解一下有关递归搜索的程序,
对你有帮助

1、先找到先序的第一个节点(A)一定是根节点
2、在中序中找到它(A)
因为中序遍历是左-根-右
所以中序遍历中A的左边一定属于A的左子树 也就是B和D
右边的属于右子树
再递归调用——重复第一步
(BD,BD)和(CEGF,GECF)

递归调用完以后直接打先序的第一个节点(A)就是后续了

太简单了!买一本""

告诉你 我老师的说法:
先学几个单词:

1.root 根
2.middle 中间
3.first 先

再仔细看看,root_m spos_f 是缩写吧

其实有些阅读程序
尽量把代码转换成算法
没必要一步一步跟踪

还有你要多了解一下有关递归搜索的程序,
对你有帮助

1、先找到先序的第一个节点(A)一定是根节点
2、在中序中找到它(A)
因为中序遍历是左-根-右
所以中序遍历中A的左边一定属于A的左子树 也就是B和D
右边的属于右子树
再递归调用——重复第一步
(BD,BD)和(CEGF,GECF)

递归调用完以后直接打先序的第一个节点(A)就是后续了

v