学步园

【问题描述】已知两个序列，分别表示二叉树前序遍历和中序遍历的结果，根据他们建立一个二叉树，注意处理两个序列不合法的情况。

【举例】

如果输入为：

char preOrder[]={'a','b','d','e','c','f','g'};
char inOrder[]={'d','b','e','a','f','c','g'};

输出这样一棵树:

【代码】

#include "stdafx.h"
#include <iostream>
using namespace std;
struct BTreeNode{
	char value;
	struct BTreeNode *leftchild;
	struct BTreeNode *rightchild;
};
//notice:the forth param is refernce
void CreatBTree(char *preOrder,char *inOrder,int len,BTreeNode *&root){
	BTreeNode *temp=(BTreeNode*)malloc(sizeof(BTreeNode*));
	temp->value=*preOrder;
	temp->leftchild=NULL;
	temp->rightchild=NULL;

	if(root==NULL)
		root=temp;
	if(len==1)
		return;

	//record the end of inOrder'left part
	char *leftEnd=inOrder;
	//length of left part
	int leftLength=0;
	while(*leftEnd!=*preOrder)
	{
		++leftLength;
		//illegal
		if(leftLength>len)
			break;
		++leftEnd;
	}

	//length of right part
	int rightLength=len-leftLength-1;
	if(leftLength>0)
		CreatBTree(preOrder+1,inOrder,leftLength,root->leftchild);
	if(rightLength>0)
		CreatBTree(preOrder+leftLength+1,inOrder+leftLength+1,rightLength,root->rightchild);

}
int main(){
	char preOrder[]={'a','b','d','e','c','f','g'};
	char inOrder[]={'d','b','e','a','f','c','g'};
	int len=sizeof(preOrder)/sizeof(char);
	BTreeNode *root=NULL;
	CreatBTree(preOrder,inOrder,len,root);
	return 0;
}

【扩展】考虑用前序和后续遍历的序列建立一棵二叉树