Huffman树 构造 Huffman树的一般规律 根据给定的n个权值{w1,w2,…wn},构成n棵二叉 树的集合F={T,T2,Tn},其中每棵二叉树T中只有 个带权为w的根结点,其左右子树均空 2)在F中选取两棵根结点的权值最小的树作为左右 子树构造一棵新的二叉树,且置新的二叉树的根结 点的权值为其左右子树上根结点的权值之和 3)在F中删除这两棵树,同时将新得到的二叉树加 入F中 重复2)和3),直到F中只含一棵树为止。此时得到的 便是 Huffman树
Huffman树 • 构造Huffman树的一般规律 – 1) 根据给定的n个权值{w1 ,w2 ,…wn}，构成n棵二叉 树的集合F={T1 ,T2 ,…Tn}，其中每棵二叉树Ti中只有 一个带权为wi的根结点，其左右子树均空 – 2) 在F中选取两棵根结点的权值最小的树作为左右 子树构造一棵新的二叉树，且置新的二叉树的根结 点的权值为其左右子树上根结点的权值之和 – 3) 在F中删除这两棵树，同时将新得到的二叉树加 入F中 – 重复2)和3)，直到F中只含一棵树为止。此时得到的 便是Huffman树
Huffman树 ·如:已知事件abcd对应的权值集合w={7,5,24},试 设计对应 Huffman树 a(b a stepl 6 c d step2 24 step 2 4 step4 4
Huffman树 • 如：已知事件a,b,c,d对应的权值集合w={7,5,2,4}，试 设计对应Huffman树 a b c d 7 5 2 4 step1 c d 2 4 6 a b 7 5 step2 a 7 c d 2 4 b 6 5 11 step3 a 7 c d 2 4 b 6 5 11 step4 18