利用先序表和中序表，后序表和中序表建二叉树

利用先序表和中序表，后序表和中序表建二叉树，必须要好好理解
DLR 先序
LDR 中序
LRD 后序
深刻的含义，以及它们之间的联系，这个很重要！！！
说很难说清，直接代码记录吧

/*  小总结   利用后序表（LRD）找到根节点
****对比 中序表（LDR）找到对应的根节点 这样以此基础将中序表分为左右两部分 ，即左支树和右支树
*****而中序表中根节点的位置序号对应后序表中位置  又可以将后序表分为左支树 右支树俩部分
*****以此方法递归不断寻找构造
********************************************
*******************************************
******LRD：  D G E B F C A
******LDR：  D B E G A F C
稍微表示一下变化顺序 叶节点就省略了（反正我能看懂）

             DGEB   FCa
			 DBEG   aFC


             D   GEb   Fca
			 D   bEG   aFc

              
		     d   Geb    Fca
			 d   G e g  Fca

因为先写的后序中序建表，就以此为例简述原理
先序中序原理一样         
*/
#include<stdio.h>
#include<stdlib.h>

typedef struct node{
	char data;
	struct node *LC;
	struct node *RC;
}BNode;

//中序后序建二叉树
BNode *PMCreatBTree(char *post,char *in,int n){  //post 放后序LDR  in放中序
	BNode *b;
	char root,*p;
	int k;
	if(n<=0){
		return NULL;
	}
	root=*(post+n-1);  //找根节点
	b=(BNode *)malloc(sizeof(BNode));
	b->data=root;
	for(p=in;p<in+n;p++){
		if(*p==root)
			break;
	}
	k=p-in;//定位
	b->LC=PMCreatBTree(post,in,k);
	b->RC=PMCreatBTree(post+k,p+1,n-k-1);      //右支树的递归建立

	return b;
}

//前序中序建二叉树
BNode *PrInCreatBTree(char *pre,char *in,int n){
	BNode *c;
	char *p;
	int k;
	if(n<=0)
		return NULL;
	c=(BNode *)malloc(sizeof(BNode));
	c->data= *pre;
	for(p=in;p<in+n;p++){
		if(*p==*pre)
			break;
	}
	k=p-in;
	c->LC=PrInCreatBTree(pre+1,in,k);
	c->RC=PrInCreatBTree(pre+k+1,p+1,n-k-1);

	return c;


}

//前序遍历
void ShowPre(BNode *b){
	if(b){
		printf("%c",b->data);
		ShowPre(b->LC);
		ShowPre(b->RC);
	}
}

//中序遍历
void ShowIn(BNode *b){
	if(b){
		ShowIn(b->LC);
		printf("%c",b->data);
		ShowIn(b->RC);
	}
	
}

//后序遍历
void ShowPost(BNode *b){
	if(b){
		ShowPost(b->LC);
		ShowPost(b->RC);
		printf("%c",b->data);
	}
	
}

int main(){
	int n;
	BNode *b=NULL;
	BNode *c=NULL;
	char pre[]="ABDEGCF";
	char in[]="DBEGAFC";
	char post[]="DGEBFCA";

	n=sizeof(post)/sizeof(char)-1;

	b=PMCreatBTree(post,in,n);
	c=PrInCreatBTree(pre,in,n);

	printf("前序中序建表验证:\n");
	printf("\n前序遍历结果为:\n");
	ShowPre(c);
	printf("\n");
	printf("中序遍历结果为:\n");
	ShowIn(c);
	printf("\n");
	printf("后序遍历结果为:\n");
	ShowPost(c);

	printf("\n\n*******************************\n\n");

	printf("后序中序建表验证:\n");
	printf("\n前序遍历结果为:\n");
	ShowPre(b);
	printf("\n");
	printf("中序遍历结果为:\n");
	ShowIn(b);
	printf("\n");
	printf("后序遍历结果为:\n");
	ShowPost(b);
	printf("\n");
	return 0;
}

这里就不手动输入数据了，都是一样的
测试结果：