什么是完全二叉树定义,huffman什么意思

目的根据给定的加权叶节点计算Huffman树，即最优二叉树。 那是所有叶节点的权值级数之和最小

算法特点Huffman算法思想直观，让权重最小的叶节点位于更底层，而权重较高的叶节点尽量在高层

请小心。 最佳二叉树中不存在只有一个儿子的节点。

算法要求给定一些叶节点和它们的权重，构成最优二叉树，直接的想法当然是把权重小的配对，作为其父节点的两个儿子。

但是，问题也有可能发生层数最少的二叉树不是最佳的情况。 这是因为，还可以使权重小的节点下沉，使权重高的节点上浮。

因此，Huffman算法在每次的确找到两个权重最小的节点，组合成为父节点。但是下一步就是用这个父节点代替原先两个小权重节点的位置，继续挑选两个权重最小的节点这样，如果生成的父节点的权重保持较小，则可能继续成为子节点，最终生成的二叉树也将是最佳的。

在算法示例中，指定一组子节点及其权重。

FOERGT235447的两个最小节点分别为f和o，组合为fo(5)

FOERGT55447的两个最小节点分别为r和g，组合为rg(8)

FOERGT5587的两个最小节点分别是FO和e，并且耦合到Foe(10 )

FOERGT1087的两个最小节点分别为RG和t，组合成rgt(15 )

FOERGT1015将这两个子树组合在一起，成为最佳的二叉树。

过程如下图所示。