中序和前序 或 中序和后序构建二叉树

利用递归，构建二叉树的时候主要就是要搞清楚，前序和中序，后序与中序的关系，然后要递归地往下构建，先建当前节点的左孩子，再右孩子，然后我利用另外一种序列遍历来验证 构建的二叉树是否正确。

#include <iostream>#include <cstdio>using namespace std;const int maxn = 35;int in[maxn];int PRe[maxn];struct node {	int data;	node *lchild;	node *rchild;};//inOrder和preOrder创建 树/*    inOrder: 12 11 20 17 1 15 8 5    preOrder: 1 11 12 17 20 5 8 15*/// or////use the inOrder and preOrder create the binary treenode *Create(int preL, int preR, int inL,int inR) {    if ( preL > preR ) return NULL;    node *root = new node();    root->data = pre[preL];    int index;    for ( index = inL; index <= inR; index++ ) {        if ( in[index] == pre[preL] )break;    }    int numLeft = index - inL;    root->lchild = Create(preL+1, preL+numLeft, inL, index-1);    root->rchild = Create(preL+numLeft+1, preR, index+1, inR);    return root;}void PostOrderTraversal(node *root) {	if ( root != NULL ) {		PostOrderTraversal(root->lchild);		PostOrderTraversal(root->rchild);        cout << root->data << " ";	}}int main() {	int n;	cin >> n;	for ( int i = 0 ; i < n; i++ ) {		cin >> in[i];	}	for ( int i = 0; i < n; i++ ) {		cin >> pre[i];	}	node *root;    root = Create(0,n-1,0,n-1);	PostOrderTraversal(root);	return 0;}
#include <iostream>#include <cstdio>using namespace std;const int maxn = 35;int in[maxn];int post[maxn];struct node {	int data;	node *lchild;	node *rchild;};//inOrder和postOrder 创建 树/*    inOrder:12 11 20 17 1 15 8 5    postOrder:12 20 17 11 15 8 5 1*/// use the inOrder and postOrder create the binary tree//node *Create(int postL, int postR, int inL, int inR) {	if ( postL > postR ) return NULL;	node *root = new node();	root->data = post[postR];	int index;	for ( index = inL; index <= inR; index++ ) {		if ( in[index] == post[postR] )break;	}	int numLeft = index - inL;	root->lchild = Create(postL, postL+numLeft-1, inL, index-1);	root->rchild = Create(postL+numLeft, postR-1, index+1, inR);	return root;}void PreOrderTraversal(node *root) {	if ( root != NULL ) {        cout << root->data << " ";		PreOrderTraversal(root->lchild);		PreOrderTraversal(root->rchild);	}}int main() {	int n;	cin >> n;	for ( int i = 0 ; i < n; i++ ) {		cin >> in[i];	}	for ( int i = 0; i < n; i++ ) {		cin >> post[i];	}	node *root;    root = Create(0,n-1,0,n-1);	PreOrderTraversal(root);	return 0;}