Question

数据结构之最优二叉树

Answer 1

基本术语

　　路径（Path）和路径长度 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径 路径上的分支数目称做路径长度 　　树的路径长度 从树根到每一结点的路径长度之和 　　树的带权路径长度（Weighted Path Length of Tree） 树中所有叶结点的带权路径长度之和 记作

　　Huffman树 又称最优二叉树 它是n个带树叶子结点构成的所有二叉树中 带权路径长度WPL最小的二叉树

构造Huffman树

　　Huffman算法 　　( ) 根据给定的n个权值{w w … wn}构成n棵二叉树的集合F={T T … Tn} 其中每棵二叉树Ti中只有一个带权为wi的根结点 其左右子树均空 　　( ) 在F中选取两棵根结点的权值最小的树作为左右子树构成一棵新的二叉树 且置新的二叉树的根结点的权值为其左 右子树上根结点的权值之和 　　( ) 在F中删除这两棵树 同时将新得到的二叉树加入F中 　　( ) 重复( )和( ) 直到F只含一棵树为止 这棵树便是 　　Huffman树 　　Huffman树的存储结构

　　 　　实现Huffman算法

lishixinzhi/Article/program/sjjg/201311/22685