哈夫曼树

哈夫曼树是一种带权路径长度最短的二叉树，它是由哈夫曼提出的。在计算机科学中，哈夫曼树是一种常用的数据结构，用于编码和压缩。它的构造过程是：首先将给定的n个权值看成n个叶子结点，构成一棵二叉树的集合T；然后从集合T中选出两个根结点的权值最小的树作为左、右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和；再从集合T中删除这两棵树，同时将新得到的二叉树加入集合T中；重复第二步，直到T只含一个结点为止。最后这棵二叉树即为所求得的哈夫曼树。