数据结构实战

在前面的二叉树章节里，我们都是采用手动的方法来构建二叉树的，本节我们将采用前序法构建一棵二叉树。再来看一下我们需要构建二叉树的结构：

        这是我们需要构建的二叉树，我们将采用前序法生成这一棵树。先来看一下前序序列：

0 1 3 4 2 5 7 8 6

        下面我们来编写前序生成算法：

//前序构建二叉树
void tree_create_preamble(s_node *p_node, int left_right, s_node **node, void ***p)
{
	if (p == null)
	{
		return;
	}
	//遇到空指针返回
	if (**p == null)
	{
		return;
	}

	//创建新节点
	*node = (s_node *) malloc(sizeof(s_node));
	tree_init_node(*node, **p);

	//设置父节点
	(*node)->parent = p_node;
	if (p_node != null)
	{
		//设置父节点的左孩子
		if (left_right == 0)
		{
			p_node->left_child = *node;
		}
		//设置父节点的右孩子
		else if (left_right == 1)
		{
			p_node->right_child = *node;
		}
	}

	//下一个数据地址
	(*p)++;
	//构建左子树
	tree_create_preamble(*node, 0, &((*node)->left_child), p);

	//下一个数据地址
	(*p)++;
	//构建右子树
	tree_create_preamble(*node, 1, &((*node)->right_child), p);

}

        再来定义一个数据结构，为了测试我们的二叉树可以存放任意类型的数据：

typedef struct
{
	int no;
	char *name;
} student;

//删除整数函数
void free_student(student *stu)
{
	if (stu != null)
	{
		free(stu->name);
		free(stu);
	}
}

//访问整数函数
void visit_student(student *stu)
{
	if (stu != null)
	{
		printf("%d\t%s\n", stu->no, stu->name);
	}
}

        在main函数中实现构建“学生”的二叉树：

int main(int argc, char **args)
{
	//初始化树
	s_tree tree;
	tree_init(&tree, &visit_student, &free_student);

	student *stu0 = (student *) malloc(sizeof(student));
	stu0->no = 0;
	stu0->name = (char *) malloc(20);
	memcpy(stu0->name, "AAA", 20);

	student *stu1 = (student *) malloc(sizeof(student));
	stu1->no = 1;
	stu1->name = (char *) malloc(20);
	memcpy(stu1->name, "BBB", 20);

	student *stu2 = (student *) malloc(sizeof(student));
	stu2->no = 3;
	stu2->name = (char *) malloc(20);
	memcpy(stu2->name, "CCC", 20);

	student *stu3 = (student *) malloc(sizeof(student));
	stu3->no = 4;
	stu3->name = (char *) malloc(20);
	memcpy(stu3->name, "DDD", 20);

	student *stu4 = (student *) malloc(sizeof(student));
	stu4->no = 2;
	stu4->name = (char *) malloc(20);
	memcpy(stu4->name, "EEE", 20);

	student *stu5 = (student *) malloc(sizeof(student));
	stu5->no = 5;
	stu5->name = (char *) malloc(20);
	memcpy(stu5->name, "FFF", 20);

	student *stu6 = (student *) malloc(sizeof(student));
	stu6->no = 7;
	stu6->name = (char *) malloc(20);
	memcpy(stu6->name, "GGG", 20);

	student *stu7 = (student *) malloc(sizeof(student));
	stu7->no = 8;
	stu7->name = (char *) malloc(20);
	memcpy(stu7->name, "HHH", 20);

	student *stu8 = (student *) malloc(sizeof(student));
	stu8->no = 6;
	stu8->name = (char *) malloc(20);
	memcpy(stu8->name, "III", 20);

	student **pdata = (student **) malloc(sizeof(student *) * 20);

	pdata[0] = stu0;
	pdata[1] = stu1;
	pdata[2] = stu2;
	pdata[3] = null;
	pdata[4] = null;
	pdata[5] = stu3;
	pdata[6] = null;
	pdata[7] = null;
	pdata[8] = stu4;
	pdata[9] = stu5;
	pdata[10] = stu6;
	pdata[11] = null;
	pdata[12] = null;
	pdata[13] = stu7;
	pdata[14] = null;
	pdata[15] = null;
	pdata[16] = stu8;
	pdata[17] = null;
	pdata[18] = null;

	//前序构建二叉树
	tree_create(&tree, 0, (void **) pdata);

	//前序遍历
	tree_preamble_visit(&tree, tree.root);
	printf("\n");
	//中序遍历
	tree_inorder_visit(&tree, tree.root);
	printf("\n");
	//后序遍历
	tree_postorder_visit(&tree, tree.root);
	printf("\n");

	free(pdata);

	//销毁树
	tree_destroy(&tree);

	return 0;
}

        运行结果：

0	AAA
1	BBB
3	CCC
4	DDD
2	EEE
5	FFF
7	GGG
8	HHH
6	III

3	CCC
1	BBB
4	DDD
0	AAA
7	GGG
5	FFF
8	HHH
2	EEE
6	III

3	CCC
4	DDD
1	BBB
7	GGG
8	HHH
5	FFF
6	III
2	EEE
0	AAA

        本例代码：

code path   chapter.05/e.g.5.3/

https       https://github.com/magicworldos/datastructure.git
git         git@github.com:magicworldos/datastructure.git
subverion   https://github.com/magicworldos/datastructure