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

    2019-09-24 13:44:05
    题目描述: 根据给定的叶结点字符及其对应的...第二行为一个字符串,包含n个字符,每个字符对应一个叶子结点,第三行为每个叶子结点的概率(即权值),要求根据各叶结点构造哈夫曼树构造哈夫曼树的原则是先两个最...
    题目描述:
    根据给定的叶结点字符及其对应的权值创建哈夫曼树。
    输入:
    第一行为叶子结点的数目n(1<=n<=100)。第二行为一个字符串,包含n个字符,每个字符对应一个叶子结点,第三行为每个叶子结点的概率(即权值),要求根据各叶结点构造哈夫曼树。构造哈夫曼树的原则是先两个最小的,构造一个父结点,其中最小的结点为左孩子,次小的为右孩子,如果两个最小的叶结点相等,则取排在前一个位置的为左孩子。
    输出:
    哈夫曼树的权值,左孩子,右孩子及其对应的父亲,相邻数据之间用空格隔开;
    输入样例:
    5
    abcde
    15 25 15 20 25
    输出样例:
    15 0 0 6
    25 0 0 7
    15 0 0 6
    20 0 0 7
    25 0 0 8
    30 1 3 8
    45 4 2 9
    55 5 6 9

    100 7 8 0


    思路:就是选择两个最小的结点,并且没有父亲的结点。不断的拼凑就可以,

      

         主要点:

              相同的结点权值:选择下标小的,在前面。

              交换的时候:第二个最小的可以直接赋值,第一个交换的时候,要判断第二个与第一个的之前的判断,在将新的值赋给第一个结点。


    代码如下:

    import java.util.Scanner;
    
    public class buildHuffmanTree {
    
    	public static class huffmanTreeNode {
    		int father;
    		int lchild;/// 最小的
    		int rchild;/// 最大的
    		int value;
    	}
    
    	public static void main(String[] args) {
    
    		Scanner sc = new Scanner(System.in);
    
    		huffmanTreeNode huffmanTreeArray[];
    		int number;
    		String ti;
    		number = sc.nextInt();
    		ti = sc.next();
    		huffmanTreeArray = new huffmanTreeNode[number * 2 + 1];
    		for (int i = 0; i <= number * 2; i++)
    			huffmanTreeArray[i] = new huffmanTreeNode();
    
    		for (int i = 1; i <= number; i++) {
    			huffmanTreeArray[i].father = 0;
    			huffmanTreeArray[i].lchild = 0;
    			huffmanTreeArray[i].rchild = 0;
    			huffmanTreeArray[i].value = sc.nextInt();
    		}
    		int min, max, t;
    		for (int i = 1; i <= number - 1; i++) {
    			/// 刚开始找两个没有父亲的作为最小最大的初始值
    			min = max = t = 0;
    			for (int j = 1; j <= number + i - 1; j++) {
    				if (huffmanTreeArray[j].father != 0)
    					continue;
    				if (t == 0)
    					max = j;
    				else
    					min = j;
    				t = t + 1;
    				if (t == 2)
    					break;
    			}
    
    			/// 先判断是不是要交换一下位置
    			if (huffmanTreeArray[min].value > huffmanTreeArray[max].value) {
    				int k = min;
    				min = max;
    				max = k;
    			}
    			/// 下面就是正确的寻找最小和第二小的
    			for (int j = 1; j <= number + i - 1; j++) {
    				if (huffmanTreeArray[j].father != 0 || j == min || j == max)
    					continue;
    				if (huffmanTreeArray[j].value < huffmanTreeArray[min].value) {
    					if (huffmanTreeArray[min].value <=  huffmanTreeArray[max].value)
    						max = min;
    					min = j;
    				} else if (huffmanTreeArray[max].value > huffmanTreeArray[j].value)
    					max = j;
    			}
    			/// 现在就是开始赋予孩子和父亲
    			huffmanTreeArray[min].father = number + i;
    			huffmanTreeArray[max].father = number + i;
    			huffmanTreeArray[number + i].value = huffmanTreeArray[max].value + huffmanTreeArray[min].value;
    			if (huffmanTreeArray[max].value == huffmanTreeArray[min].value) {
    				if (max < min) {
    					huffmanTreeArray[number + i].rchild = min;
    					huffmanTreeArray[number + i].lchild = max;
    				} else {
    					huffmanTreeArray[number + i].rchild = max;
    					huffmanTreeArray[number + i].lchild = min;
    				}
    			} else {
    				if (huffmanTreeArray[max].value > huffmanTreeArray[min].value) {
    					huffmanTreeArray[number + i].lchild = min;
    					huffmanTreeArray[number + i].rchild = max;
    				} else {
    					huffmanTreeArray[number + i].lchild = max;
    					huffmanTreeArray[number + i].rchild = min;
    				}
    			}
    		}
    
    		/// 下面就是开始输出
    		for (int i = 1; i <= number * 2 - 1; i++)
    			System.out.println(String.format("%d %d %d %d", huffmanTreeArray[i].value, huffmanTreeArray[i].lchild,
    					huffmanTreeArray[i].rchild, huffmanTreeArray[i].father));
    	}
    }

    转载于:https://www.cnblogs.com/new-zjw/p/8540903.html

    展开全文
  • 树的带权路径长度WPL 哈夫曼树构造 哈夫曼树性质 哈夫曼编码 试题

    带权路径长度

    在这里插入图片描述

    树的带权路径长度WPL

    在这里插入图片描述

    哈夫曼树

    在这里插入图片描述

    哈夫曼树构造

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    哈夫曼树性质

    在这里插入图片描述

    哈夫曼编码

    在这里插入图片描述
    固定长度编码
    在这里插入图片描述
    可变长编码
    在这里插入图片描述
    前缀编码
    在这里插入图片描述
    在这里插入图片描述
    固定长度编码、可变长编码、前缀编码、哈夫曼编码
    在这里插入图片描述
    思维倒图
    在这里插入图片描述


    试题
    在这里插入图片描述
    在这里插入图片描述


    在这里插入图片描述
    在这里插入图片描述

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

    2014-06-26 14:39:31
    讲解构造哈夫曼树的过程,超详细。 对于不理解哈夫曼树的过程构造的新人来讲,十分有用!
  • 构造哈夫曼树生成哈夫曼编码 参考 程序员小灰-漫画:什么是 “哈夫曼树” ? 程序员小灰-漫画:“哈夫曼编码” 是什么鬼? 编写一个程序exp7-5.cpp,构造一棵哈夫曼树, 输出对应的哈夫曼编码和平均查找长度, 并对...

    构造哈夫曼树生成哈夫曼编码

    参考
    程序员小灰-漫画:什么是 “哈夫曼树” ?
    程序员小灰-漫画:“哈夫曼编码” 是什么鬼?

    编写一个程序exp7-5.cpp,构造一棵哈夫曼树,
    输出对应的哈夫曼编码和平均查找长度,
    并对下表(表7.8)所示的数据进行验证。
    
    表7.8 单词及出现的频度
    单词	The	of	a	to	and	in	that	he	is	at	on	for	His	are	be
    频度	1192	677	541	518	462	450	242	195	190	181	174	157	138	124	123
    
    #include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    
    struct TreeNode{
        int weight=0;
        string word;
        string huffmancode;
        struct TreeNode* lChild;
        struct TreeNode* rChild;
    };
    
    TreeNode *w_node[15];
    
    class cmp{
        public:
        bool operator()(const TreeNode *n1,const TreeNode *n2)const{
            return n1->weight > n2->weight;
        }
    };
    
    //创建哈夫曼树
    TreeNode* CreateHuffmanTree(int w[],string s[]){
        priority_queue<TreeNode*,vector<TreeNode*>,cmp > q;
        for(int i = 0;i < 15; i++){
            TreeNode* node = new TreeNode;
            node->lChild = node->rChild = NULL;
            node->weight = w[i];
            node->word = s[i];
            q.push(node);
            w_node[i] = node;  //记录下原本的点
        }
        
        while (q.size()>1)
        {
            TreeNode *parent = new TreeNode;
            parent->lChild = q.top();
            q.pop();
            parent->rChild = q.top();
            q.pop();
            parent->weight = parent->lChild->weight + parent->rChild->weight;
            q.push(parent);
        }
        return q.top();
    }
    
    //递归编码
    void encode(TreeNode *node,string code){
        if(node==NULL)return;
        node->huffmancode = code;
        encode(node->lChild,code+'0');
        encode(node->rChild,code+'1');
    }
    
    //WPL
    int getWPL(TreeNode *node,int depth){
        if(node->lChild==NULL&&node->rChild==NULL){
            return node->weight*depth;
        }
        return getWPL(node->lChild,depth+1)+getWPL(node->rChild,depth+1);
    }
    
    int main(){
        int weight[] = {1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123};
        string s[] = {"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"};
        TreeNode *root = CreateHuffmanTree(weight,s);
        encode(root,"");
        for(int i=0;i<15;i++){
            cout<<w_node[i]->word<<":"<<w_node[i]->huffmancode<<endl;
        }
        cout<<"平均查找长度:"<<getWPL(root,0);
        system("pause");
        return 0;
    }
    
    展开全文
  • C语言构造哈夫曼树、哈夫曼编码

    千次阅读 2019-04-22 20:20:15
    1.构造哈夫曼树 #include <stdio.h> #include <stdlib.h> #define MAXVALUE 10000 /* 节点最大权值 */ #define MAXLEAF 30 /* 哈夫曼树叶子节点最大个数 */ #define MAXNODE MAXLEAF * 2 - 1 /* ...

    四个叶子节点{1,3,5,5},构造Huffman树,并进行Huffman编码
    设编码时:左分支为‘0’,右分支为‘1’

    0
    1
    0
    1
    0
    1
    14
    5
    9
    4
    5
    1
    3
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAXVALUE 10000          /* 节点最大权值 */
    #define MAXLEAF 30              /* 哈夫曼树叶子节点最大个数 */
    #define MAXNODE MAXLEAF * 2 - 1 /* Huffman树中节点总数 */
    typedef struct 
    {
        int weight;                 /* 节点权值 */
        int parent;                 /* 无双亲节点时为-1,否则为双亲节点下标 */
        int lchild;                 /* 无左孩子时为-1,否则为左孩子下标 */
        int rchild;                 /* 无右孩子时为-1,否则为右孩子下标 */
    }HNode, HuffmanTree[MAXNODE];
    
    typedef struct CodeNode/* 编码表的存储结构 */
    {
        int weight;/* 存放要表示的符号 */
        char *code;/* 存放相应符号编码 */
    }CodeNode, HuffamanCode[MAXLEAF];
    
    
    /**
     * @description: 构造Huffman树
     * @param w[]:传递n个叶子节点权值
     *               n:叶子节点个数
     */
    void CreateHuffmanTree(HuffmanTree HTree, int w[], int n)
    {
        /**
         * min1: 集合中最小权值
         * min1: 集合中次小权值 
         * index1:最小权值节点下标
         * index2:次小权值节点下标
         */
        int i, j, min1, min2, index1, index2;
    
        for (i = 0; i < 2 * n - 1; i++)/* 树中节点初始化 */
        {
            HTree[i].weight = 0;
            HTree[i].parent = -1;
            HTree[i].lchild = -1;
            HTree[i].rchild = -1;
        }
        
        for (i = 0; i < n; i++)
            HTree[i].weight = w[i];
        printf("Huffman树初态\nindex | weight | parent | lchild | rchild\n");
        for (int i = 0; i < 2 * n - 1; i++)
        {
            printf("%3d%9d%9d%9d%9d\n", 
                    i, HTree[i].weight, HTree[i].parent, HTree[i].lchild, HTree[i].rchild);
        }
        /************************************************
         * 设n0(叶子节点)、n1(分支为1)、n2(分支为2)分别为二叉树中度为0、1、2的节点个数,
         * n为总节点个数,则 n = n0 + n1 + n2;
         * 设二叉树分支数为B,则 B = n + 1, B = n1 + 2 * n2;
         * 联立上述三个方程--->n0 = n2 + 1;
         * 
         * Huffman树中只有度为0、2的节点:
         * n = n0 + n1 + n2 = n0 + n2;
         * n0 = n2 + 1;
         * Huffman树中:n = 2 * n0 - 1.
         ************************************************/
        for (i = 0; i < n - 1; i++)/* 构造除n个叶子节点外的其余 n - 1 个双亲节点 */
        {
            min1 = min2 = MAXVALUE;
            index1 = index2 = 0;
    
            for (j = 0; j < n + i; j++)
            {
                if (HTree[j].weight < min1 && HTree[j].parent == -1)
                {/* 若节点权值比min1小且该节点无双亲节点,则更新最小节点 */
                    min2 = min1; index2 = index1; /* 更新次小节点 */
                    index1 = j;
                    min1 = HTree[j].weight;
                }
                else if (HTree[j].weight < min2 && HTree[j].parent == -1)
                {/* 若 min1 < 节点权值 < min2 且该节点无双亲节点,则更新次小节点 */
                    index2 = j;
                    min2 = HTree[j].weight;
                }
            }
    
            HTree[index1].parent = n + i;
            HTree[index2].parent = n + i;
            HTree[n+i].weight = HTree[index1].weight + HTree[index2].weight;
            HTree[n+i].lchild = index1;
            HTree[n+i].rchild = index2;
        }
    }
    
    /**
     * @description: 从叶子节点-->根节点逆向搜索,若当前节点是其双亲左孩子,置‘0’,否则置‘1’
     * @param:HTree:构造好的Huffman树
     *         HCode:Huffman树叶子节点编码
     *         n:叶子节点个数 
     */
    void HuffmanCoding(HuffmanTree HTree, HuffamanCode HCode, int n)
    {
        char *cd;
        int i, child, parent, start;
    
        /* n个叶子节点的Huffman树,叶子节点最长路径为 n-1,加上'\0',共n个空间 */
        cd = (char *)malloc(n * sizeof(char));
        cd[n-1] = '\0';                 
    
        for (i = 0; i < n; i++)         /* 求n个叶子节点的Huffman编码 */
        {
            start = n - 1;
            child = i;                  /* child:当前节点下标 */
            parent = HTree[i].parent;   /* parent:当前节点双亲节点下标 */
    
            while (parent != -1)        /* 若未搜寻至根节点,则一直循环 */
            {
                start--;
                if (HTree[parent].lchild == child) 
                    cd[start] = '0';    /* 左孩子,置‘0’ */
                else 
                    cd[start] = '1';    /* 右孩子,置‘1’ */
               
                child = parent;         /* 旧双亲节点作为新孩子节点 */
                parent = HTree[parent].parent;/* 旧双亲节点的双亲节点作为新双亲节点 */
            }
            
            HCode[i].code = (char *)malloc((n - start) * sizeof(char));
            HCode[i].weight = HTree[i].weight;
            strcpy(HCode[i].code, &cd[start]);
        }
        free(cd);
    }
    
    int main(void)
    {
        int w[] = {1, 3, 5, 5}, n = 4;
        HuffmanTree ht;
        HuffamanCode hc;
    
        CreateHuffmanTree(ht, w, n);
        printf("Huffman树终态\nindex | weight | parent | lchild | rchild\n");
        for (int i = 0; i < 2 * n - 1; i++)
        {
            printf("%3d%9d%9d%9d%9d\n", 
                    i, ht[i].weight, ht[i].parent, ht[i].lchild, ht[i].rchild);
        }
        
        HuffmanCoding(ht, hc, n);
        printf("Huffman编码\n节点值  编码\n");
        for (int i = 0; i < n; i++)
        {
            printf("%4d\t%s\n", hc[i].weight, hc[i].code);
        } 
        
        return 0;
    }
    

    在这里插入图片描述

    展开全文
  • c语言构造哈夫曼树-哈夫曼编码

    万次阅读 多人点赞 2018-12-05 14:59:59
    构造哈夫曼树 首先,我们需要了解哈夫曼树是什么: 一.相关知识点 路径: 路径是指从一个节点到另一个节点的分支序列。 路径长度: 指从一个节点到另一个结点所经过的分支数目。 ,从根节点到a的分支数目是2, 数...
  • 这里主要是想处理一下自己写构造哈夫曼树时遇到的问题。 一开始,我是建了一个存结构体指针的优先队列,以权值为标准从小到大排序,然后选最小和次小节点组成父节点。但是运行后权值的排序是乱的。既不是从小到大也...
  • 构造哈夫曼树,并生成编码 构造哈夫曼树,并生成编码
  • 今天我们要共同学习的是c语言构造哈夫曼树-哈夫曼编码构造哈夫曼树首先,我们需要了解哈夫曼树是什么:相关知识点路径: 路径是指从一个节点到另一个节点的分支序列。路径长度: 指从一个节点到另一个结点所经过的...
  •  本算法采用二叉链表来构造二叉树,并用递归算法求哈夫曼编码构造哈夫曼树概念:哈夫曼树为带权路径最短的二叉树构造过程:每次选出最小的两个顶点,分别作为左右分支,构造出父节点,父节点权值为两顶点之和,...
  • 统计下面一段英文的不同字符个数和每个字符的出现频率,利用统计数据构造构造哈夫曼树和哈夫曼编码 The Chinese official said he viewed the Trump Presidency not as an aberration but as the product of a ...
  • 在作业本上分别针对权值集合W=(6,5,3,4,60,18,77)和W=(7,2,4,5,8)构造哈夫曼树 提交构造过程的照片 完成情况: 知识点 假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2...
  • 使用最小堆构造哈夫曼树

    千次阅读 2019-02-27 21:16:28
    哈夫曼树: 路径:从树根到某个节点的路径为根节点到该节点所经过的一个节点序列。路径长度为路径所含的分支数。 树的路径长度:从根节点到其他所有...构造哈夫曼树的算法: 将n个带有权值且只有一个叶节点的二...
  • 优先队列构造哈夫曼树 借用博主的图用于知识复习,感谢,侵删 求哈夫曼树的权值,由于优先队列默认采用大顶堆,如若采用小顶堆,按照 priority_queue<typename vecotr<typename> greater<typename> ...
  • 构造哈夫曼树并层序遍历 #include<iostream> #include<algorithm> using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int ElemType; #define MAXSIZE 100 typedef struct...
  • 构造哈夫曼树的算法

    千次阅读 2016-02-02 18:43:44
    ②、构造哈夫曼树的算法; ③、编写一个存放每个节点哈夫曼编码的类型; ④、编写哈夫曼树求对应的哈夫曼编码的算法; ⑤、编写主函数。 代码如下: #include #include #include #include //①: typedef ...
  • 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
  • 统计下面一段英文的不同字符个数和每个字符的出现频率,利用统计数据构造构造哈夫曼树和哈夫曼编码 The Chinese official said he viewed the Trump Presidency not as an aberration but as the product of a ...
  • 树12——构造哈夫曼树并输出哈夫曼编码

    万次阅读 多人点赞 2019-04-04 21:00:23
    为一组权值分别为2、4、7、15的结点序列构造一棵哈夫曼树,然后输出相应的哈夫曼编码。 为了便于设计,可利用一个二维数组实现哈夫曼树的算法。因为需要保存字符的权重、双亲结点位置、左孩子结点位置和右孩子结点...
  •  本算法采用二叉链表来构造二叉树,并用递归算法求哈夫曼编码构造哈夫曼树概念:哈夫曼树为带权路径最短的二叉树构造过程:每次选出最小的两个顶点,分别作为左右分支,构造出父节点,父节点权值为两顶点之和,...
  • 构造哈夫曼树的算法模拟。数据结构有个重要的算法。共同学习

空空如也

空空如也

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

构造哈夫曼树