编辑代码

/****************   第6.3.3节 从遍历序列恢复二叉树（133页） ****/
/**************** 算法6.7 从遍历序列恢复二叉树（133页）**********
		            算法6.7   从（先序和中序）遍历序列恢复二叉树
					          （以后序输出二叉树）
************************************************************/
#include <stdlib.h>
#include <stdio.h>
#define maxsize  100
typedef char datatype;

//二叉树的二叉链表存储表示
typedef struct node {
	datatype data;						//结点数据域
	struct node *lchild, *rchild;	//左右孩子指针
} bitree;

/*******算法6.7   从遍历序列恢复二叉树（先序和中序遍历序列）
**********************************************************/
bitree *BPI(datatype preod[], datatype inod[], int i, int j, int k, int h)

// i,j为先序遍历数组起始位和终点下标，k,h为中序起始和终端下标
{
	int m;
	bitree *p;
	p = (bitree *)malloc(sizeof(bitree)); //构造根结点
	p->data = preod[i];
	m = k;
	while (inod[m] != preod[i])
		m++;         //查找根结点在中序序列中的位置
	if (m == k)
		p->lchild = NULL; // 对左子树进行构造
	else
		p->lchild = BPI(preod, inod, i + 1, i + m - k, k, m - 1);
	if (m == h)
		p->rchild = NULL; // 对右子树进行构造
	else
		p->rchild = BPI(preod, inod, i + m - k + 1, j, m + 1, h);
	return (p);
}

void show(bitree *t) {  //以后序遍历输出二叉树
	if (t == NULL)
		return;
	show((t->lchild));
	show((t->rchild));
	printf("%2c", t->data);
}

int main() {
	bitree *T;
	datatype preod[maxsize];
	datatype inod[maxsize];
	int i, j, n;
	printf("输入结点个数");
	scanf("%d", &n);

	printf("请输入前序\n");
	_flushall(); //清除所有缓冲区
	for (i = 0; i < n; i++) {
		scanf("%c", &preod[i]);
	}

	printf("请输入中序\n");
	_flushall();  //清除所有缓冲区
	for (j = 0; j < n; j++) {
		scanf("%c", &inod[j]);
	}

	T = BPI(preod, inod, 0, n - 1, 0, n - 1);
	printf("后序输出二叉树：\n");
	show(T);
	return 0;
}

//测试样例1 (教材第131页图6.10中的二叉树)
// 输入: 结点个数 8  前序preod: ABDEGCFH  中序inod: DBEGACHF
// 输出：后序postod: DGEBHFCA

//测试样例2 (教材第134页图6.11)
// 输入: 结点个数 9  前序preod: ABHFDECKG  中序inod: HBDFAEKCG
// 输出：后序postod: HDFBKGCEA