2001年NOIP普及组] 求先序排列

2001年NOIP普及组] 求先序排列

• 分析：根据题意，已知中序遍历和后序遍历求先序遍历，很显然是用递归求解。我们知道后序遍历中根节点是最后一个，所以可以首先确定根节点的位置，然后通过根节点找中序遍历中的根节点，根据中序遍历就可以确定左子树和右子树节点的个数，再看是否有左子树和右子树，如果有用递归继续往下寻找，依此类推，直到全部遍历完。要注意的一点序列长度区间是左闭右开。

• #include<iostream>
  #include<cstdio>
  #include<cstring>
  using namespace std;
  char b[10],c[10];
  int len;
  void work(int bl,int br,int cl,int cr)
  {
  cout<<c[cr-1];//打印根节点 左闭右开
  int bk;//中序遍历中根节点的位置
  for(int i=bl;i<br;i++)//左闭右开
  {
  if(b[i]==c[cr-1])//中序遍历根节点
  {
  bk=i;
  break;
  }
  }
  int ln=bk-bl;//左子树的节点个数
  int rn=br-1-bk;//右子树节点个数 （左闭右开）
  if(ln>0)//有左子树
  {
  work(bl,bl+ln,cl,cl+ln);//先中序 再后序
  }
  if(rn>0)//有右子树
  {
  work(bk+1,bk+1+rn,cr-1-rn,cr-1);//先中序 再后序
  } //（左边取得到 右边取不到）
  return ;
  }
  int main()
  {
  cin>>b>>c;
  len=strlen(b);//求长度 b c长度一样求谁都行
  work(0,len,0,len);//中序[0,len] 后序[0,len] 区间！！
  return 0;
  }