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树