算法训练 求先序排列  
时间限制:1.0s   内存限制:256.0MB
      
锦囊1
  后序的最后一个字母为根结点。
 
问题描述
  给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度<=8)。
输入格式
  两行,每行一个字符串,分别表示中序和后序排列
输出格式
  一个字符串,表示所求先序排列

  样例输入
  BADC
  BDCA

样例输出
ABCD
 
作者注释:解此题,狠狠的复习了一把先、中、后序遍历二叉树。针对此题的笔记如下:
 
先序、中序、后序分别用pre、in、last数组表示。
  1、后序的最后一个节点必为根节点;
  2、在中序里由根节点可划分左右子树;
  3、根节点就是要往先序中填充的节点;
  4、递归左右子树。
 
递归体的四个参数:
  instart:中序起始位置;
  insend:中序终止位置;
  lastroot:后序根节点(即后序最后一个节点);
  preindex:欲填充的先序位置。
 
在中序中:
  左子树根节点 = 上一个后序根节点 - 右子树长度;
  右子树根节点 = 上一个后序根节点 - 1.
 
左子树根节点:
  lastroot - [(inend - i) + 1];
右子树根节点:
  lastroot - 1;
左子树的根节点插入先序中的位置:
  preindex + 1;
右子树的根节点插入先序中的位置:
  [(i - instart) + 1] + preindex;(其中i为中序中根节点的下标);
 
递归体:
  对于左子树:dfs(instart, i - 1, lastroot - [(inend - i) + 1], preindex + 1);
  对于右子树:dfs(i + 1, inend, lastroot - 1, preindex + [(i - instart) + 1]);
 
代码:
 /*
DEABFCHG
DEAFHGCB
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char pre[],in[],last[];//数组规模比预算稍微设置大一点
void dfs(int instart,int inend,int lastroot,int preindex){
if(instart>inend) return;//出口
for(int i=instart;i<=inend;i++){
if(in[i] == last[lastroot]){
pre[preindex] = in[i];
dfs(instart,i-,lastroot-(inend-i)-,preindex+);//左子树
dfs(i+,inend,lastroot-,preindex+(i-instart)+);//右子树
return;
}
}
}
int main(){
scanf("%s",&in);//录入中序,后序
getchar();//处理回车
scanf("%s",&last);
int leni = strlen(in);
int lenl = strlen(last);
dfs(,leni-,lenl-,);
printf("%s",pre);
return ;
}
05-01 04:47