第六节 根据两种遍历顺序确定树结构

procedure solve1(s1，s2:string)； { 计算和输出中序遍历s1和后序遍历s2对应的前序遍历}
var
  k:integer；
begin
  if length(s2)=1   {若当前子树仅剩一个节点，则输出}
     then write(s2)
     else begin
           k:=pos(s2[length(s2)]，s1)；{在中序遍历中寻找子树根}
           write(s1[k])；
           if k>1            {若左子树存在，则递归遍历左子树}
              then solve1(copy(s1，1，k-1)，copy(s2，1，k-1))；
           if k<length(s1)   { 若右子树存在，则递归遍历右子树}
              then solve1(copy(s1，k+1，length(s1)-k)，copy(s2，k，length(s2)-k))；
          end；
end;

procedure solve2(s1，s2:string)；{计算和输出中序遍历s1和前序遍历s2对应的后序遍历}
var
   k:integer；
begin
   if length(s2)=1   {若当前子树仅剩一个节点，则输出}
      then write(s2)
      else begin
            k:=pos(s2[1]，s1)；  {在中序遍历中寻找子树根}
            if k>1        {若左子树存在，则递归遍历左子树}
               then solve2(copy(s1，1，k-1)，copy(s2，2，k-1))；
            if k<length(s1) { 若右子树存在，则递归遍历右子树}
            then solve2(copy(s1，k+1，length(s1)-k)，copy(s2，k+1，length(s2)-k))；
          end；
    write(s1[k])；{或者输出子树根s2[1]}
end;