哈夫曼树是最优二叉树,它的特点是所有叶子节点上的权重之和最小的树。构建哈夫曼树的过程如下:
构建哈夫曼树的过程很简单,但是需要用到另外一个辅助数据结构:有序链表。我们将实现一个有序链表存放构建哈夫曼树的节点:
#include "typedef.h" //表数据结构 typedef struct s_list { //权重 int weights; //数据项 void *data; //头节点 struct s_list *next; } s_list; //按升序插入链表 bool list_insert(s_list *list, int weights, void *data) { if (list == null || data == null) { return false; } //申请新节点内存 s_list *p_new = (s_list *) malloc(sizeof(s_list)); p_new->weights = weights; p_new->data = data; p_new->next = null; //第一个节点 if (list->next == null) { list->next = p_new; return true; } //按顺序插入节点 s_list *p = list; while (p->next != null) { //只在权重小于下一个节点时插入 if (p_new->weights <= p->next->weights) { //插入新节点 p_new->next = p->next; p->next = p_new; return true; } p = p->next; } p->next = p_new; return true; } //删除链表中指定元素节点 bool list_delete(s_list *list, void *data) { if (list == null) { return false; } s_list *p = list; while (p->next != null) { //找到数据相同的节点 if (p->next->data == data) { //删除节点 s_list *p_del = p->next; p->next = p_del->next; //释放内存 free(p_del); return true; } p = p->next; } return false; }
再来实现一个哈夫曼树:
//赫夫曼节点 typedef struct s_node { //数据指针 void *data; //父节点 struct s_node *parent; //左孩子节点 struct s_node *left_child; //右孩子节点 struct s_node *right_child; } s_node; //赫夫曼数据结构 typedef struct s_tree { //根节点 s_node *root; //访问函数指针 void (*visit_node)(); //释放内存函数指针 void (*free_node)(); } s_tree; //由一个有序链表构建赫夫曼树 bool tree_create(s_tree *tree, s_list *list) { if (tree == null) { return false; } if (list == null) { return false; } if (list->next == null) { return false; } //当有序链表中前两个节点不为空时 while (list->next != null && list->next->next != null) { //取出有序链表中第一个节点 s_list *p0 = list->next; //取出有序链表中第二个节点 s_list *p1 = list->next->next; //取得树节点,权重小的为左节点,权重大的为右节点, s_node *n_left = (s_node *) p0->data; s_node *n_right = (s_node *) p1->data; //权重相同时无子树的为左节点 if (p0->weights == p1->weights) { s_node *n_temp = n_left; n_left = n_right; n_right = n_temp; } //申请新节点内存 s_node *n_node = (s_node *) malloc(sizeof(s_node)); //权重相加 int weights = p0->weights + p1->weights; //删除有序链表中的前两个节点 list_delete(list, p0->data); list_delete(list, p1->data); //构建新节点 n_node->data = null; n_node->left_child = n_left; n_node->right_child = n_right; n_left->parent = n_node; n_right->parent = n_node; //将新节点插入有序链表 list_insert(list, weights, n_node); } //经由上面处理后,有序链表中只留下一个节点 s_list *p = list->next; //取得二叉树的根节点 s_node *n_root = (s_node *) p->data; //设定二叉树的根节点 tree->root = n_root; return true; } //前序遍历 void tree_preamble_visit(s_tree *tree, s_node *node) { if (tree == null) { return; } if (tree->root == null) { return; } if (node == null) { return; } //中 tree->visit_node(node->data); //左 tree_preamble_visit(tree, node->left_child); //右 tree_preamble_visit(tree, node->right_child); }
最后来实现两个例子,测试我们的哈夫曼树:
#include <stdio.h> #include <stdlib.h> #include <string.h> #include "tree.h" #include "list.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() { s_list *list = (s_list *) malloc(sizeof(s_list)); list->weights = 0; list->data = null; list->next = null; s_tree tree; tree_init(&tree, &visit_int, &free_int); 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_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); list_insert(list, 0, n0); list_insert(list, 1, n1); list_insert(list, 2, n2); list_insert(list, 3, n3); list_insert(list, 4, n4); list_insert(list, 5, n5); list_insert(list, 6, n6); list_insert(list, 7, n7); list_insert(list, 8, n8); tree_create(&tree, list); //前序遍历 tree_preamble_visit(&tree, tree.root); printf("\n"); //销毁树 tree_destroy(&tree); free(list); } void sample_B() { s_list *list = (s_list *) malloc(sizeof(s_list)); list->weights = 0; list->data = null; list->next = null; s_tree tree; tree_init(&tree, &visit_int, &free_int); int *t0 = (int *) malloc(sizeof(char)); int *t1 = (int *) malloc(sizeof(char)); int *t2 = (int *) malloc(sizeof(char)); int *t3 = (int *) malloc(sizeof(char)); int *t4 = (int *) malloc(sizeof(char)); int *t5 = (int *) malloc(sizeof(char)); int *t6 = (int *) malloc(sizeof(char)); int *t7 = (int *) malloc(sizeof(char)); *t0 = 5; *t1 = 29; *t2 = 7; *t3 = 8; *t4 = 14; *t5 = 23; *t6 = 3; *t7 = 11; 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)); 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); list_insert(list, 5, n0); list_insert(list, 29, n1); list_insert(list, 7, n2); list_insert(list, 8, n3); list_insert(list, 14, n4); list_insert(list, 23, n5); list_insert(list, 3, n6); list_insert(list, 11, n7); tree_create(&tree, list); //前序遍历 tree_preamble_visit(&tree, tree.root); printf("\n"); //销毁树 tree_destroy(&tree); free(list); } int main(int argc, char **args) { sample_A(); sample_B(); return 0; }
运行结果:
7 8 4 5 6 3 0 1 2 8 11 23 29 14 7 3 5
这两个哈夫曼树如下:
本例代码:
code path chapter.05/e.g.5.5/ 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号