#include "stdafx.h"
#include <iostream>
using namespace std;

struct Node
{
	char data;
	Node *lc;
	Node *rc;
};
void CreateBinTree(Node *&root,char *preStr,int preLeft,int preRight,char *inStr,int inLeft,int inRight)
{//root要取引用，因为Node*指针类型也就是变量地址，是传值类型的，不能传出，取引用才能传出
	if (preLeft > preRight || inLeft > inRight) //已经把遍历结果处理完了，也就是这棵子树构造完成了
	{
		root = NULL;
	}else
	{
		root = new Node;
		root->data = preStr[preLeft];
		int index = inLeft;
		while (inStr[index] != preStr[preLeft])//查找前序结果第一个字符在中序结果中的位置
		{
			index++;
		}
		//由于前序遍历的结果每个元素都是一个根节点的值，而中序遍历结果分成两部分后，每部分都要构造一棵树，所以在递归时也要从前序遍历中取相同个数的元素出来
		CreateBinTree(root->lc, preStr, preLeft + 1, preLeft + index - inLeft, inStr, inLeft,index-1);
		CreateBinTree(root->rc, preStr, preLeft + index - inLeft + 1, preRight, inStr, index + 1, inRight);
	}
}
int main()
{
	char* preStr = "0134256";
	char* inStr = "3140526";
	Node *root;
	CreateBinTree(root, preStr, 0, 6, inStr, 0, 6);
	system("pause");
	return 0;
}