精华内容
下载资源
问答
  • 哈夫曼树的存储结构原理
    2019-09-23 23:32:06
    1. 哈夫曼树的构造
        给定N个权值分别为w1, w2, ..., Wn的节点。构造哈夫曼树的算法描述如下:
        1)将这N个结点分别作为N棵树仅含一个结点的二叉树,构成森林F.
        2)构造一个新节点,并从F中选取两棵根结点权值最小的树作为新节点的左、右子树,并且将新节点的权值置为左、右子树上根结点的权                    
        值之和。
        3)从F中删除刚才选出的两棵树,同时将新得到的树加入F中。
        4)重复步骤2和3,直至F中只剩下一棵树为止。
    2. 哈夫曼编码
           哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码,它是可变长度编码。可变长编码即可以对待处理字符串中不同字符使用不等长的二进制位表示,可变长编码比固定长度编码好很多,可以对频率高的字符赋予短编码,而对频率较低的字符则赋予较长一些的编码,从而可以使平均编码长度减短,起到压缩数据的效果。
           哈夫曼编码是前缀编码。如果没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码。对前缀编码的解码也是相对简单的,因为没有一个码是另一个编码的前缀,所以可以识别出第一个编码,将它翻译为原码,再对余下的编码文件重复同样操作。
            哈夫曼编码首先要构造一棵哈夫曼树,首先,将每个出现的字符当做一个独立的结点,其权值作为它出现的频度(或次数),然后构造哈夫曼树。显然所有字符节点均出现在叶子结点中。我们可以将字符的编码解释为从根至该字符路径上标记的序列,其中标记为0表示"转向左孩子",标记为1表示为"转向右孩子"。 如下图,矩形方块表示字符及出现的次数
     
             因此,这棵哈夫曼树的WPL为:
                       WPL = 1*45 + 3 * (13+12+16) + 4 * (5+9) = 224
    #ifndef _HAFFMANTREE_H
    #define _HAFFMANTREE_H
    
    /*
    实现对赫夫曼编码主要步骤:
     1 生成一个节点数组用来存放树的节点信息
     2 初始化
     3 从中找出权值最小和权值次小节点然后生成这两个节点的双亲节点权值最小节点是该双亲节点的左孩子次小为右孩子然后将该双亲节点加入到节点数组中并标记为已加入
     4 重复三步骤知道赫夫曼树构造成功
    */
    #include<stdio.h>
    #include<malloc.h>
    #define LEN_CODE sizeof(HaffmanCode)
    #define LEN_NODE sizeof(haffmannode)
    #define MAXWEIGHT 1000 //用来存储最大的权值数
    #define MaxBits 30 //用来存储转化后的编码
    
    typedef struct HaffManTree
    {
        int weight;  //存放节点的权值
        int LeftChild,RightChild,Parent;  //采用仿真指针方法存放节点的左右孩子和双亲下标
        int flag;  //用来判断该节点是否已经加入了赫夫曼树中( 0表示未加入,1表示已经加入 )
    }haffmannode;
    
    typedef struct HaffMancode
    {
        int bits[MaxBits]; //用来存放编码
        int weight;  //用来存放对应的权值
        int start; //存放编码的起始位置
    }HaffmanCode;
    
    void MakeTree(int weight[],int n,haffmannode haffmantree[]);
    void MakeCode(haffmannode haffmantree[],int n,HaffmanCode haffmancode[]);
    void DispCode(char temp[],haffmannode tree[],HaffmanCode Code[],int n);
    
    #endif
    /*
    功能函数的实现
    */
    #include"haffman.h"
    
    void MakeTree(int weight[],int n,haffmannode haffmantree[])
    {
        int i,j,m1,m2,x1,x2;
        //初始化(n个叶节点一共 2*n-1 个节点)
        for(i=0;i < 2*n-1; i++)
        {
            if(i < n)  //处理 n 个叶子节点
            {
                haffmantree[i].weight=weight[i];
            }
            else haffmantree[i].weight=0;
            haffmantree[i].LeftChild=-1;  //开始时候让左右孩子和双亲的下标为 -1 
            haffmantree[i].RightChild=-1;
            haffmantree[i].Parent=-1;
            haffmantree[i].flag=0;  
        }
        
        //每次从中选出权值最小的和次小的构成树的左右子树
        //处理 n-1 个非叶子节点
        for(i=0; i < n-1;i++)
        {
            m1=m2=MAXWEIGHT;
            x1=x2=0;
            //从有权值的节点中查找 m1 用来存放权值最小的 m2 用来存放权值次小的 x1 用来存放权值最小的下标 x2 用来存放权值次小的下标
            for(j=0;j < n+i; j++)
            {
                if(haffmantree[j].weight < m1 && haffmantree[j].flag==0)
                {
                    m2=m1; 
                    x2=x1;
                    m1=haffmantree[j].weight;
                    x1=j;
                }
                else if(haffmantree[j].weight < m2 && haffmantree[j].flag==0)
                {
                    m2=haffmantree[j].weight;
                    x2=j;
                }
            }
            haffmantree[x1].Parent=n+i; // 比如第一个双亲节点的下标就是 n 第二个双亲节点的下标就是 n+1 --------
            haffmantree[x2].Parent=n+i;
            haffmantree[x1].flag=1;
            haffmantree[x2].flag=1;
            haffmantree[n+i].weight=haffmantree[x1].weight + haffmantree[x2].weight;  //权值求和
            //printf("%d\n",haffmantree[n+i].weight);
            haffmantree[n+i].LeftChild=x1;
            haffmantree[n+i].RightChild=x2;    
        }
    }
    
    //本函数用来实现对赫夫曼编码的解决
    void MakeCode(haffmannode haffmantree[],int n,HaffmanCode haffmancode[])
    {
        int i,j;
        int Child,Parent;
        HaffmanCode *code;
        code=(HaffmanCode *)malloc(LEN_CODE);  //用来存放临时数据
        for(i=0;i < n ;i++)
        {
            code->weight=haffmantree[i].weight;
            code->start=0; 
            Child=i;    
            Parent=haffmantree[Child].Parent;
            while(Parent != -1) //当双亲节点不为根节点时候
            {
                if(haffmantree[Parent].LeftChild==Child)  //如果当前节点是双亲节点的左孩子就将0加入到该编码中如果是右孩子就将1加入到编码中
                    code->bits[code->start]=0;
                else
                    code->bits[code->start]=1;
                code->start++;  
                Child=Parent;  //自底向上移动判断
                Parent=haffmantree[Child].Parent;
            }
            for(j=0;j < code->start;j++) //把该编码加入到对应的编码数组中
            {
                haffmancode[i].bits[j]=code->bits[j];
            }
            haffmancode[i].weight=code->weight; //把对应的权值加入到对应编码数组的权值中去
            haffmancode[i].start=code->start; //将结束位置复制进去
        }
    }
    
    
    void DispCode(char temp[],haffmannode tree[],HaffmanCode Code[],int n) //本函数主要用来实现哈夫曼编码的输出
    {
        int i,j;
        printf("\n输出赫夫曼编码:\n\n");
        for(i=0;i<n;i++)
        {
            printf("字符= %c \tWeight= %d \t\n字符= %c \tCode=",temp[i],tree[i].weight, temp[i]);
            for(j=(Code[i].start-1);j>=0;j--)//输出编码
            {
                printf("%d",Code[i].bits[j]);
            }
            printf("\n\n");
        }
    }

     

     

    转载于:https://www.cnblogs.com/enumhack/p/7473043.html

    更多相关内容
  • 哈夫曼树定义与原理

    2022-05-14 21:46:10
    哈夫曼树定义与原理 图上两棵二叉树可以简化为叶子结点带权的二叉树,A表示不及格、B表示及格、C表示 中等、D表示良好、E表示优秀。每个叶子的分支线上的数字就是成绩所占比例。 路径长度:树中一个结点到另一...

    哈夫曼树定义与原理

    image
    image
    image

    图上两棵二叉树可以简化为叶子结点带权的二叉树,A表示不及格、B表示及格、C表示
    中等、D表示良好、E表示优秀。每个叶子的分支线上的数字就是成绩所占比例。

    image

    • 路径长度:树中一个结点到另一个结点之间的分支构成两个结点之间的路径,路径上的分支数目称做路径长度。
    • 树的路径长度:从树根到每一结点的路径长度之和。
    • a树的路径长度:1+1+2+2+3+3+4+4 = 20
    • b树的路径长度:1+2+3+3+2+1+2+2 = 16
    • 结点的带权路径长度:该结点到树根之间的路径长度与结点上权的乘积。
    • 树的带权路径长度:树中所有叶子结点的带权路径长度之和。用WPL表示

    带权路径长度WPL最小的二叉树称做哈夫曼树,也叫最优二叉树。

    • a树WPL:315
    • b树WPL:220
    • 上述结果意味着:10000个学生,a树需要31500次比较,b树只需要22000次比较,少了三分之一的量,性能明显提升。

    如何构造哈夫曼树

    image
    image

    上图虽然是哈夫曼树,但是每次判断需要比较两次。比如根结点(T < 80 && T >= 70 )效率上不如下图的高:
    image

    哈夫曼编码

    image
    如上,数据被压缩了,节约了大约17%的存储或传输成本。

    展开全文
  • 假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:  (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);  (2) 在森林中选出两个根结点...

    1 构造原理

    假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:
      (1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);
      (2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
      (3)从森林中删除选取的两棵树,并将新树加入森林;
      (4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。

    显然对n个权值,构造哈夫曼树树需要合并n-1次,形成的树结点总数为2n-1;
    

    2 代码实现

    根据哈夫曼树的构造原理,为方便实现,我们使用数组来存储每个结点,其命名为Tree;

    2.1 节点结构

    节点具有以下结构:
      weight:权值
      parent:父节点在数组中的位置(同时用来判断该节点是否已经参与了合并)
      lchild, rchild:左右孩子结点在数组中的位置
      code:该结点所分配的编码

    //结点结构
    struct HNode{
    	float weight;  //权值
    	int parent;  //父节点,父节点主要判定一个结点是否已经加入哈夫曼树
    	int lchild, rchild;  //左孩子,右孩子
    	string code;  //记录结点编码
    	HNode() {
    		weight = 0;
    		parent = lchild = rchild = -1;
    		code = "";
    	}
    	HNode(float w) {
    		weight = w;
    		parent = lchild = rchild = -1;
    		code = "";
    	}
    };
    

    2.2 关键成员函数解析

    2.2.1 构造函数

    为了判定一个结点是否已经加入哈夫曼树中,可通过parent域的值来确定。初始时parent的值为-1,当某结点加入到树中时,该节点parent域的值为其双亲结点在数组中的下标。

    构造哈夫曼树时,首先将n个权值的叶子结点存放到数组haftree的前n个分量中,然后不断将两棵子树合并为一棵子树,并将新子树的根节点顺序存放到数组Tree的前n个分量的后面。

    ** 哈夫曼算法用伪代码描述为**:
      1、数组haftree初始化,所有数组元素的双亲、左右孩子都置为-1;
      2、数组haftree的前n个元素的权值置给定权值;
      3、进行n-1次合并:
         3.1 在二叉树集合中选取两个权值最小的根节点,其下标分别为i1,i2;
         3.2 将二叉树i1、i2合并为一棵新的二叉树k。

    构造函数输入为权值数组和数组长度
    
    	//构造哈夫曼树,输入权值数组 和 数组长度n
    	void Create(float* a, int n) {
    		TreeSize = 2 * n - 1;  //确定哈夫曼树的结点个数
    		Tree = new HNode[TreeSize];
    		//权值数组保存在哈夫曼树数组前n个数值
    		for (int i = 0; i < n; i++)
    		{
    			Tree[i].weight = a[i];
    		}
    
    		//开始进行n-1次合并操作,形成一颗哈夫曼树
    		int s1, s2;
    		int nextPos = (TreeSize + 1) / 2; //记录下一个插入位置,起始为n
    		for (int i =0; i < (TreeSize-1)/2; i++) {
    			SelectTwoMin(nextPos, s1, s2); //找到数组中权值最小的两个点
    			//对Tree中新节点的孩子结点及权值赋值
    			Tree[nextPos].lchild = s1;
    			Tree[nextPos].rchild = s2;
    			Tree[nextPos].weight = Tree[s1].weight + Tree[s2].weight;
    			//给这两个结点分配父节点(意味着两个结点已加入哈夫曼树)
    			Tree[s1].parent = Tree[s2].parent = nextPos;
    			nextPos++;  //插入位置后移一位
    		}
    	}
    

    2.2.2 寻找最小的两个点

    先寻找到前两个还未合并的点(parent=-1),在和后面未合并过的点比较权值,确定最终最小的两个点,并确保权值小的在前面;

    	//寻找数组中权值最小的两个点
    	void SelectTwoMin(int nextPos,int &s1, int &s2) 
    	{
    		//找到第一个未加入哈夫曼树的结点,标记为s1
    		int i=0;
    		while (Tree[i].parent != -1) {
    			i++;
    		}
    		//从s2后一位开始找到第二个未加入哈夫曼树的结点,标记为s2
    		s1 = i;
    		int j = i + 1;
    		while (Tree[j].parent != -1) {
    			j++;
    		}
    		s2 = j;
    		//调整s1和s2对应权值大小,确保s1对应点的权值更小,从而寻找更小的点时只需和s2比较
    		KeepOrder(s1, s2);
    
    		//从s2后一位开始,和s1,s2比较,确定数组中权值最小的两个点
    		for (int k = j + 1; k <nextPos; k++) 
    		{
    			if (Tree[k].parent == -1) {
    				if (Tree[k].weight < Tree[s2].weight) {
    					s2 = k;
    					//找到小于s2的点后,需和s1比较确定大小顺序
    					KeepOrder(s1, s2);
    				}
    			}
    		}
    	}
    	//确保n1对应结点的权值小于n2
    	void KeepOrder(int& n1,int& n2) {
    		if (Tree[n1].weight > Tree[n2].weight)
    		{
    			float tmp = n1;
    			n1 = n2;
    			n2 = tmp;
    		}
    	}
    

    2.2.3 对构造好的哈夫曼树进行编码并输出

    这里使用层次遍历,借助一个队列实现;孩子结点的编码由父节点的code加上’1’/‘0’(根据其处于父节点的左孩子还是右孩子而定,左孩子为’1’);
      只输出叶子结点的编码.也可以在编码完成后直接输出Tree数组的前n个的结点的编码;

    	//对树中结点编码并输出
    	void PrintCoder() 
    	{
    		cout << "index weight     code" << endl;
    		queue<int> codeQueue;  //只保存编号
    		int tmp;
    		codeQueue.push(TreeSize - 1);
    		while (!codeQueue.empty())
    		{
    			tmp = codeQueue.front();
    			codeQueue.pop();
    			if (Tree[tmp].lchild ==-1 && Tree[tmp].rchild == -1) {  
    				//叶子节点直接输出
    				cout << setw(5) << tmp << setw(6) << Tree[tmp].weight << setw(10) << Tree[tmp].code << endl;	
    			}
    			else {//因为哈夫曼树中只有N0和N2
    				codeQueue.push(Tree[tmp].lchild);
    				Tree[Tree[tmp].lchild].code = Tree[tmp].code + "1";  //对左孩子编码
    
    				codeQueue.push(Tree[tmp].rchild);
    				Tree[Tree[tmp].rchild].code = Tree[tmp].code + "0"; //对右孩子编码
    			}
    		}
    	}
    };
    

    2.2.4 输出整个哈夫曼树所有的结点的全部信息(除编码);

    	//输出构建完成的哈夫曼树
    	void PrintTree() {
    		cout << "index weight parent lchild rchild" << endl;
    		for (int i = 0; i < TreeSize; i++) {
    			cout << setw(5) << i;
    			cout << setw(6) << Tree[i].weight;
    			cout << setw(6) << Tree[i].parent;
    			cout << setw(6) << Tree[i].lchild;
    			cout << setw(6) << Tree[i].rchild;
    			cout << endl;
    		}
    	}
    

    2.2 完整代码

    #pragma once
    #include <iostream>
    #include <iomanip>
    #include <Queue>
    #include <string>
    using namespace std;
    //用来获取数组长度
    template <class T>
    int getArrayLen(T& array)
    {
    	return (sizeof(array) / sizeof(array[0]));
    }
    
    //结点结构
    struct HNode{
    	float weight;  //权值
    	int parent;  //父节点,父节点主要判定一个结点是否已经加入哈夫曼树
    	int lchild, rchild;  //左孩子,右孩子
    	string code;  //记录结点编码
    	HNode() {
    		weight = 0;
    		parent = lchild = rchild = -1;
    		code = "";
    	}
    	HNode(float w) {
    		weight = w;
    		parent = lchild = rchild = -1;
    		code = "";
    	}
    };
    
    class HuffmanTree {
    	HNode* Tree;  //哈夫曼树结点数组头部
    	int TreeSize; //树中结点树总数,TreeSize=叶子结点n(要编码的字符个数) * 2 - 1
    public:
    	HuffmanTree() {
    		Tree = NULL;
    		TreeSize = 0;
    	}
    	~HuffmanTree() {
    		delete[] Tree;
    	}
    
    	//构造哈夫曼树,输入权值数组 和 数组长度n
    	void Create(float* a, int n) {
    		TreeSize = 2 * n - 1;  //确定哈夫曼树的结点个数
    		Tree = new HNode[TreeSize];
    		//权值数组保存在哈夫曼树数组前n个数值
    		for (int i = 0; i < n; i++)
    		{
    			Tree[i].weight = a[i];
    		}
    
    		//开始进行n-1次合并操作,形成一颗哈夫曼树
    		int s1, s2;
    		int nextPos = (TreeSize + 1) / 2; //记录下一个插入位置,起始为n
    		for (int i =0; i < (TreeSize-1)/2; i++) {
    			SelectTwoMin(nextPos, s1, s2); //找到数组中权值最小的两个点
    			//对Tree中新节点的孩子结点及权值赋值
    			Tree[nextPos].lchild = s1;
    			Tree[nextPos].rchild = s2;
    			Tree[nextPos].weight = Tree[s1].weight + Tree[s2].weight;
    			//给这两个结点分配父节点(意味着两个结点已加入哈夫曼树)
    			Tree[s1].parent = Tree[s2].parent = nextPos;
    			nextPos++;  //插入位置后移一位
    		}
    	}
    
    	//寻找数组中权值最小的两个点
    	void SelectTwoMin(int nextPos,int &s1, int &s2) 
    	{
    		//找到第一个未加入哈夫曼树的结点,标记为s1
    		int i=0;
    		while (Tree[i].parent != -1) {
    			i++;
    		}
    		//从s2后一位开始找到第二个未加入哈夫曼树的结点,标记为s2
    		s1 = i;
    		int j = i + 1;
    		while (Tree[j].parent != -1) {
    			j++;
    		}
    		s2 = j;
    		//调整s1和s2对应权值大小,确保s1对应点的权值更小,从而寻找更小的点时只需和s2比较
    		KeepOrder(s1, s2);
    
    		//从s2后一位开始,和s1,s2比较,确定数组中权值最小的两个点
    		for (int k = j + 1; k <nextPos; k++) 
    		{
    			if (Tree[k].parent == -1) {
    				if (Tree[k].weight < Tree[s2].weight) {
    					s2 = k;
    					//找到小于s2的点后,需和s1比较确定大小顺序
    					KeepOrder(s1, s2);
    				}
    			}
    		}
    	}
    
    	//确保n1对应结点的权值小于n2
    	void KeepOrder(int& n1,int& n2) {
    		if (Tree[n1].weight > Tree[n2].weight)
    		{
    			float tmp = n1;
    			n1 = n2;
    			n2 = tmp;
    		}
    	}
    
    	//输出构建完成的哈夫曼树
    	void PrintTree() {
    		cout << "index weight parent lchild rchild" << endl;
    		for (int i = 0; i < TreeSize; i++) {
    			cout << setw(5) << i;
    			cout << setw(6) << Tree[i].weight;
    			cout << setw(6) << Tree[i].parent;
    			cout << setw(6) << Tree[i].lchild;
    			cout << setw(6) << Tree[i].rchild;
    			cout << endl;
    		}
    	}
    
    	//对树中结点编码并输出
    	void PrintCoder() 
    	{
    		cout << "index weight     code" << endl;
    		queue<int> codeQueue;  //只保存编号
    		int tmp;
    		codeQueue.push(TreeSize - 1);
    		while (!codeQueue.empty())
    		{
    			tmp = codeQueue.front();
    			codeQueue.pop();
    			if (Tree[tmp].lchild ==-1 && Tree[tmp].rchild == -1) {  
    				//叶子节点直接输出
    				cout << setw(5) << tmp << setw(6) << Tree[tmp].weight << setw(10) << Tree[tmp].code << endl;	
    			}
    			else {//因为哈夫曼树中只有N0和N2
    				codeQueue.push(Tree[tmp].lchild);
    				Tree[Tree[tmp].lchild].code = Tree[tmp].code + "1";  //对左孩子编码
    
    				codeQueue.push(Tree[tmp].rchild);
    				Tree[Tree[tmp].rchild].code = Tree[tmp].code + "0"; //对右孩子编码
    			}
    		}
    	}
    };
    
    

    3 测试代码及输出

        ///哈夫曼树
        HuffmanTree hTree;
    	float x[] = { 5,29,7,8,14,23,3,11 };
    	hTree.Create(x, getArrayLen(x));//避免输入错误的数组长度导致错误
    	hTree.PrintTree();
    	hTree.PrintCoder();
    

    正确输出:

    4 参考资料

    1.哈夫曼树算法及C++实现:https://www.cnblogs.com/smile233/p/8184492.html
    2.百度百科·哈夫曼树:https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91/2305769#5
    3.数据结构:Huffman树(哈夫曼树)原理及C++实现:https://blog.csdn.net/weixin_41427400/article/details/80383686

    展开全文
  • 所谓哈夫曼树就是要求最小加权路径长度,这是什么意思呢?简而言之,就是要所有的节点对应的路径长度(高度-1)乘以该节点的权值,然后保证这些结果之和最小。下面这篇文章就给大家详细介绍
  • 2. 掌握哈夫曼树与哈夫曼码逻辑结构和存储结构。 3.掌握哈夫曼树与哈夫曼码的基本操作。 二、设计内容和要求 1.输入一个文本,统计各字符出现的频度,输出结果 2.使用二叉链表或三叉链表作存贮结构,构造哈夫曼树 3...
  • 从键盘输入若干字符及每个字符出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树,求出各字符的哈夫曼编码。要求: 1. 输出存放哈夫曼树的数组HT的初态和终态; 2. 输出每个字符的哈夫曼编码; 3. 输入...
  • 本篇文章主要介绍了C++哈夫曼树编码和译码的实现,详细的讲诉了哈夫曼树编码的原理,有需要的同学可以了解一下。
  • 实验报告 实验名称 哈弗曼编码和译码 专业班级 电子信息科学与技术0904 姓 名 秦杰 学 号 1404090506 指导教师 胡志坤 2011年 11月 实验四哈夫曼编码和译码 实验目的和要求 掌握哈夫曼树的基本概念及其存储结构 ...
  • 1.哈夫曼树的定义: 什么是哈夫曼树? 又称为最优二叉树,是带权路径长度之和最小的二叉树。 带权路径长度之和又是什么? 设二叉树有n个叶子结点,每个叶子结点的权重为Wk,从根节点到每个叶子结点的长度为Ik,则...

    1.哈夫曼树的定义:

    什么是哈夫曼树?
    又称为最优二叉树,是带权路径长度之和最小的二叉树。
    带权路径长度之和又是什么?
    设二叉树有n个叶子结点,每个叶子结点的权重为Wk,从根节点到每个叶子结点的长度为Ik,则所有叶子结点带权路径长度( Wk * Ik)的和为该树的带权路径长度之和(WPL)。
    WPL = ∑nk=1 Wk * Ik
    这些只是概念上的东西,所谓带权路径长度之和最小不过就是为了让经常出现的东西不像其他东西一样占用过多空间,看下面这个例子理解这句话:
    在这里插入图片描述
    对于这个例题相信大家都会这样写出代码,对应的判定树:
    在这里插入图片描述
    但是如果有很多人的成绩要经过这样的转换,而这些人学习又很好,都考了八十分以上,那岂不是每次都要经过四次判断才能完成转换。所以需要对这个树进行修改,我们假设下面一种情况来体会分析的过程:
    在这里插入图片描述
    对于上面那个判断树,1到根节点的长度为1,2到根节点的长度为2,3到根节点的长度为3,4、5到根节点的长度为4,所以我们套用前面的公式得到用上面那个判断树的查找效率就是:
    在这里插入图片描述
    但是0-59(对应一分)所占的比例只有0.05,而后面的都有0.3、0.4,显然每次第一个判断是否在0-59内是不合适的,我们根据所占比例改为:
    在这里插入图片描述
    这样修改之后我们可以清晰地看到所占比例(相当于权重)的分数的到根节点的长度变短了,所以查找效率提升了。这就是哈夫曼树的真谛。

    2.哈夫曼树的创建及原理:

    根据上面的例子我们可以看出,我们每次都先把出现频率最低的放在下面,所以我们构造哈夫曼树时,每次都把权重最小的两棵二叉树合并。看这个例子体会过程:注意第四步并不是把4和6合并,而是4和5,因为每次都把权重最小的两棵二叉树合并在这里插入图片描述
    而最小堆就是小的元素在上,大的元素在下,很适合我们像上图这样边取出边合并边存入,所以我们的数据就放入最小堆来实现哈夫曼树:
    在这里插入图片描述
    这是具体的实现,其中关于堆的函数可以看这片文章https://mp.csdn.net/postedit/104214196,不过这里面是最大堆的函数实现,稍作改动即为最小堆。
    由于堆其实就是优先队列,我们可以用STL库中的优先队列priority_queue来进行数据的存放:(其实和用最小堆来实现不过是在调用函数时可以用库里面的不用自己定义了)

    priority_queue<int,vector<int>,greater<int> > q;
    //priority_queue对应最小堆的定义形式,为什么这样写自己去查优先级设置。
    int main()
    {
    	int n;
    	cin>>n;
    	int i,weight[n];
    	for(i=0;i<n;i++){
    		cin>>weight[i];
    		q.push(weight[i]);
    	}
    	while(q.size()>1){
    		int x=q.top()//得到堆顶值(最小值)
    		q.pop();
    		int y=q.top();//得到堆顶值(最小值)
    		q.pop();
    		q.push(x+y);//合并两个权重最小的子树
    		//根据需要加一些其他的
    	}
    }
    

    这样做最终得到的只有根节点的值,但哈夫曼树的真正作用其实不是哈夫曼树的本身,而是他在创建时每次合并后根据其他需要进行一些别的运算。

    3.哈夫曼树的特点:

    (1)没有度为1的节点
    因为是两两合并得到的,不可能有单独的一个出来。
    (2)n个叶子结点的哈夫曼树有一共有2n-1个节点
    因为没有度为1的节点,还有公式n0=n2+1(也就是叶子结点数比度为2的节点个数多一个),所以。。。
    (3)哈夫曼树的任意非叶节点的左、右子树交换后依然还是哈夫曼树。
    (4)对于同一组权重,可以有多个不同结构的哈夫曼树,但他们的WPL一定都相同!!! 看下面这个例子:
    在这里插入图片描述

    4.哈夫曼编码:

    字符串中字符的编码:
    对于几十万单词的英语论文,我们不可能为每个字母开辟相同的编码空间,万一a出现了100000次,而z只出现了一次,那z的空间就白白浪费了。解决这件事就用到了哈夫曼树的原理。看这个例子:
    在这里插入图片描述
    解决方案如下:
    在这里插入图片描述
    显然前两种和我们说的那种情况一样,那么我们如何来实现不等长编码呢?
    在这里插入图片描述
    再看下面的例子:
    在这里插入图片描述
    如例子中这样建树,对应a=00,u=01,x=10,z=11
    在这里插入图片描述
    这样建树,对应a=0,x=10,u=110,z=11,这时就是不等长编码了。那么问题又来了,怎样让编码的代价(cost)最小呢?,这就用到哈夫曼树的原理,就和之前的例子:
    在这里插入图片描述
    我们只需要得到每个字母出现的次数(权重),然后每次都让最小的两个子树合并,左为0右为1一直到叶子结点(也就是字母出现次数存放的地方)为字母从上到下记录其编码。 例:
    在这里插入图片描述
    在这里插入图片描述
    只给出了最终的结果,其中过程自己去画体会。

    展开全文
  • 提示:哈夫曼树原理以及python实现: 例如:最近面试时被Q的点,但是工作三年,当年考研时学的东西基本上又还给了老师,除去链表工作中可能用的比较多,树相关基本只记得名词。 网上很多讲解都看过了,不过算法...
  • 数据结构18————哈夫曼树

    千次阅读 多人点赞 2017-12-21 22:10:51
    数据结构15————哈夫曼树 一.内容 1.哈夫曼树的定义和原理 2.哈夫曼树的建立 3.哈夫曼编码 4.哈夫曼算法的实现
  • 实验五 求二叉树叶子,高度及哈夫曼树
  • 哈夫曼树_数据结构课程设计《 数据结构 》课程设计——赫夫曼编码/译码器设计指导教师:孙树森、周维达班级:09数媒(2)班学号:姓名:林真超数据结构课程设计实验报告一、题目:赫夫曼编码/译码器设计二、目的:1、...
  • 做数据结构课设的时候写的
  • 哈夫曼树 概述 给定n个权值作为n个叶子节点构造一棵二叉树,若该树的带权路径长度(wpl)最小,这样的二叉树为最优二叉树,也称赫夫曼树、哈夫曼树、霍夫曼树 赫夫曼树是带权路径最短的树,其中权值大的节点离根较近 ...
  • 哈夫曼树、哈夫曼编码详解

    千次阅读 多人点赞 2021-06-17 09:33:06
    哈夫曼树、哈夫曼编码,也就这么一回事,一文搞懂!
  • 哈夫曼树构造原理及方法

    千次阅读 2020-11-02 10:46:45
    哈夫曼树(最优二叉树) 百度百科:https://baike.baidu.com/item/%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91/2305769?fr=aladdin 一. 目的: 找出存放一串字符所需的最少的二进制编码 二. 构造方法: 首先统计出每种...
  • 哈夫曼树的应用——数据结构课程设计
  • 哈夫曼树,也称最优二叉树,是数据结构的一个重要内容,实际运用中我们通过哈夫曼编码来大幅度提高无损压缩的比例。 弄清哈夫曼树,我们首先要弄清以下四个概念。 概念1:什么是路径? 在一棵树中,从一个结点到另一...
  • 哈夫曼树/赫夫曼树 Python实现赫夫曼树 Python实现哈夫曼树 哈夫曼编码 哈夫曼压缩 哈夫曼解压 最简单的方式实现哈夫曼树
  • 详解哈夫曼树和哈夫曼编码

    千次阅读 多人点赞 2021-04-25 11:01:29
    哈夫曼树 并查集是一种用来管理元素分组情况的数据结构,可以高效地进行查询、合并操作,但无法进行分割操作。 1.查询元素a和元素b是否属于同一组 2.合并元素a和元素b所在的组 并查集使用树形结构实现,但不是...
  • 1.哈夫曼树:给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树共有2*n-1个结点(性质)。 2.哈夫曼树构建:选取权值...
  • 文章目录1、先掌握几个概念1.1 什么是路径?...  先听一遍哈夫曼树的概念:给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(WPL)达到最小,称这样的二叉树为最优二叉树,也成为哈夫曼树(Huf...
  • 给定报文中26个字母a-z及空格的出现频率{64, 13, 22, 32, 103, 21, 15, 47, 57, 1, 5, 32, 20, 57, 63, 15, 1, 48, 51, 80, 23, 8, 18, 1, 16, 1, 168},构建哈夫曼树并为这27个字符编制哈夫曼编码,并输出。...
  • 二、实验内容 1.根据给出的字符以及这些字符的使用频率构建哈夫曼树。 2.根据哈夫曼树对字符进行哈夫曼编码,并保存这些编码。...1. 建立哈夫曼树存储结构和哈夫曼编码的存储结构。 2. 建立哈夫曼树的...
  • 本文详细介绍了哈夫曼树的概念,并且提供了Java实现,最后又介绍了哈夫曼编码的概念以及原理
  • 目录八大数据结构——哈夫曼树(七)基础定义哈夫曼树的构造哈夫曼树编码哈夫曼树解码代码实现完整代码 树是数据结构中非常重要的一项,有关树的数据结构有许多种,本文重点研究的是哈夫曼树(最优二叉树)。 基础...
  • 哈夫曼树及其应用

    千次阅读 2021-02-13 19:26:16
    哈夫曼树及其应用 树结构是一种应用非常广泛的结构,在一些特定应用中,树具有一些特殊特点,利用这些特点能解决很多工程问题。下面以哈夫曼树为例,说明二叉树的一个具体应用。 基本概念 哈夫曼树又称最优树,是一...
  • 二叉树作为非线性数据结构,是以分支关系定义层次结构,以下重点为二叉树的存储结构及基本操作,以及树与二叉树之间的转化,最后介绍特殊的树结构——哈夫曼树
  • 【笔记】哈夫曼树

    千次阅读 2017-11-01 00:34:54
    哈夫曼树的概念 哈夫曼树的构造算法 哈夫曼编码 哈夫曼编码算法的实现

空空如也

空空如也

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

哈夫曼树的存储结构原理