二叉树的创建：根据前序中序、中序后序递归创建二叉树

根据如图创建二叉树：

   

  先序遍历为： "A B C D E F G H"
  中序遍历为： "C B E D F A G H"
  后序遍历为： "C E F D B H G A"

代码如 下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h> // memset;
#include<iostream>
using namespace std;

typedef char ElemType;

typedef struct BtNode //创建二叉树
{
	 BtNode *leftchild;  
	 BtNode *rightchild;
	 ElemType data;
}BtNode, *BinaryTree;

 BtNode * Buynode() //申请结点
{
    BtNode *s = ( BtNode*)malloc(sizeof(BtNode));
	if(NULL == s) exit(1);
	memset(s,0,sizeof(BtNode));
	return s;
}

void Freenode(BtNode *p)
{
	free(p);
}

void PreOrder(BtNode *p) //先序
{
	if(p != NULL)
	{
		printf("%c ",p->data);
		PreOrder(p->leftchild);
		PreOrder(p->rightchild);
	}
}

void InOrder(BtNode *p) //中序
{
	if(p != NULL)
	{
		InOrder(p->leftchild);
		printf("%c ",p->data);
		InOrder(p->rightchild);
	}
}

void PastOrder(BtNode *p) //后序
{
	if(p != NULL)
	{
		PastOrder(p->leftchild);
		PastOrder(p->rightchild);
		printf("%c ",p->data);
	}
}

int FindIndex(const ElemType *istr,int n,ElemType x) //找下标
{
	int pos = -1;
	for(int i = 0;i<n;++i)
	{
		if(istr[i] == x)
		{
			pos = i;
			break;
		}
	}
	return pos; // -1;
}

BtNode * CreatePI(const ElemType *pstr,const ElemType *istr,int n)//先序中序创建
{
	struct BtNode *s = NULL;
	if(n > 0)
	{
		s = Buynode();
		s->data = *pstr;
		int pos = FindIndex(istr,n,*pstr);
		if(-1 == pos) exit(1);
		s->leftchild = CreatePI(pstr+1,istr,pos);
		s->rightchild = CreatePI(pstr+1+pos,istr+1+pos,n-pos-1);
	}
	return s;
}
BtNode * CreateTreePI(const ElemType *pstr,const ElemType *istr,int n)//先序中序创建
{
	if(NULL == pstr || NULL == istr || n < 1) return NULL;
	return CreatePI(pstr,istr,n);
}

struct BtNode * CreateIL(const ElemType *istr,const ElemType *lstr,int n)//中序后序创建
{
	struct BtNode *s = NULL;
	if(n > 0)
	{
		s = Buynode();
		s->data = lstr[n-1]; // *(lstr+n-1);
		int pos = FindIndex(istr,n,lstr[n-1]);
		if(-1 == pos) exit(1);
		s->leftchild = CreateIL(istr,lstr,pos);
		s->rightchild = CreateIL(istr + pos + 1,lstr + pos,n - pos -1);
	}
	return s;
}
struct BtNode * CreateTreeIL(const ElemType *istr,const ElemType *lstr,int n)//中序后序创建
{
	if(NULL == istr || NULL == lstr || n < 1) return NULL;
	return CreateIL(istr,lstr,n);
}

int main()
{
	char *pstr = "ABCDEFGH";
	char *istr = "CBEDFAGH";
	char *lstr = "CEFDBHGA";
	int n =  strlen(pstr);
	BinaryTree root = CreateTreePI(pstr,istr,n);
	//BinaryTree root = CreateTreeIL(istr,lstr,n);
	PreOrder(root); printf("\n");
	InOrder(root); printf("\n");
	PastOrder(root); printf("\n");
	return 0;
}

运行结果：