哈夫曼树怎么画,哈夫曼编码的最优子结构性质怎么证明

哈夫曼树怎么画,哈夫曼编码的最优子结构性质怎么证明

哈夫曼编码一般我们理解为将字符用01表示，由于不同字符出现的次数不一样，我们将出现次数多的字符编码短一些，次数少的编码长一些。哈夫曼编码的设计原理是先构造哈夫曼树，哈夫曼树构造规则是选择两个权值最小的结点构造为树，递归这一过程直到一棵树位置，所有信源对应的结点都是叶子结点。然后根据哈夫曼树，构造编码的时候，为每一个叶子结点设计编码。往左默认为0，往右默认为1，所以每个叶子结点都有一个编码，当然信源都有哈夫曼编码。这个证明题不知道要考什么。