本文共 2165 字，大约阅读时间需要 7 分钟。

/* binarytree.h */#ifndef BINARYTREE_H#define BINARYTREE_Htypedef struct node *link;struct node {	unsigned char item;	link l, r;};link init(unsigned char VLR[], unsigned char LVR[], int n);void pre_order(link t, void (*visit)(link));void in_order(link t, void (*visit)(link));void post_order(link t, void (*visit)(link));int count(link t);int depth(link t);void destroy(link t);#endif/* binarytree.c */#include 
   
    #include "binarytree.h"static link make_node(unsigned char item){	link p = malloc(sizeof *p);	p->item = item;	p->l = p->r = NULL;	return p;}static void free_node(link p){	free(p);}/* * VLR 前序遍历 * LVR 中序遍历 * n   节点个数 */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++);        /* 循环结束后k就是根节点的在中序遍历中的位置 */        /* 跟左边的就是左子树（k个），右边的就是右字树（n-k-1个）*/	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 pre_order(link t, void (*visit)(link)){	if (!t)		return;	visit(t);	pre_order(t->l, visit);	pre_order(t->r, visit);}void in_order(link t, void (*visit)(link)){	if (!t)		return;	in_order(t->l, visit);	visit(t);	in_order(t->r, visit);}void post_order(link t, void (*visit)(link)){	if (!t)		return;	post_order(t->l, visit);	post_order(t->r, visit);	visit(t);}int count(link t){	if (!t)		return 0;	return 1 + count(t->l) + count(t->r);}int depth(link t){	int dl, dr;	if (!t)		return 0;	dl = depth(t->l);	dr = depth(t->r);	return 1 + (dl > dr ? dl : dr);}void destroy(link t){	post_order(t, free_node);}/* main.c */#include 
    
     #include "binarytree.h"void print_item(link p){	printf("%d", p->item);}int main(){	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);	pre_order(root, print_item);	putchar('\n');	in_order(root, print_item);	putchar('\n');	post_order(root, print_item);	putchar('\n');	printf("count=%d depth=%d\n", count(root), depth(root));	destroy(root);	return 0;}
    
   

前序和中序遍历的结果合在一起可以唯一确定二叉树的形态，

也就是说根据遍历结果可以构造出二叉树.

转载地址：http://axuhj.baihongyu.com/