《题目》：假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的 频率分别为：{0.19, 0.21, 0.02, 0.03, 0.06, 0.07, 0.1, 0.32}.

要求：画出哈夫曼树

哈夫曼树的构造

分析：我们这里直接将小数整数化，容易看出大小来。

①8个结点的权值大小如下：

②从19，21，2，3，6，7，10，32中选择两个权小结点。选中2，3。同时算出这两个结点的和5。

③从19，21，6，7，10，32，5中选出两个权小结点。选中5，6。同时计算出它们的和11。

④从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。

注：这时选出的两个数字都不是原来的二叉树里面的结点，所以要另外开一棵二叉树。

⑤从19，21，32，11，17中选出两个权小结点。选中11，17。同时计算出它们的和28。

⑥从19，21，32，28中选出两个权小结点。选中19，21。同时计算出它们的和40。 另起一颗二叉树。

⑦从32，28， 40中选出两个权小结点。选中28，32。同时计算出它们的和60。

⑧从 40， 60中选出两个权小结点。选中40，60。同时计算出它们的和100。 好了，此时哈夫曼树已经构建好了。

哈夫曼树的内容这里不作解释，请自己搜索。下面给出哈夫曼树构造过程的 Java 实现。 结点类： 1./**2. * 二叉树节点3. */4.public class Node implements Comparable {5.6. private int value;7.8. private Node leftChild;9.10. private Node rightChild;11
哈夫曼树的内容这里不作解释，请自己搜索。下面给出哈夫曼树构造过程的 Java 实现。
结点类：1./**2. * 二叉树节点3. */4.public class Node implements Comparable {5.6.    private int value;7.8.    private Node leftChild;9.10.    private Node rightChild;11.12.    public Node(int value) {13.        this.value = value;14.    }15.16.    public int getValue() {17.        return value;18.    }19.20.    public void setValue(int value) {21.        this.value = value;22.    }23.24.    public Node getLeftChild() {25.        return leftChild;26.    }27.28.    public void setLeftChild(Node leftChild) {29.        this.leftChild = leftChild;30.    }31.32.    public Node getRightChild() {33.        return rightChild;34.    }35.36.    public void setRightChild(Node rightChild) {37.        this.rightChild = rightChild;38.    }39.40.    public String toString(int level) {41.        String indent = "";42.        for (int i = 0; i < level; i++) {43.            indent += "  ";44.        }45.46.        return indent + value + "/n" +47.                (leftChild != null ? leftChild.toString(level + 1) : "") +48.                (rightChild != null ? rightChild.toString(level + 1) : "");49.    }50.51.    public int compareTo(Object o) {52.        Node that = (Node) o;53.        double result = this.value - that.value;54.        return result > 0 ? 1 : result == 0 ? 0 : -1;55.    }56.}
哈夫曼树构造类：1.public class HuffmanTreeBuilder {2. 3.    public static void main(String[] args) {4.        List nodes = Arrays.asList(5.                new Node(40),6.                new Node(8),7.                new Node(10),8.                new Node(30),9.                new Node(10),10.                new Node(2)11.        );12. 13.        Node node = HuffmanTreeBuilder.build(nodes);14.        System.out.println(node.toString(0));15.    }16. 17.    /**18.     * 构造哈夫曼树19.     *20.     * @param nodes 结点集合21.     *22.     * @return 构造出来的树的根结点23.     */24.    private static Node build(List nodes) {25.        nodes = new ArrayList(nodes);26.        sortList(nodes);27.        while (nodes.size() > 1) {28.            createAndReplace(nodes);29.        }30.        return nodes.get(0);31.    }32. 33.    /**34.     * 组合两个权值最小结点，并在结点列表中用它们的父结点替换它们35.     *36.     * @param nodes 结点集合37.     */38.    private static void createAndReplace(List nodes) {39.        Node left = nodes.get(nodes.size() - 1);40.        Node right = nodes.get(nodes.size() - 2);41.        Node parent = new Node(left.getValue() + right.getValue());42.        parent.setLeftChild(left);43.        parent.setRightChild(right);44.        nodes.remove(nodes.size() - 1);45.        nodes.remove(nodes.size() - 1);46.        nodes.add(parent);47.        sortList(nodes);48.    }49. 50.    /**51.     * 将结点集合由大到小排序52.     *53.     * @param nodes 结点集合54.     */55.    private static void sortList(List nodes) {56.        Collections.sort(nodes);57.    }58.}
说明：
1、HuffmanTreeBuilder 的 25 行新建了一个结点集合，以免对参数进行修 改。
2、createAndReplace 方法首先获取末尾两个节点，然后构造它们的父结点 ，接着在结点集合中将这两个节点删除，把父结点加进去。

哈夫曼树的构造过程可以详见推荐博客：哈夫曼树以及哈夫曼编码的构造步骤

建议先看完推荐博客中的文字说明，或者自己找一本数据结构的树来仔细阅读以下关于哈夫曼树的构造

然后再来看下面给出的code

这里给出的是关于哈夫曼树的构造代码：

#include <cstdio>
#include <cstring>
using namespace std;

typedef struct {
    int weight;         // 结点权值?
    int parent, lc, rc; // 双亲结点和左 右子节点
} HTNode, *HuffmanTree;

void Select(HuffmanTree &HT, int n, int &s1, int &s2)
{
    int minum;      // 定义一个临时变量保存最小值?
    for(int i=1; i<=n; i++)     // 以下是找到第一个最小值
    {
        if(HT[i].parent == 0)
        {
            minum = i;
            break;
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(HT[i].parent == 0)
            if(HT[i].weight < HT[minum].weight)
                minum = i;
    }
    s1 = minum;
    // 以下是找到第二个最小值，且与第一个不同
    for(int i=1; i<=n; i++)     
    {
        if(HT[i].parent == 0 && i != s1)
        {
            minum = i;
            break;
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(HT[i].parent == 0 && i != s1)
            if(HT[i].weight < HT[minum].weight)
                minum = i;
    }
    s2 = minum;
}

void CreatHuff(HuffmanTree &HT, int *w, int n)
{
    int m, s1, s2;
    m = n * 2 - 1;  // 总结点的个数
    HT = new HTNode[m + 1]; // 分配空间
    for(int i=1; i<=n; i++) // 1 - n 存放叶子结点，初始化
    {
        HT[i].weight = w[i];
        HT[i].parent = 0;
        HT[i].lc = 0;
        HT[i].rc = 0;
    }
    for(int i=n+1; i<=m; i++)   // 非叶子结点的初始化
    {
        HT[i].weight = 0;
        HT[i].parent = 0;
        HT[i].lc = 0;
        HT[i].rc = 0;
    }
    
    printf("\nthe HuffmanTree is: \n");

    for(int i = n+1; i<=m; i++)     // 创建非叶子节点，建哈夫曼树
    {   // 在HT[1]~HT[i-1]的范围内选择两个parent为0且weight最小的两个结点，其序号分别赋值给 s1 s2
        Select(HT, i-1, s1, s2);
        HT[s1].parent = i;  // 删除这两个结点
        HT[s2].parent = i;
        HT[i].lc = s1;      // 生成新的树，左右子节点是 s1和s2
        HT[i].rc = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;   // 新树的权�?
        printf("%d (%d, %d)\n", HT[i].weight, HT[s1].weight, HT[s2].weight);
    }
    printf("\n");
}

int main()
{
    HuffmanTree HT;
    
    int *w, n, wei;
    printf("input the number of node\n");
    scanf("%d", &n);
    w = new int[n+1];
    printf("\ninput the %dth node of value\n", n);

    for(int i=1; i<=n; i++)
    {
        scanf("%d", &wei);
        w[i] = wei;
    }
    CreatHuff(HT, w, n);



    return 0;
}

 

    今天做题的时候，遇到了一个关于哈夫曼树的题，由于一直不是很明白哈夫曼树的构造过程，所以找了很多资料都不是特别清楚的，直到我遇到了这篇文章，哈哈，在此分享给大家哦！




注意：哈夫曼树并不唯一，但带权路径长度一定是相同的。




（1）8个结点的权值大小如下：



（2）从19，21，2，3，6，7，10，32中选择两个权小结点。选中2，3。同时算出这两个结点的和5。







（3）从19，21，6，7，10，32，5中选出两个权小结点。选中5，6。同时计算出它们的和11。



（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。

（BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）




（5）从19，21，32，11，17中选出两个权小结点。选中11，17。同时计算出它们的和28。



（6）从19，21，32，28中选出两个权小结点。选中19，21。同时计算出它们的和40。另起一颗二叉树。



（7）从32，28， 40中选出两个权小结点。选中28，32。同时计算出它们的和60。  



（8）从 40， 60中选出两个权小结点。选中40，60。同时计算出它们的和100。 好了，此时哈夫曼树已经构建好了。






    这是原作者的链接哦，我觉得还不错呢，大家可以去看看的！


注意：哈夫曼树并不唯一，但带权路径长度一定是相同的。




（1）8个结点的权值大小如下：



（2）从19，21，2，3，6，7，10，32中选择两个权小结点。选中2，3。同时算出这两个结点的和5。







（3）从19，21，6，7，10，32，5中选出两个权小结点。选中5，6。同时计算出它们的和11。



（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。

（BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）




（5）从19，21，32，11，17中选出两个权小结点。选中11，17。同时计算出它们的和28。



（6）从19，21，32，28中选出两个权小结点。选中19，21。同时计算出它们的和40。另起一颗二叉树。



（7）从32，28， 40中选出两个权小结点。选中28，32。同时计算出它们的和60。  



（8）从 40， 60中选出两个权小结点。选中40，60。同时计算出它们的和100。 好了，此时哈夫曼树已经构建好了。



这是原博文的链接哦！点击打开链接


注意：哈夫曼树并不唯一，但带权路径长度一定是相同的。




（1）8个结点的权值大小如下：



（2）从19，21，2，3，6，7，10，32中选择两个权小结点。选中2，3。同时算出这两个结点的和5。







（3）从19，21，6，7，10，32，5中选出两个权小结点。选中5，6。同时计算出它们的和11。



（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。

（BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）




（5）从19，21，32，11，17中选出两个权小结点。选中11，17。同时计算出它们的和28。



（6）从19，21，32，28中选出两个权小结点。选中19，21。同时计算出它们的和40。另起一颗二叉树。



（7）从32，28， 40中选出两个权小结点。选中28，32。同时计算出它们的和60。  



（8）从 40， 60中选出两个权小结点。选中40，60。同时计算出它们的和100。 好了，此时哈夫曼树已经构建好了。