重建二叉树
时间限制：1000 ms | 内存限制：65535 KB
难度：3
描述
题目很简单，给你一棵二叉树的后序和中序序列，求出它的前序序列（So easy!）。
输入
输入有多组数据（少于100组），以文件结尾结束。
每组数据仅一行，包括两个字符串，中间用空格隔开，分别表示二叉树的后序和中序序列（字符串长度小于26，输入数据保证合法）。
输出
每组输出数据单独占一行，输出对应得先序序列。
样例输入
ACBFGED ABCDEFG
CDAB CBAD
样例输出
DBACEGF
BCAD
//从后序中找到根(最后一个结点)，然后确定根在中序中的位置，从而可以将中序序列分为左右子序列,后序中按此左序列的长度确定的序列即为后序左序列，
//后序中剩下的序列去掉根即为后序右序列,递归建树，然后NLR遍历
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct node{
char data;
struct node *lchild,*rchild;
}BitNode,*BiTree;
void GetPreorder(char *last,char *mid,BiTree &T,int len)
{
if(!len)
{
T = NULL;
return;
}
char ch = last[len-];//得到根结点
int index = ;//索引记录根结点在中序中的位置
while(mid[index] != ch) index ++;
T = (BiTree)malloc(sizeof(BitNode));//为根结点开辟空间
T->data = ch;
//递归建立左子树和右子树
GetPreorder(last,mid,T->lchild,index);
GetPreorder(last+index,mid+index+,T->rchild,len-index-);
}
void Preorder(BiTree T)
{
if(T)
{
putchar(T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
int main()
{
char mid[],last[];
while(scanf("%s%s",last,mid) != EOF)
{
BiTree T;
GetPreorder(last,mid,T,strlen(mid));//last,mid接收字符串后系统自动加'\0'
Preorder(T);
puts("");
}
return ;
}
//非递归输出
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXSIZE 26 typedef struct node{
char ch;
struct node *lchild,*rchild;
}BitNode,*BiTree; typedef struct sqstack{
int top;
BitNode* ch[MAXSIZE];//数组中每个元素都是树中结点指针
}Sqstack; void GetPreorder(char *post,char *mid,BiTree &T,int len)
{
if(!len)
{
T = NULL;
return;
}
int index = strchr(mid,post[len-]) - mid;
T = (BitNode *)malloc(sizeof(BitNode));
T->ch = post[len-];
GetPreorder(post,mid,T->lchild,index);
GetPreorder(post+index,mid+index+,T->rchild,len-index-);
} void IniStack(Sqstack &S)
{
S.top = -;
} int IsEmpty(Sqstack S)
{
if(S.top == -) return ;
else return ;
} void Push(Sqstack &S,BiTree T)
{
S.ch[++S.top] = T;
} void Pop(Sqstack &S,BiTree &T)
{
T = S.ch[S.top--];
} void Preorder(BiTree T)
{
Sqstack S;
IniStack(S);
while(T || !IsEmpty(S))
{
if(T)
{
putchar(T->ch);//visit
Push(S,T);
T = T->lchild;
}
else{
Pop(S,T);
T = T->rchild;
}
}
} int main()
{
char post[],mid[];
while(scanf("%s%s",post,mid) != EOF)
{
BiTree T;
GetPreorder(post,mid,T,(int)strlen(post));
Preorder(T);//非递归
puts("");
}
return ;
}
//不建树直接输出前序序列
//author:1495457 #include <stdio.h>
#include <string.h>
void preorder(char *post,char *mid,int len)
{
if(!len) return;
putchar(post[len-]);
int index = strchr(mid,post[len-]) - mid;//strchr:在一个串中查找给定字符的第一个匹配之处
preorder(post,mid,index);
preorder(post+index,mid+index+,len-index-);
}
int main()
{
char post[],mid[];
while(scanf("%s%s",post,mid) != EOF)
{
preorder(post,mid,strlen(post));
puts("");
}
}
补充:如果已知前序、中序,求后序
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct node{
char data;
struct node *lchild,*rchild;
}BitNode,*BiTree;
void GetPostorder(char *pre,char *mid,BiTree &T,int len)
{
if(!len)
{
T = NULL;
return;
}
char ch = pre[];//得到根结点
int index = ;//索引记录根结点在中序中的位置
while(mid[index] != ch) index ++;
T = (BiTree)malloc(sizeof(BitNode));//为根结点开辟空间
T->data = ch;
//递归建立左子树和右子树
GetPostorder(pre+,mid,T->lchild,index);
GetPostorder(pre+index+,mid+index+,T->rchild,len-index-);
}
void Postorder(BiTree T)
{
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
putchar(T->data);
}
}
int main()
{
char pre[],mid[];
while(scanf("%s%s",pre,mid) != EOF)
{
BiTree T;
GetPostorder(pre,mid,T,strlen(pre));
Postorder(T);
puts("");
}
return ;
}
//前、中
//DBACEGF ABCDEFG ACBFGED
//ABCDEFG BCDAGFE DCBGFEA
参照:http://www.tuicool.com/articles/jaiAVj
2016-07-06