在前面的二叉树章节里,我们都是采用手动的方法来构建二叉树的,本节我们将采用前序法构建一棵二叉树。再来看一下我们需要构建二叉树的结构:
这是我们需要构建的二叉树,我们将采用前序法生成这一棵树。先来看一下前序序列:
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
Copyright © 2015-2023 问渠网 辽ICP备15013245号