题干

• 已知：二叉树的先序序列和中序序列
• 求：后序序列
  

C++实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string>
using namespace std;

struct TreeNode
{
	char data;
	TreeNode* left;
	TreeNode* right;
};

TreeNode* Rebuild(string preOrder, string inOrder) {
	if (preOrder.size() == 0) {
		return NULL;
	}
	else {
		char rootdata = preOrder[0];//在先序中找到根
		TreeNode* pNew = new TreeNode;
		pNew->data = rootdata;
		int pos = inOrder.find(rootdata);//找到根在中序中的位置
		//preOrder.substr(1,pos)这是左子树的前序
		//inOrder.substr(0,pos)这是左子树的中序
		//preOrder.substr(pos+1,末尾)这是右子树的前序
		//inOrder.substr(pos+1,末尾)这是右子树的中序
		pNew->left = Rebuild(preOrder.substr(1, pos), inOrder.substr(0, pos));
		pNew->right = Rebuild(preOrder.substr(pos + 1), inOrder.substr(pos + 1));
		return pNew;
	}
}

void postOrder(TreeNode* proot) {
	if (proot == NULL) {
		return;
	}
	else {
		postOrder(proot->left);
		postOrder(proot->right);
		printf("%c", proot->data);
	}
}

int main() {
	char preOrder[30];
	char inOrder[30];
	while (scanf("%s%s", preOrder, inOrder) != EOF) {
		TreeNode* proot;
		proot = Rebuild(preOrder, inOrder);
		postOrder(proot);
		printf("\n");
	}
	return 0;
}