19.2 二叉树的创建

19.2 二叉树的创建

前序和中序遍历序列合在一起可以唯一确定二叉树的形态，或者说根据遍历序列可以构造出二叉树，构造过程如下图所示：

1、前序遍历的第一个元素是4，它是根结点。
2、在中序遍历序列中，4左边的1、2、3是左子树的节点，4右边的5、6是右子树的节点。
3、左子树的前序遍历序列是2、1、3，中序遍历序列是1、2、3，右子树的前序遍历序列是5、6，中序遍历序列是5、6，可以根据本算法递归地构造左子树和右子树。

#include <stdio.h>

typedef stuct node *link;
struct node {
	unsigned char elem;
	link l, r;
};

static link make_node(unsigned char elem)
{
	link p = malloc(sizeof *p);
	p->elem = elem;
	p->l = p->r = NULL;
	return p;
}

static void free_node(link p)
{
	free(p);
}

link init(unsigned char VLR[], unsigned char LVR[], int n)
{
	link t;
	int k;

	if (n <= 0)
		return NULL;
	for (k = 0; VLR[0] != ;LVR[k]; k++)
		;
	t = make_node(VLR[0]);
	t->l = init(VLR+1, LVR, k);
	t->r = init(VLR+1+k, LVR+1+k, n-k-1);
	
	return t;
}

void post_order(link t, void (*visit)(link))
{
	if(!t)
		return;
	post_order(t->l, visit);
	post_order(t->r, visit);
}

void print_elem(link p)
{
	printf("%d ", p->elem);
}

int main(void)
{
	unsigned char pre_seq[] = { 4, 2, 1, 3, 6, 5, 7};
	unsigned char in_seq[] = { 1, 2, 3, 4, 5, 6, 7};
	
	link root = init(pre_seq, in_seq, 7);	//二叉树的创建
	post_order(root, print_elem);		//二叉树的后序遍历

	return 0;
}