ツリーの前シーケンスと中シーケンスに基づいてツリーを復元し、後シーケンスループシーケンスを出力します.

code:

#include "stdafx.h"
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include
#include
#include

struct Node {
	Node*lchild;
	Node*rchild;
	char data;
}Tree[50];
int loc;
//       
Node*create()
{
	Tree[loc].lchild = Tree[loc].rchild = NULL;
	return &Tree[loc++];
}
char str1[30], str2[30];
//     
void postOrder(Node*T)
{
	if (T->lchild != NULL)
		postOrder(T->lchild);
	if (T->rchild != NULL)
		postOrder(T->rchild);
	printf("%c", T->data);
}
//     
void midOrder(Node*T)
{
	if (T->lchild != NULL)
		midOrder(T->lchild);
	printf("%c", T->data);
	if (T->rchild != NULL)
		midOrder(T->rchild);
}
//     
void preOrder(Node*T)
{
	printf("%c", T->data);
	if (T->lchild != NULL)
		preOrder(T->lchild);
	if (T->rchild != NULL)
		preOrder(T->rchild);
}
//               
//             
Node*build(int s1, int e1, int s2, int e2)
{
	//      ，    
	Node*root = create();
	root->data = str1[s1];

	int rootIdx;
	//                   
	for (int i = s2; i <= e2; i++)
	{
		if (str2[i] == str1[s1])
		{
			rootIdx = i;
			break;
		}
	}
	//                 
	if (rootIdx != s2)
		root->lchild = build(s1 + 1, s1 + (rootIdx - s2), s2, rootIdx - 1);
	//                 
	if (rootIdx != e2)
		root->rchild = build(s1 + (rootIdx - s2) + 1, e1, rootIdx + 1, e2);
	return root;
}

void get_postOrder()
{
	int x;
	scanf_s("%d", &x);
	while (x)
	{
		std::cin >> str1;
		std::cin >> str2;
		loc = 0;
		int l1 = strlen(str1);
		int l2 = strlen(str2);
		Node*T = build2(0, l1 - 1, 0, l2 - 1);
		preOrder(T);
		printf("
");
		scanf_s("%d", &x);
	}
}

int main(void)
{
	get_postOrder();
	

	system("pause");
    return 0;
}