欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

前序中序求后序

程序员文章站 2022-05-19 21:21:59
...
Test:
FDXEAG
XDEFAG



/*
涉及到二叉树的问题最好不用动态申请,对内存的管理很麻烦
采用预分配的静态数组
*/
//本题目由前序和中序得到后序,方法:先构造二叉树,再进行
#include<stdio.h>
#include<string.h>
struct Node{
	Node *lchild;
	Node* rchild;
	char data;
}Tree[50];
char str1[50],str2[50];//分别存放前序和中序
int loc;//指向下一个尚未分配到的位置
Node *creat(){//申请一个空节点
	Tree[loc].lchild=Tree[loc].rchild=NULL;
	return &Tree[loc++];
}
void PostOrder(Node *T){
	if(T->lchild) PostOrder(T->lchild);
	if(T->rchild) PostOrder(T->rchild);
	printf("%c",T->data);
}
/*
	先序的第一个是根,确定其在中序下的位置即可划分左右子树
*/
Node *build(int s1,int e1,int s2,int e2){
	Node *ret=creat();
	ret->data=str1[s1];
	int root;
	for(int i=s2;i<=e2;i++){
		if(str2[i]==str1[s1])
		{root=i;break;}		
	}
	int size=root-s2;
	//当root不为s2和e2时有左右子树
	if(root!=s2)
		ret->lchild=build(s1+1,s1+size,s2,root-1);
	if(root!=e2)
		ret->rchild=build(s1+size+1,e1,root+1,e2);
	return ret;
}

int main(){
	while(scanf("%s",str1)!=EOF){
		scanf("%s",str2);
		int len1=strlen(str1);
		int len2=strlen(str2);
		Node *T=build(0,len1-1,0,len2-1);
		PostOrder(T);
		printf("\n");
	}
	return 0;
}