codevs 1013 求先序排列

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目链接：http://codevs.cn/problem/1013/

题目描述 Description

给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。

输入描述 Input Description

两个字符串，分别是中序和后序（每行一个）

输出描述 Output Description

一个字符串，先序

样例输入 Sample Input

BADC

BDCA

样例输出 Sample Output

ABCD

#include<stdio.h>
#include<string.h>
#include<stdlib.h> #define MaxSize 100 typedef char ElemType;
typedef struct node
{
ElemType data; //数据元素
struct node *lchild; //指向左孩子结点
struct node *rchild; //指向右孩子结点
} BTNode; BTNode *CreateBT2(char *post,char *in,int n)
/*post存放后序序列,in存放中序序列,n为二叉树结点个数,
本算法执行后返回构造的二叉链的根结点指针*/
{
BTNode *s;
char r,*p;
int k;
if (n<=) return NULL;
r=*(post+n-); //根结点值
s=(BTNode *)malloc(sizeof(BTNode)); //创建二叉树结点*s
s->data=r;
for (p=in;p<in+n;p++) //在in中查找根结点
if (*p==r)
break;
k=p-in; //k为根结点在in中的下标
s->lchild=CreateBT2(post,in,k); //递归构造左子树
s->rchild=CreateBT2(post+k,p+,n-k-); //递归构造右子树
return s;
}
void PreOrder1(BTNode *b) //先序非递归遍历算法
{
BTNode *St[MaxSize],*p;
int top=-;
if (b!=NULL)
{
top++; //根结点进栈
St[top]=b;
while (top>-) //栈不为空时循环
{
p=St[top]; //退栈并访问该结点
top--;
printf("%c",p->data);
if (p->rchild!=NULL) //右孩子结点进栈
{
top++;
St[top]=p->rchild;
}
if (p->lchild!=NULL) //左孩子结点进栈
{
top++;
St[top]=p->lchild;
}
}
printf("\n");
}
}
int main(int argc, char *argv[])
{
char str1[MaxSize],str2[MaxSize];//str1:中序序列，str2：后序序列
BTNode *bt;
scanf("%s%s",str1,str2);
bt=CreateBT2(str2,str1,strlen(str1));
PreOrder1(bt);
return ;
}