树与森林通常为人们在实际生活中对事物的感观认知,例如中国有很多个省,每个省中又有多个城市,每个成都市中又被划分出多个区、县等等。又如一个公司有多个事业部,每一个事业部下又有多个部门,每个部门中又有多个业务方向等等。我们把这类数据抽象为“树”型结构。多个树被称之为森林。我们可以使用图形来表示树和森林的结构:
树(多叉树)
森林(多叉树森林)
为了与二叉树区分开来,普通的树型结构通常称为多叉树。它的表示方法也有很多,例如父节点表示法:
typedef struct s_node { //数据指针 void *data; //父节点 struct s_node *parent; } s_node;
或者采用孩子节点表示法:
typedef struct s_node { //数据指针 void *data; //孩子节点 struct s_node* children[MAX_COUNT]; } s_node;
或者采用父子节点表示法:
typedef struct s_node { //数据指针 void *data; //父节点 struct s_node *parent; //孩子节点 struct s_node *children[MAX_COUNT]; } s_node;
这几种数据结构都可以表示多叉树。但它们有都一些局限性,构建树操作和遍历树操作都相对复杂。
对于多叉树和森林,通常还有另外一种比较好的表示方法,叫做:孩子兄弟表示法,或者叫二叉树表示法,或者叫二叉链表表示法。这种表示方法是将树或森林转化为通用二叉树来表示。二叉树中左节点表示当前节点的孩子节点,右节点表示当前节点的兄弟节点。任何一个多叉树或森林都可以采用这种方式转化为一棵二叉树:
多叉树转化为二叉树表示
森林转化为二叉树表示
二叉树中左节点表示多叉树中子节点,二叉树中右节点表示多叉树中的兄弟节点:
//二叉树节点 typedef struct s_node { //数据指针 void *data; //父节点 struct s_node *parent; //左孩子节点 struct s_node *left_child; //右兄弟节点 struct s_node *right_sibling; } s_node; //二叉树数据结构 typedef struct s_tree { //根节点 s_node *root; //访问函数指针 void (*visit_node)(); //释放内存函数指针 void (*free_node)(); } s_tree;
在前面的章节中我们已经学习二叉树的相关操作,这里就可以使用直接使用二叉树来表示多叉树与森林:
#include <stdio.h> #include <stdlib.h> #include <string.h> #include "tree.h" //删除整数函数 void free_int(int *i) { if (i != null) { free(i); } } //访问整数函数 void visit_int(int *i) { if (i != null) { printf("%d ", *i); } } //多叉树的二叉树表示法 void sample_A() { int *t0 = (int *) malloc(sizeof(int)); int *t1 = (int *) malloc(sizeof(int)); int *t2 = (int *) malloc(sizeof(int)); int *t3 = (int *) malloc(sizeof(int)); int *t4 = (int *) malloc(sizeof(int)); int *t5 = (int *) malloc(sizeof(int)); int *t6 = (int *) malloc(sizeof(int)); int *t7 = (int *) malloc(sizeof(int)); int *t8 = (int *) malloc(sizeof(int)); *t0 = 0; *t1 = 1; *t2 = 2; *t3 = 3; *t4 = 4; *t5 = 5; *t6 = 6; *t7 = 7; *t8 = 8; //初始化树 s_tree tree; tree_init(&tree, &visit_int, &free_int); s_node *n0 = (s_node *) malloc(sizeof(s_node)); s_node *n1 = (s_node *) malloc(sizeof(s_node)); s_node *n2 = (s_node *) malloc(sizeof(s_node)); s_node *n3 = (s_node *) malloc(sizeof(s_node)); s_node *n4 = (s_node *) malloc(sizeof(s_node)); s_node *n5 = (s_node *) malloc(sizeof(s_node)); s_node *n6 = (s_node *) malloc(sizeof(s_node)); s_node *n7 = (s_node *) malloc(sizeof(s_node)); s_node *n8 = (s_node *) malloc(sizeof(s_node)); tree_init_node(n0, t0); tree_init_node(n1, t1); tree_init_node(n2, t2); tree_init_node(n3, t3); tree_init_node(n4, t4); tree_init_node(n5, t5); tree_init_node(n6, t6); tree_init_node(n7, t7); tree_init_node(n8, t8); //插入根节点 tree_insert(&tree, null, 0, n0); tree_insert(&tree, n0, 0, n1); tree_insert(&tree, n1, 1, n2); tree_insert(&tree, n2, 0, n4); tree_insert(&tree, n2, 1, n3); tree_insert(&tree, n4, 1, n5); tree_insert(&tree, n3, 0, n6); tree_insert(&tree, n6, 1, n7); tree_insert(&tree, n7, 1, n8); //前序遍历 tree_preamble_visit(&tree, tree.root); printf("\n"); //中序遍历 tree_inorder_visit(&tree, tree.root); printf("\n"); //后序遍历 tree_postorder_visit(&tree, tree.root); printf("\n"); //销毁树 tree_destroy(&tree); } //森林的二叉树表示法 void sample_B() { int *t0 = (int *) malloc(sizeof(int)); int *t1 = (int *) malloc(sizeof(int)); int *t2 = (int *) malloc(sizeof(int)); int *t3 = (int *) malloc(sizeof(int)); int *t4 = (int *) malloc(sizeof(int)); int *t5 = (int *) malloc(sizeof(int)); int *t6 = (int *) malloc(sizeof(int)); int *t7 = (int *) malloc(sizeof(int)); int *t8 = (int *) malloc(sizeof(int)); *t0 = 0; *t1 = 1; *t2 = 2; *t3 = 3; *t4 = 4; *t5 = 5; *t6 = 6; *t7 = 7; *t8 = 8; //初始化树 s_tree tree; tree_init(&tree, &visit_int, &free_int); s_node *n0 = (s_node *) malloc(sizeof(s_node)); s_node *n1 = (s_node *) malloc(sizeof(s_node)); s_node *n2 = (s_node *) malloc(sizeof(s_node)); s_node *n3 = (s_node *) malloc(sizeof(s_node)); s_node *n4 = (s_node *) malloc(sizeof(s_node)); s_node *n5 = (s_node *) malloc(sizeof(s_node)); s_node *n6 = (s_node *) malloc(sizeof(s_node)); s_node *n7 = (s_node *) malloc(sizeof(s_node)); s_node *n8 = (s_node *) malloc(sizeof(s_node)); tree_init_node(n0, t0); tree_init_node(n1, t1); tree_init_node(n2, t2); tree_init_node(n3, t3); tree_init_node(n4, t4); tree_init_node(n5, t5); tree_init_node(n6, t6); tree_init_node(n7, t7); tree_init_node(n8, t8); //插入根节点 tree_insert(&tree, null, 0, n0); tree_insert(&tree, n0, 0, n1); tree_insert(&tree, n1, 1, n2); tree_insert(&tree, n2, 0, n3); tree_insert(&tree, n2, 1, n6); tree_insert(&tree, n3, 1, n4); tree_insert(&tree, n4, 1, n5); tree_insert(&tree, n6, 0, n7); tree_insert(&tree, n7, 1, n8); //前序遍历 tree_preamble_visit(&tree, tree.root); printf("\n"); //中序遍历 tree_inorder_visit(&tree, tree.root); printf("\n"); //后序遍历 tree_postorder_visit(&tree, tree.root); printf("\n"); //销毁树 tree_destroy(&tree); } int main(int argc, char **args) { sample_A(); printf("\n"); sample_B(); return 0; }
运行结果:
0 1 2 4 5 3 6 7 8 1 4 5 2 6 7 8 3 0 5 4 8 7 6 3 2 1 0 0 1 2 3 4 5 6 7 8 1 3 4 5 2 7 8 6 0 5 4 3 8 7 6 2 1 0
本例代码:
code path chapter.05/e.g.5.4/ 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号