开发笔记:数据结构笔记11哈夫曼树与哈夫曼编码

&＃xff08;笔记总结自浙大MOOC&＃xff09;
哈夫曼树的定义

哈夫曼树的构造
每次把权值最小的两棵二叉树合并

typedef struct TreeNode *HuffmanTree;
struct TreeNode{
int Weight;
HuffmanTree Left, Right;
} HuffmanTree Huffman( MinHeap H ) {
/* 假设H->Size个权值已经存在H->Elements[]->Weight里 */
int i; HuffmanTree T;
BuildMinHeap(H); /*将H->Elements[]按权值调整为最小堆*/
for (i &＃61; 1; i < H->Size; i&＃43;&＃43;) { /*做H->Size-1次合并*/
T &＃61; malloc( sizeof( struct TreeNode) ); /*建立新结点*/
T->Left &＃61; DeleteMin(H);
/*从最小堆中删除一个结点&＃xff0c;作为新T的左子结点*/
T->Right &＃61; DeleteMin(H);
/*从最小堆中删除一个结点&＃xff0c;作为新T的右子结点*/
T->Weight &＃61; T->Left->Weight&＃43;T->Right->Weight;
/*计算新权值*/
Insert( H, T ); /*将新T插入最小堆*/ }
T &＃61; DeleteMin(H); return T; }


整体复杂度为O(N logN)

哈夫曼树的特点:
没有度为1的结点&＃xff1b;
n个叶子结点的哈夫曼树共有2n-1个结点&＃xff1b;
哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树&＃xff1b;
对同一组权值{w1 ,w2 , …… , wn}&＃xff0c;存在不同构的哈夫曼树&＃xff1a;
对一组权值{ 1, 2 , 3, 3 }&＃xff0c;不同构的两棵哈夫曼树&＃xff1a;

哈夫曼编码