【二叉树】已知二叉树前序序列和中序序列，重建唯一二叉树

样例：

                 a

                /  

              b     f

                   

               c     g

              /

            d

             

              e

此二叉树前序序列为；abcdefg中序序列为：bdecafc

思路：先观察前序第一个节点a，其必为树的根；中序序列里节点a之前的节点构成节点a的左子树，剩下的节点为节点a的右子树；对于左右子树同样重复上面的步骤判断即可。

#include <stdio.h>
#include <stdlib.h>

//由前序序列、中序序列重建二叉树
void reconstruct_tree(char *pre, char* in, int i, treenode** T){
	int k;

	if(i==0){
		*T = NULL;
		return;
	}
	else{
		if((*T=(treenode*)malloc(sizeof(treenode)))==NULL){
			printf("malloc failed
");
			exit(0);
		}
		else{
			(*T)->data = *pre;
			(*T)->lc = NULL;
			(*T)->rc = NULL;
			k=0;
			if(*pre!=*in){
				for(k=0; k<i; k++){
					if(*pre==*(in+k)){
						break;
					}
				}
				reconstruct_tree(pre+1, in, k, &(*T)->lc);
			}
			if(k<i){
				reconstruct_tree(pre+k+1, in+k+1, i-k-1, &(*T)->rc);
			}
		}
	}
}

int main(void)
{
	treenode *mytree=NULL;
	tlist *mytlist=NULL;
	int i,k;
	char *pre, *in;

	scanf("%d", &i);
	if((pre=(char*)malloc(sizeof(char)*i))==NULL){
		printf("malloc failed
");
		exit(0);
	}
	if((in=(char*)malloc(sizeof(char)*i))==NULL){
		printf("malloc failed
");
		exit(0);
	}
	for(k=0; k<i; k++){
		fflush(stdin);
		scanf("%c", pre+k);
	}
	for(k=0; k<i; k++){
		fflush(stdin);
		scanf("%c", in+k);
	}
	reconstruct_tree(pre, in, i, &mytree);

	pre_visit_tree(mytree); printf("
");

	system("pause");
	return 0;
}