学步园

/**
* 问题描述：
*	根据一颗二叉树的前序和中序遍历结果，重构这颗二叉树并输出后序遍历结果
*/
#include <iostream>
using namespace std;

typedef struct node {
	int value;
	struct node *left;
	struct node *right;
}NODE;
NODE *root;

//节点分配函数
NODE *malloc_NODE(int value){
	NODE *p = NULL;
	p = (NODE *)malloc(sizeof(NODE));
	p->value = value;
	p->right = NULL;
	p->left = NULL;
	return p;
}

/**
 * 每次递归根节点已经创建好，我们的任务就是递归创建左子树和右子树
 * 从图中可以看到：
 * 左子树的前序和中序的起始指针很容易找到，但是右子树的
 * 前序和中序的起始指针需要知道左子树的长度才行。
 * 此外我们还需要维护一个子树的长度tLen，以便知道当前递归是否应该结束。
*/
void rebuild_tree(NODE *root,	//当前子树根节点
					int *pre,   //当前子树先序序列起始指针
					int *in,	//当前子树中序序列起始指针
					int tLen)	//当前子树长度(节点个数)
{
	/**
	 * 首先根据中序序列求出"左子树的长度"和"右子树的长度"
	 *
	 * Then:
	 * 左子树"前序起始点" = 当前前序序列起始点 + 1;
	 * 左子树"中序起始点" = 当前中序序列起始点;
	 * 
	 * 右子树"前序起始点" = 当前前序序列起始点 + 左子树长度 + 1;
	 * 右子树"中序起始点" = 当前中序起始点 + 左子树长度 + 1;
	 */

	//求出根节点在中序序列中的索引(根据这个索引值求左右子树长度)
	int root_value = *pre;
	int root_index = 0;
	int *p = in;
	for(int i=0;i<tLen;i++){
		if(*p++ == root_value) break;
		root_index++;
	}

	//求解左子树和右子树的长度
	int lLen = root_index;
	int rLen = tLen-root_index-1;

	//递归左子树
	if(lLen != 0){
		root->left = malloc_NODE(pre[1]);
		rebuild_tree(root->left, pre+1, in, lLen);
	}
	else{
		root->left = NULL;
	}

	//递归右子树
	if(rLen != 0){
		root->right = malloc_NODE(pre[lLen+1]);
		rebuild_tree(root->right, pre+lLen+1, in+lLen+1, rLen);
	}else{
		root->right = NULL;
	}
}

//前序遍历输出
void printBST(NODE *node){
	if(node != NULL){
		cout<<node->value<<endl;
		printBST(node->left);
		printBST(node->right);
	}
}

#define M 5
int main(){
	int pre[M] = {1,2,4,5,3};
	int in[M] = {4,2,5,1,3};

	root = malloc_NODE(pre[0]);

	//以root为根节点，按照pre和in两个序列重构二叉树
	rebuild_tree(root, pre, in, M);
	printBST(root);
	return 0;
}