数据结构实战

        哈夫曼树是最优二叉树，它的特点是所有叶子节点上的权重之和最小的树。构建哈夫曼树的过程如下：

1. 将所有叶子节点置于一个集合中。
2. 从集合中取出权重最小的两个节点。
3. 将这两个节点分别做为一个新节点的左节点和右节点，将两个节点的权重相加作为新节点的权重。
4. 将这两个节点从集合中删除。
5. 将新节点的加入集合中。
6. 重复第2步，直至集合中只有1个节点为止。

        构建哈夫曼树的过程很简单，但是需要用到另外一个辅助数据结构：有序链表。我们将实现一个有序链表存放构建哈夫曼树的节点：

#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