【浙大数据结构】哈夫曼树

哈夫曼树

定义

带权路径长度(WPL)：设二叉树有n个叶结点，每个叶结点带有权值wk,从根结点到每个叶结点的长度为lk，则每个叶结点的带权路径长度之和就是：
$$
WPL = \sum_{n=1}^n{w_kl_k}
$$
最优二叉树或哈夫曼树：WPL最小的二叉树

哈夫曼树的构造

每次把权值最小的两棵树合并

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode* HuffmanTree;
struct TreeNode{
	int Weight;
	HuffmanTree Left;
	HuffmanTree Right;
};

typedef struct HeapStruct* Heap;
struct HeapStruct{
	HuffmanTree* Elements; // Elements是一个数组，元素为指向TreeNode的指针
	int Size;
	int Capacity;
};

void BuildMinHeap(Heap H); //按照权值将H中的Elements[]排成最小堆

struct TreeNode* DeleteMin(Heap H); //返回H最小结点的地址

void Insert(Heap H, HuffmanTree T);// 将指针T插入H中

HuffmanTree Huffman(Heap H)
{
	int i;
	HuffmanTree T = nullptr;
	for(i = 0; i < H->Size; i++){ //进行Size-1次处理
		T = (HuffmanTree)malloc(sizeof(struct TreeNode));
		T->Left = DeleteMin(H);
		T->Right = DeleteMin(H);
		T->Weight = T->Left->Weight + T->Right->Weight;
		Insert(H, T);// 将新生成的T塞回H里
	}
	//for循环结束后H中只剩下一个元素，即T指向的元素的地址
	
	T = DeleteMin(H); //这一步意义不大，猜测是为了清空 H
	return T;
}