哈弗曼树

哈弗曼树是一种带权路径长度最小的二叉树，它是由左子树和右子树构成的。每个节点的权值是该点到根节点的路径长度与该节点上标记的权值的乘积。构建哈弗曼树的过程包括：根据给定的n个权值{w1,w2,...,wn}构造n棵只有一个根节点的二叉树，并利用最小堆(或优先队列)求出结点的权值。然后，从最小堆中取出两个权值最小的结点，作为左右子树的根节点，并将这两个权值合并为新节点的权值。重复这个过程，直到所有的结点都被合并到一个树中。最后，这个树就是哈弗曼树。