哈夫曼树的定义 假设有n个权值,构造有n个叶子结点的二叉树,每个叶子结点的权值是n个权值之一,这样的二叉树可以构造很多棵,其中必有一棵是带权路径长度最小的,这棵二叉树就称为最优二叉树或哈夫曼树。 构建哈夫曼树的方式 假设有7个树(一个节点),其权重分别为1、2、3、4、5、6、7。 找到两个权重最小的树1和2。 1 和2 分别作为新树的左右子树,新树的根结点权重为1 2 =3。剩下的树:3、3、4、5、6、7。 再找到两个最小的树,分别是3和3构成新树,新树权重为6。剩下的树为:6、4、5、6、7。 重复步骤2和3…