精华内容
下载资源
问答
  • 哈夫曼树的构造

    2020-04-11 20:09:43
    《题目》:假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的...哈夫曼树的构造 分析:我们这里直接将小数整数化,容易看出大小来。 ①8个结点的权值大小如下: ②从19,21,2,3,6,7,10,32中选择两个权小结点...

    《题目》:假设用于通信的电文由字符集{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 ...

    哈夫曼树的内容这里不作解释,请自己搜索。下面给出哈夫曼树构造过程的 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 方法首先获取末尾两个节点,然后构造它们的父结点 ,接着在结点集合中将这两个节点删除,把父结点加进去。

    展开全文
  • 哈夫曼树的构造(C语言实现)

    万次阅读 多人点赞 2018-12-06 17:48:27
    哈夫曼树的构造过程可以详见推荐博客:哈夫曼树以及哈夫曼编码的构造步骤 建议先看完推荐博客中的文字说明,或者自己找一本数据结构的树来仔细阅读以下关于哈夫曼树的构造 然后再来看下面给出的code 这里给出的是...

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

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

    然后再来看下面给出的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;
    }

     

    展开全文
  • 哈夫曼树的构造过程

    万次阅读 多人点赞 2017-07-25 23:42:57
    今天做题的时候,遇到了一个关于哈夫曼树的题,由于一直不是很明白哈夫曼树的构造过程,所以找了很多资料都不是特别清楚的,直到我遇到了这篇文章,哈哈,在此分享给大家哦! 注意:哈夫曼树并不唯一,但...

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



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


    (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。 好了,此时哈夫曼树已经构建好了。

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,853
精华内容 741
关键字:

哈夫曼树的构造