2021-12-12 16:52:15

带权路径长度WPL：从根结点到各个叶子结点的路径长度和相应叶子结点权值的乘积之和

哈夫曼树：带权路径长度最小的二叉树（最优二叉树）

-没有度为1的结点，有n个叶子结点的哈夫曼树共有2n-1个结点

-任意非叶结点的左右子树交换后依旧是哈夫曼树

-对同一组权值，存在多个不同的哈夫曼树，但带权路径长度都相同

哈夫曼树的构造：将权值按升序排列，每次把权值最小的两棵二叉树合并为一棵树，合并产生的新结点的权值为左右子树的权值之和，最终的根结点的权值即为最短带权路径长度。

如何找到权值最小的结点？——最小堆

堆：有优先权的队列，依照优先权（关键字）大小而不是入队顺序进行出队。即，插入时都是在队头插入，但删除时要查找最小的关键字；或者在插入的时候进行排序，删除时直接删去队尾元素。

存储结构：用数组表示的有序的完全二叉树，任一结点的关键字是其子树中所有结点的最小值.

最小堆的数据结构定义

typedef struct Heap *MinHeap;
struct Heap {
    HuffmanTree *Data; //存储哈夫曼树的结点的数组
    int Size; //堆当前存储的元素个数
    int Capacity; //堆的最大容量
};

最小堆的基本操作函数定义

-生成一个空的最小堆

MinHeap CreateMinHeap(int MaxSize) //创建一个空的最小堆
{
    MinHeap H = (MinHeap)malloc(sizeof(struct Heap));
    H->Data = (HuffmanTree)malloc((MaxSize+1)*sizeof(struct TNode));
    H->Size = 0;
    H->Capacity = MaxSize;
    H->Data[0]->Weight = MINDATA; //哨兵，比所有结点都要小的值#define MINDATA -1
    return H;
}

-创建最小堆

void PercDown(MinHeap H, int p) //调整算法
{
    int Parent, Child;
    HuffmanTree MinT,temp;
    MinT = H->Data[p]; //取出根结点
    temp = H->Data[H->Size--]; //最小堆中的最后一个元素
    for(Parent = p; Parent*2 <= H->Size; Parent = Child) { //在有左孩子的条件下，从根结点开始向下比较
        Child = Parent*2; //先让Child指向左孩子
        if((Child != H->Size) && (H->Data[Child] > H->Data[Child+1])) //如果有右孩子且右孩子比左孩子小
            Child++; //Child指向右孩子
        if(temp <= H->Data[Child]) //如果最后这个元素比根结点的左右孩子都小，即temp是最小元素
            break;
        else //否则将左右孩子中小的那一个移动到根结点
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = temp;
}

void BuildMinHeap(MinHeap H) //先形成一个完全二叉树，再不断调整以满足哈夫曼树的特性
{
    int i;
    for(i = H->Size/2; i > 0; i--)
        PercDown(H,i);
}

-最小堆的插入

bool IsFull(MinHeap H) //判断最小堆是否已满
{
    if (H->Size == H->Capacity)
        return true;
    else
        return false;
}

void Insert(MinHeap H, HuffmanTree T) //将元素T插入最小堆，元素类型为树结点
{
    int i;
    if (IsFull(H)) {
        printf("最小堆已满");
        return;
    }
    i = ++H->Size; //i插入到堆中最后一个元素后面
    for( ; H->Data[i/2]->Weight > T->Weight; i/=2) //不断跟父结点比较
        H->Data[i] = H->Data[i/2];
    H->Data[i] = T; //将T插入
}

-最小堆的删除

bool IsEmpty(MinHeap H) //判断最小堆是否为空
{
    if (H->Size == 0)
        return true;
    else
        return false;
}

HuffmanTree DeleteMin(MinHeap H) //删除并返回最小堆中最小的元素
{
    int Parent, Child;
    HuffmanTree MinT, temp;
    if(IsEmpty(H)) {
        printf("最小堆已空");
    }
    MinT = H->Data[1]; //取出根结点
    temp = H->Data[H->Size--]; //最小堆中的最后一个元素
    for(Parent = 1; Parent*2 <= H->Size; Parent = Child) { //在有左孩子的条件下，从根结点开始向下比较
        Child = Parent*2; //先让Child指向左孩子
        if((Child != H->Size) && (H->Data[Child] > H->Data[Child+1])) //如果有右孩子且右孩子比左孩子小
            Child++; //Child指向右孩子
        if(temp <= H->Data[Child]) //如果最后这个元素比根结点的左右孩子都小，即temp是最小元素
            break;
        else //否则将左右孩子中小的那一个移动到根结点
            H->Data[Parent] = H->Data[Child];
    }
    H->Data[Parent] = temp;
    return MinT;
}

将找到的最小结点合并——哈夫曼树的构造

链表实现

哈夫曼树的数据结构定义

typedef struct TNode *HuffmanTree;
struct TNode { //树结点定义
    int Weight; //权值
    HuffmanTree Left, Right; //左右孩子，类型为树结点
};

哈夫曼树的构造

HuffmanTree Huffman(MinHeap H)
{
    int i;
    HuffmanTree T;
    BuildMinHeap(H);
    for (i = 1; i < H->Size; i++) { //做Size-1次合并
        T = (HuffmanTree)malloc(sizeof(struct TNode));
        T->Left = DeleteMin(H); //从最小堆中删除一个结点作为新的T的左孩子
        T->Right = DeleteMin(H); //从最小堆中删除一个结点作为新的T的右孩子
        T->Weight = T->Left->Weight + T->Right->Weight;//计算新带权路径长度
        Insert(H,T); //将新T插入最小堆
    }
    T = DeleteMin(H);
    return T;
}

数组实现

数据结构定义

typedef struct {
    char data; //结点的数据
    int weight; //结点的权值
    int lchild, rchild; //左、右孩子
    int parent; //父结点
}HNode;

哈夫曼树的构造

void HuffmanTree(HNode hufftree[], int w[], int n)
{
    for(i = 0; i < 2*n-1; i++) { //初始化
        hufftree[i].parent = -1;
        hufftree[i].lchild = -1;
        hufftree[i].rchild = -1;
    }
    for(i = 0; i < n; i++) //初始化结点权重
        hufftree[i].weight = -1;
    for(k = 0; k < 2*n-1; k++) {
        Select(hufftree, i1, i2); //待写
        hufftree[i1].parent = k;
        hufftree[i2].parent = k;
        hufftree[k].weight = hufftree[i1].weight + hufftree[i2].weight;
        hufftree[k].lchild = i1;
        hufftree[k].rchild = i2;
    }
}

哈夫曼编码

- 根据字符出现的频率构造哈夫曼树，使电文总长度最短

- 从根结点开始，若编码是1则往左走，编码是0则往右走，遇到叶子结点则译出一个字符

霍夫曼树数据结构算法

更多相关内容

利用最小堆实现哈夫曼树
2015-11-17 14:31:34

本资源是数据结构中利用最小堆实现哈夫曼树的一个C++代码，仅供参考，欢迎指正

收起

最小堆实现哈夫曼树的构造及哈夫曼编码、解码

2020-04-10 19:26:38

最小堆建哈夫曼树测试用例： 5 1 2 3 4 5 #include<stdio.h> #include<stdlib.h> #define MinData -10001 typedef struct Heap *MinHeap; typedef struct HTNode *HuffmanTree; struct Heap{ ...

原文链接：https://blog.csdn.net/Authur520/article/details/84781037?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1

最小堆建哈夫曼树

测试用例：

5
1  2  3  4  5

在这里插入图片描述

#include<stdio.h>
#include<stdlib.h>
#define MinData -10001
typedef struct Heap *MinHeap;
typedef struct HTNode *HuffmanTree;
struct Heap{
    HuffmanTree *data;//存储堆元素的数组，存储时从下标1开始 
    int Size;    //记录当前堆元素个数
    int Capacity;   //堆的最大容量
};
struct HTNode{
	int Weight;//权值 
	HuffmanTree Left;
	HuffmanTree Right;
};

MinHeap CreateMinHeap(int MaxSize);//建一个最小堆 
bool Insert(MinHeap H,HuffmanTree item);//将新T插入最小堆 
HuffmanTree DeleteMin(MinHeap H);//从最小堆中删除一个结点，作为新T的子节点
MinHeap BuildMinHeap(MinHeap H);//将H->data[]按权值Weight调整为最小堆 
HuffmanTree Huffman(MinHeap H);//构造哈夫曼树 
void PreOrderTraversal(HuffmanTree BST);//先序遍历 
void Inorder(HuffmanTree BST);//中序遍历 
bool IsFull(MinHeap H);
bool IsEmpty(MinHeap H);
int main()
{
	int i,N;
	MinHeap H;
	HuffmanTree T,BT=NULL;
	printf("请输入叶子结点的个数:\n"); 
	scanf("%d",&N);
	H=CreateMinHeap(2*N);
	printf("请输入%d个叶子结点对应的权值:\n",N);
	for(i=1; i<=N; i++){/*最小堆元素赋值*/ 
		T=(HuffmanTree)malloc(sizeof(struct HTNode));
		T->Weight = 0;
		T->Left = T->Right = NULL;
		scanf("%d",&(T->Weight));
		H->data[++(H->Size)] = T;
	}
	
	BT = Huffman(H);  //构造哈夫曼树 
	printf("先序遍历此哈夫曼树的权值:\n"); 
	PreOrderTraversal(BT);  //先序遍历此哈夫曼树 
	puts("");
	printf("中序遍历此哈夫曼树的权值:\n");
	Inorder(BT);//中序遍历此哈夫曼树 
	return 0;
}

HuffmanTree Huffman(MinHeap H)//构造哈夫曼树 
{
/*假设H->Size个权值已经存在H->data[]->Weight里*/
	int i,N;
	HuffmanTree T;
	BuildMinHeap( H );//将H->data[]按权值调整为最小堆
	N=H->Size;
	for(i=1;i<N;i++)//做 H->Size-1次合并 
	{
		T=(HuffmanTree)malloc(sizeof(struct HTNode)); //建立一个新的根结点 
		T->Weight = 0;
		T->Left = T->Right = NULL;
		T->Left=DeleteMin(H); //从最小堆中删除一个节点，作为新T的左子结点
		T->Right=DeleteMin(H);//从最小堆中删除一个节点，作为新T的右子结点 
		T->Weight=T->Left->Weight+T->Right->Weight;//计算新权值 
		Insert(H,T);//将新T插入到最小堆 
	}
	return DeleteMin(H);
}
MinHeap CreateMinHeap(int MaxSize)
{/*创建容量为MaxSize的最小堆*/
    MinHeap H = (MinHeap)malloc(sizeof(struct Heap));
    H->data = (HuffmanTree*)malloc((MaxSize+1)*sizeof(HuffmanTree));
    H->Size = 0;
    H->Capacity = MaxSize;
    HuffmanTree T=(HuffmanTree)malloc(sizeof(struct HTNode)); //建立一个新的根结点 
    //定义哨兵-小于堆中所有可能元素权值的值 
    T->Weight = 0;
	T->Left = T->Right = NULL;
    T->Weight=MinData;
    H->data[0] =T;
	return H;
}
bool IsFull(MinHeap H)
{
	return (H->Size==H->Capacity);
}
bool IsEmpty(MinHeap H)
{
	return (H->Size==0);
}
bool Insert(MinHeap H,HuffmanTree item)
{
    int i;
	if( IsFull(H) ){
		printf("最小堆已满\n");
		return false;
	}
	i = ++H->Size;  //i指向插入后堆中的最后一个元素的位置
	for(; H->data[i/2]->Weight > item->Weight; i/=2)  //无哨兵，则增加判决条件 i>1 
	    H->data[i] = H->data[i/2];  //向下过滤结点 
	H->data[i] = item;   //将item插入 
	
	return true;  
    
}
HuffmanTree DeleteMin(MinHeap H)
{/*从最小堆H中取出权值为最小的元素，并删除一个结点*/
	int parent,child;
	HuffmanTree MinItem,temp = NULL;
	if( IsEmpty(H) ){
		printf("最小堆为空\n");
		return NULL;
	}
	MinItem = H->data[1];  //取出根结点-最小的元素-记录下来
	/*用最小堆中的最后一个元素从根结点开始向上过滤下层结点*/
	temp = H->data[H->Size--];  //最小堆中最后一个元素，暂时将其视为放在了根结点
	for(parent=1; parent*2<=H->Size; parent=child){
		child = parent*2;
		if((child != H->Size) && (H->data[child]->Weight > H->data[child+1]->Weight)){/*有右儿子，并且左儿子权值大于右儿子*/
			child++; //child指向左右儿子中较小者 
		}
		if(temp->Weight > H->data[child]->Weight){
			H->data[parent] = H->data[child];  //向上过滤结点-temp存放位置下移到child位置 
		}else{
			break;  //找到了合适的位置
		}
	} 
	H->data[parent] = temp;  //temp存放到此处
	
	return MinItem; 
}
MinHeap BuildMinHeap(MinHeap H)
{/*这里假设所有的H->Size个元素已经存在H->data[]中*/
 /*本函数将H->data[]中的元素调整，使其满足堆的有序性*/ 
	int i,parent,child;
	HuffmanTree temp;
	for(i=H->Size/2;i>0;i--){  //从最后一个父结点开始，直到根结点 
		temp = H->data[i];
		for(parent=i; parent*2<=H->Size; parent=child){
		    /*向下过滤*/
			child = parent*2;
		    if((child != H->Size) && (H->data[child]->Weight > H->data[child+1]->Weight)){/*有右儿子，并且左儿子权值大于右儿子*/
			    child++; //child指向左右儿子中较小者 
		    }
		    if(temp->Weight > H->data[child]->Weight){
			    H->data[parent] = H->data[child];  //向上过滤结点-temp存放位置下移到child位置 
		    }else{
			    break;  //找到了合适的位置 
		    }
	    }/*结束内部for循环对以H->data[i]为根的子树的调整*/
		
		H->data[parent] = temp;  //temp（原H->data[i]）存放到此处  
	} 
	return H; 
}
void PreOrderTraversal(HuffmanTree BST)
{
	if( BST ){
		printf("%d ",BST->Weight);     //先访问根节点 
		PreOrderTraversal(BST->Left);  //再访问左子树 
		PreOrderTraversal(BST->Right); //最后访问右子树 
	}
}
void Inorder(HuffmanTree BST)
{
	if(BST)
	{
		Inorder(BST->Left);//先访问左子树 
		printf("%d ",BST->Weight);//再访问根节点 
		Inorder(BST->Right);//最后访问右子树 
	}
}

增加了哈夫曼编码、解码

测试用例：

6
6  3  8  2  10  4
a  b  c  d   e  f

在这里插入图片描述

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MinData -10001  //随着堆元素的具体值而改变  

typedef struct TreeNode *HuffmanTree;
typedef struct TreeNode{
	char ch;  //要编码的字符 
	int Weight;  //权值
	HuffmanTree Left;
	HuffmanTree Right; 
}HuffmanNode;
 
typedef struct HeapStruct *MinHeap;
struct HeapStruct{
	HuffmanTree *data;  //存储堆元素的数组  存储时从下标1开始 
	int Size;  //堆的当前元素的个数
	int Capacity;  //堆的最大容量 
};
 
HuffmanTree NewHuffmanNode();
MinHeap CreateMinHeap(int MaxSize);
bool Insert(MinHeap H,HuffmanTree item);
HuffmanTree DeleteMin(MinHeap H);
MinHeap BuildMinHeap(MinHeap H);
HuffmanTree Huffman(MinHeap H);
void PreOrderTraversal(HuffmanTree BST);
void HuffmanCode(HuffmanTree BST,int depth);//编码 
 
int main()
{
	int i,N;
	MinHeap h;
	HuffmanTree T,BT = NULL;
	
	printf("请输入叶子结点的个数:\n"); 
	scanf("%d",&N);
	h = CreateMinHeap(2*N);  //创建最小堆   //N个叶子节点最终形成的哈夫曼树最多有2N-1个树结点 
	printf("请输入%d个叶子结点对应的权值:\n",N); 	
	for(i=1; i<=N; i++){/*最小堆元素赋值*/ 
		T = NewHuffmanNode();
		scanf("%d",&(T->Weight));
		//scanf("%d-%c",&(T->Weight),&(T->ch));
		h->data[++(h->Size)] = T;
	}
	char string[100]; 
	printf("请连续输入这%d个叶子结点各自代表的字符:\n",N); 
	getchar();  //吸收上面的换行符 
	gets(string);
	for(i=1; i<=h->Size; i++){/*最小堆元素赋值*/ 
		h->data[i]->ch= string[i-1];
	}
	
	BT = Huffman(h);  //构造哈夫曼树 
	printf("\n");
	HuffmanCode(BT,0);	
	return 0;
 } 
 
 /*哈夫曼树构造算法*/
HuffmanTree Huffman(MinHeap H)
 {/*假设H->Size个权值已经存在H->data[]->Weight里*/
 	int i,num;
	HuffmanTree T;
	
	BuildMinHeap( H );  //将H->data[]按权值调整为最小堆
	/*此处必须将H->Size的值交给num,因为后面做DeleteMin()和 Insert()函数会改变H->Size的值*/
	num = H->Size;     
	for(i=1; i<num; i++){  //做 H->Size-1次合并   //此处教科书有问题！
		T = NewHuffmanNode();  //建立一个新的根结点 
		T->Left = DeleteMin(H);  //从最小堆中删除一个节点，作为新T的左子结点
		T->Right = DeleteMin(H);  //从最小堆中删除一个节点，作为新T的右子结点 
		T->Weight = T->Left->Weight+T->Right->Weight;  //计算新权值 
		Insert(H,T);  //将新T插入到最小堆 
	} 
	T = DeleteMin(H);
	
	return T; 
  } 
  
/************递归进行哈夫曼编码*************/
void HuffmanCode(HuffmanTree BST,int depth)  //depth为目前编码到哈夫曼树的深度（层次） 
{
	static int code[10];  //编码空间 
	
	if( BST ){
		if( (BST->Left == NULL) && (BST->Right == NULL)){  //找到了叶结点
			printf("字符%c的哈夫曼编码为：",BST->ch);
			for(int i=0; i<depth; i++){
				printf("%d",code[i]);
			}
			printf("\n");
		}else{
			code[depth] = 0;  //往左子树方向编码为0 
			HuffmanCode(BST->Left,depth+1);
			code[depth] = 1;  //往右子树方向编码为1 
			HuffmanCode(BST->Right,depth+1);
		}
	} 
}


HuffmanTree NewHuffmanNode()
{
	HuffmanTree BST = (HuffmanTree)malloc(sizeof(HuffmanNode));
	BST->Weight = 0;
	BST->Left = BST->Right = NULL;
	
	return BST;
 } 
  
MinHeap CreateMinHeap(int MaxSize)
{  /*创建容量为MaxSize的最小堆*/
	MinHeap H = (MinHeap)malloc(sizeof(struct HeapStruct));
	H->data = (HuffmanTree *)malloc((MaxSize+1) * sizeof(HuffmanTree));
	H->Size = 0;
	H->Capacity = MaxSize;
	HuffmanTree T = NewHuffmanNode();
	T->ch = '\0';  //空字符 
	T->Weight = MinData;  /*定义哨兵-为小于堆中所有可能元素权值的值，便于以后更快操作*/
	H->data[0] = T;
	
	return H;
}
 
bool  IsFull(MinHeap H)
{
	return (H->Size == H->Capacity);
}
 
bool IsEmpty(MinHeap H)
{
	return (H->Size == 0);
}
 
/*插入算法-将新增结点插入到从其父结点到根结点的有序序列中*/
bool Insert(MinHeap H,HuffmanTree item)
{/*将元素item插入到最小堆H中，其中H->data[0]已被定义为哨兵*/
	int i;
	if( IsFull(H) ){
		printf("最小堆已满\n");
		return false;
	}
	i = ++H->Size;  //i指向插入后堆中的最后一个元素的位置
	for(; H->data[i/2]->Weight > item->Weight; i/=2)  //无哨兵，则增加判决条件 i>1 
	    H->data[i] = H->data[i/2];  //向下过滤结点 
	H->data[i] = item;   //将item插入 
	
	return true;
 }
 
HuffmanTree DeleteMin(MinHeap H)
{/*从最小堆H中取出权值为最小的元素，并删除一个结点*/
	int parent,child;
	HuffmanTree MinItem,temp = NULL;
	if( IsEmpty(H) ){
		printf("最小堆为空\n");
		return NULL;
	}
	MinItem = H->data[1];  //取出根结点-最小的元素-记录下来
	/*用最小堆中的最后一个元素从根结点开始向上过滤下层结点*/
	temp = H->data[H->Size--];  //最小堆中最后一个元素，暂时将其视为放在了根结点
	for(parent=1; parent*2<=H->Size; parent=child){
		child = parent*2;
		if((child != H->Size) && (H->data[child]->Weight > H->data[child+1]->Weight)){/*有右儿子，并且左儿子权值大于右儿子*/
			child++; //child指向左右儿子中较小者 
		}
		if(temp->Weight > H->data[child]->Weight){
			H->data[parent] = H->data[child];  //向上过滤结点-temp存放位置下移到child位置 
		}else{
			break;  //找到了合适的位置
		}
	} 
	H->data[parent] = temp;  //temp存放到此处
	
	return MinItem; 
}
 
MinHeap BuildMinHeap(MinHeap H)
{/*这里假设所有的H->Size个元素已经存在H->data[]中*/
 /*本函数将H->data[]中的元素调整，使其满足堆的有序性*/ 
	int i,parent,child;
	HuffmanTree temp;
	for(i=H->Size/2;i>0;i--){  //从最后一个父结点开始，直到根结点 
		temp = H->data[i];
		for(parent=i; parent*2<=H->Size; parent=child){
		    /*向下过滤*/
			child = parent*2;
		    if((child != H->Size) && (H->data[child]->Weight > H->data[child+1]->Weight)){/*有右儿子，并且左儿子权值大于右儿子*/
			    child++; //child指向左右儿子中较小者 
		    }
		    if(temp->Weight > H->data[child]->Weight){
			    H->data[parent] = H->data[child];  //向上过滤结点-temp存放位置下移到child位置 
		    }else{
			    break;  //找到了合适的位置 
		    }
	    }/*结束内部for循环对以H->data[i]为根的子树的调整*/
		
		H->data[parent] = temp;  //temp（原H->data[i]）存放到此处  
	} 
	return H; 
}

收起

展开全文

哈夫曼编码及Matlab实现.docx
2020-11-19 15:33:24

PAGE / NUMPAGES 哈夫曼编码及Matlab实现 哈夫曼编码是一种所得码字是异前置的变长码,其平均码长最短,被称为最佳变长码,也称为哈夫曼编码 其具体编码方法如下 1将信源信息符号按概率大小排队 2从最小概率的两个消息...

收起
C语言哈夫曼编码转换
2020-03-11 21:23:28

使用基于c语言的哈夫曼树实现哈夫曼编码转换。给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度...

收起

堆排序实现哈夫曼树

2021-12-31 10:01:52

1.哈夫曼树：假设由m个权值{W1,W2,…,Wm}，可以构造一棵含m个叶子结点的二叉树，第i个叶子结点的权为Wi，则其中带权路径长度WPL最小的二叉树称作最优二叉树或哈夫曼树。 2.哈夫曼树的目的：找出存放一串字符所需的...

哈夫曼树

1.哈夫曼树：假设由m个权值{W1,W2,…,Wm}，可以构造一棵含m个叶子结点的二叉树，第i个叶子结点的权为Wi，则其中带权路径长度WPL最小的二叉树称作最优二叉树或哈夫曼树。
2.哈夫曼树的目的：找出存放一串字符所需的最少的二进制编码
3.哈夫曼树的建立：Huffman为了减少通信系统中字符编码所需要的二进制位长度，提出了用于产生不定长的前缀编码算法，所谓前缀编码是指任意一个编码都不是其它编码的前缀。前缀编码的思想就是对于出现概率较大的字符采用短编码方式，对于出现概率比较小的字符采用长编码方式。下面是一个具体实例。
在这里插入图片描述

在构造完成后，将二叉树向左的分支加上0，向右的分支加上1然后就可以得出每一个叶子节点的哈夫曼编码。

4.算法实现：
思路：首先将数据构造成最小堆。堆顶就是最小的元素，然后将堆顶的元素和堆里面的最后一个元素交换，将堆的最后一个元素也就是堆里面最小的元素删除并且返回给哈夫曼树的一个结点作为这个结点的左子树。然后用剩余的元素再次构成最小堆，重复上面的步骤。不过这一次是将这个元素作为结点的右子树。然后将这个结点的左右孩子的权值相加作为结点的权值，再将结点插入堆中。重复进行，直到最后堆里面只有一个结点。

#include<iostream>
#include<vector>
#include<queue>
using namespace::std;
typedef struct HuffmanNode
{
	int weight;  //权值
	struct HuffmanNode* lchild,*rchild;
};
struct MinHeap
{
	HuffmanNode* Node;  
	int Size;     //堆里面现在有的元素
	int MaxSize;  //堆里面可以容纳的最大元素
};

//交换两个结点
void Swap(MinHeap* H, int parent, int child)
{
	HuffmanNode mid = H->Node[parent];
	H->Node[parent] = H->Node[child];
	H->Node[child] = mid;
}
//生成最小堆
void HeapSort(MinHeap* H)
{
	int parent = H->Size / 2 - 1;
	for (int i = parent; i >= 0; i--)  //从有孩子节点的最后一个根节点开始
	{
		parent = i;
		int child = 2 * parent + 1;
		while (child < H->Size)    //将这个根节点变成一个最小堆
		{
			if (child+1<H->Size&&H->Node[child].weight > H->Node[child + 1].weight)  //如果右孩子的值比左孩子小，child则指向右孩子
			{
				child++;
			}
			if (H->Node[parent].weight > H->Node[child].weight)   //如果根节点的值小于左右节点中最小的那一个，则与小的那一个交换
			{
				Swap(H, parent, child);  //交换两个结点的值
				parent = child;
			}
			child = child * 2 + 1;
		}
	}
}
//创建并且初始化堆
MinHeap* CreatHeap(int a[], int len)
{
	MinHeap* H = new MinHeap;
	H->Node = new HuffmanNode[len];
	H->MaxSize = len;
	H->Size = 0;
	//初始化堆，将堆的每一个节点都初始化为Huffman结构
	for(int i = 0; i < len; i++)
	{
		H->Node[i].weight = a[i];
		H->Node[i].lchild = NULL;
		H->Node[i].rchild = NULL;
		H->Size++;
	}
	return H;
}

//删除最小的那个根节点并返回
HuffmanNode* DeleteHeap(MinHeap* H)
{
	HuffmanNode* res = new HuffmanNode;
	res->lchild = H->Node[0].lchild;
	res->rchild = H->Node[0].rchild;
	res->weight = H->Node[0].weight;

	Swap(H, 0, H->Size - 1);  //将堆里面的第一个元素和最后一个元素互换
	H->Size--;    //删除最后一个元素
	HeapSort(H);  //删除结点后，重新构成最小堆

	return res;
}
void InsertHeap(MinHeap* H, HuffmanNode* T)
{
	H->Size++;
	H->Node[H->Size - 1].weight = T->weight;
	H->Node[H->Size - 1].lchild = T->lchild;
	H->Node[H->Size - 1].rchild = T->rchild;

	HeapSort(H); //构成最小堆
}
//先序遍历
void PreOrder(HuffmanNode* t)
{
	if (t)
	{
		cout << t->weight<<" ";     //输出结点数据
		PreOrder(t->lchild);//访问左孩子
		PreOrder(t->rchild);//访问右孩子
	}
}
int main()
{
	int a[10] = { 10,9,8,7,6,5,4,3,2,1 };
	int len = sizeof(a) / sizeof(int);  //得到a的长度
	cout << "初始的序列为" << endl;
	for (int i = 0; i < len; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	MinHeap* H = CreatHeap(a, len);
	HeapSort(H);
	cout << "最小堆的数据：" << endl;
	for (int i = 0; i < len; i++)
		cout << H->Node[i].weight << " ";
	cout << endl;
	while (H->Size > 1)   //至少有两个结点
	{
		HuffmanNode* T = new HuffmanNode;
		T->lchild = DeleteHeap(H);  //删除最小堆里面那个权值最小的结点并返回删除的结点
		T->rchild = DeleteHeap(H);
		T->weight = T->lchild->weight + T->rchild->weight;
		InsertHeap(H, T);
	}
	HuffmanNode* Huffman = H->Node;
	cout << "哈夫曼树的序列是" << endl;
	//先序遍历
	PreOrder(Huffman);
}

收起

展开全文

霍夫曼树数据结构算法

解析C++哈夫曼树编码和译码的实现
2020-12-31 04:25:40

2.根据创建好的哈夫曼树创建一张哈夫曼编码表 3.输入一串哈夫曼序列，输出原始字符三．设计思想： 1.首先要构造一棵哈夫曼树，哈夫曼树的结点结构包括权值，双亲，左右孩子；假如由n个字符来构造一棵哈夫曼树，则...

收起

Java实现哈夫曼编码

2021-12-19 15:21:07

一、内容 ... 封装字符和对应哈夫曼编码的类：HuCode.class 2、方法 1> 构造哈夫曼树：CreatHuTree() 2> 在合并节点时，选择权重最小和次小的两个节点：selectIndexOfMinWeight(HuTN...

一、内容

1、内部类

1> 哈夫曼树节点类型：HuTNode.class

2> 封装节点在底层数组的下标和对应的权重的类：IndexAndWeight.class

3> 封装字符和对应哈夫曼编码的类：HuCode.class

2、方法

1> 构造哈夫曼树：CreatHuTree()

2> 在合并节点时，选择权重最小和次小的两个节点：selectIndexOfMinWeight(HuTNode ht)

3> 根据构造的哈夫曼树，获取叶子节点对应字符的哈夫曼编码：getHuCode(HuTNode ht)

4> 根据得到的哈夫曼编码集，将字符串转换成0101串：String2HuffmanCode(String source, String huffmanCode)

5> 根据得到的哈夫曼编码集，将0101串转换成字符串：HuffmanCode2String(String huffmanCode, String source)

二、代码

public class HuTree {

    public static void main(String[] args) {
        // 构建哈夫曼树
        HuTNode[] ht = creatHuTree();

        // 输出构造好的哈夫曼树
        System.out.println("\n===============输出构造好的哈夫曼树===================");
        System.out.println("下标\t\t数据\t\t权重\t\t双亲\t\t左孩\t\t右孩");
        System.out.println("0\t\t-\t\t-\t\t-\t\t-\t\t-\t\t");
        for (int i=1; i<ht.length; ++i){
            System.out.print(i + "\t\t");
            System.out.println(ht[i]);
        }

        // 根据哈夫曼树ht，将每个给定字符及其哈夫曼编码存储到一个HuCode类型数组中
        HuCode[] hc = getHuCode(ht);

        // 输出哈夫曼编码集hc
        System.out.println("\n===============哈夫曼编码集===================");
        System.out.println("数据\t\t哈夫曼码");
        for (HuCode code: hc){
            System.out.println(code);
        }

        // 给定字符串，根据上述哈夫曼编码转换成0101串
        String source = "A_Tree";
        String huffmanCode = String2HuffmanCode(source, hc);
        System.out.println("\n===============【A_Tree】对应的0101串===================");
        System.out.println(huffmanCode);

        // 解码由上述哈夫曼编码组成的0101串
        huffmanCode = "00100011000001";
        source = huffmanCode2String(huffmanCode, hc);
        System.out.println("\n===============【00100011000001】对应的字符串===================");
        System.out.println(source);

        huffmanCode = "00111001";
        source = huffmanCode2String(huffmanCode, hc);
        System.out.println("\n===============【00111001】对应的字符串===================");
        System.out.println(source);
    }


    /**
     * 功能：构造哈夫曼树
     * 说明：该哈夫曼树使用顺序存储的方式存储在一个HuTNode类型的数组中，且该数组0号下标不使用
     * @return 返回根据给定节点和权重构造的哈夫曼树
     */
    private static HuTNode[] creatHuTree() {
        // 输入控制
        Scanner in = new Scanner(System.in);
        System.out.print("请输入各叶子节点数据域的值，以空格分隔：");
        String[] nodes = in.nextLine().split(" ");
        System.out.print("请输入各叶子节点对应的权重：");
        String[] weights = in.nextLine().split(" ");

        // 初始化哈夫曼树
        int n = nodes.length;// 带权叶子节点数
        int m = 2*n;// 由于底层数组0号位置不存放节点，所以n个叶子节点合并生成哈夫曼树后，需要2n-1+1，即2n长度的数组
        HuTNode[] ht = new HuTNode[m];
        for (int i=0; i<n; ++i){
            HuTNode newNode = new HuTNode(nodes[i].charAt(0), Integer.valueOf(weights[i]));
            ht[i+1] = newNode;
        }

        // 选择权重最小的节点两两合并构造哈夫曼树
        for (int i=0; i<n-1; ++i){// n个叶子节点需要合并n-1次
            int[] arr = selectIndexOfMinWeight(ht);// 获取权重最小的两个节点的下标

            // 创建合并的新节点
            HuTNode newNode = new HuTNode();
            newNode.lChild = arr[0];
            newNode.rChild = arr[1];
            newNode.weight = ht[arr[0]].weight + ht[arr[1]].weight;
            ht[n+i+1] = newNode;// 此时底层数组中有效节点有n+i个，将新生成的节点保存在数组中时，下标应为n+i+1

            // 修改被合并节点的双亲域
            ht[arr[0]].parent = n+i+1;
            ht[arr[1]].parent = n+i+1;
        }

        return ht;
    }


    /**
     * 在所有节点双亲域的值是0节点中，选择两个权重最小的节点，并将他们在底层数组中的下标打包成数组进行返回
     * @param ht 底层数组
     * @return 最小权重节点的下标打包成的数组
     */
    private static int[] selectIndexOfMinWeight(HuTNode[] ht) {
        int[] arr = new int[2];

        List<IndexAndWeight> list = new LinkedList<>();
        int i = 1;
        while (ht[i] != null){
            if (ht[i].parent != 0){// 过滤掉存在双亲的节点
                ++i;
                continue;
            }

            list.add( new IndexAndWeight(i, ht[i].weight) );
            ++i;
        }

        // 根据权重从从小到大排序
        list.sort(new Comparator<IndexAndWeight>() {
            @Override
            public int compare(IndexAndWeight o1, IndexAndWeight o2) {
                if (o1.weight > o2.weight){
                    return 1;
                }else {
                    return -1;
                }
            }
        });

        arr[0] = list.get(0).index;
        arr[1] = list.get(1).index;

        return arr;
    }


    /**
     * 根据哈夫曼树ht，将每个给定字符及其哈夫曼编码存储到一个HuCode类型数组中
     * @param ht 哈夫曼树
     * @return 字符和对应哈夫曼编码组成的数组，即哈夫曼编码集
     */
    private static HuCode[] getHuCode(HuTNode[] ht) {
        int n = (ht.length+1)/2;// 叶子节点个数
        HuCode[] hc = new HuCode[n];


        // 从每个叶子节点回溯找其双亲节点，并根据每一次回溯的路径，保存0或1，知道找到根节点为止
        Stack<Character> stack = new Stack<>();// 用于保存回溯得到的0或1
        for (int i=1; i<=n; ++i){
            stack.clear();

            // 回溯，并将0或1入栈
            HuTNode child = ht[i];// 叶子节点
            int childIndex = i;
            while (child.parent != 0){
                int parentIndex = child.parent;
                HuTNode parent = ht[parentIndex];

                if (parent.lChild == childIndex){// child是parent的左孩子，将0入栈
                    stack.push('0');
                }else {// child是parent的右孩子，将1入栈
                    stack.push('1');
                }

                child = ht[child.parent];
                childIndex = parentIndex;
            }

            // stack按出栈顺序组成对应字符的哈夫曼编码，
            StringBuilder code = new StringBuilder("");
            while (!stack.isEmpty()){
                code.append(stack.pop());
            }

            // 保存在hc数组中
            hc[i-1] = new HuCode(ht[i].data, code.toString());
        }

        return hc;
    }


    /**
     * 根据给定的哈夫曼编码集，将指定字符串编码成0101串
     * @param source 字符串
     * @param hc 哈夫曼编码集
     * @return 0101串
     */
    private static String String2HuffmanCode(String source, HuCode[] hc) {
        StringBuilder huffmanCode = new StringBuilder("");

        for (int i=0; i<source.length(); ++i){
            char c = source.charAt(i);

            boolean flag = false;
            for (HuCode huCode: hc){
                if (huCode.data == c){
                    huffmanCode.append(huCode.code);
                    flag = true;// 表示编码成功
                }
            }

            if (!flag){
                throw new RuntimeException("【" + c + "】不存在对应的哈夫曼编码");
            }
        }

        return huffmanCode.toString();
    }


    /**
     * 根据给定的哈夫曼编码集，将指定0101串解码成字符串
     * @param huffmanCode 0101串
     * @param hc 哈夫曼编码集
     * @return 字符串
     */
    private static String huffmanCode2String(String huffmanCode, HuCode[] hc) {
        StringBuilder source = new StringBuilder("");
        StringBuilder tempCode = new StringBuilder("");

        for (int i=0; i<huffmanCode.length(); ++i){
            tempCode.append(huffmanCode.charAt(i));
            // 判断当前tempCode是否在哈夫曼编码集中
            for (HuCode huCode: hc){
                if ( huCode.code.equals(tempCode.toString()) ){
                    tempCode.delete(0, tempCode.length());// 清空tempCode
                    source.append(huCode.data);
                }
            }
        }

        if (!tempCode.toString().equals("")){
            throw new RuntimeException("【" + huffmanCode + "】解码失败！");
        }

        return source.toString();
    }


    //数组元素类（哈夫曼树节点类）
    static class HuTNode{
        char data;// 数据域
        int weight;// 权重
        int parent;// 双亲
        int lChild;// 左孩子
        int rChild;// 右孩子

        public HuTNode(char data, int weight) {
            this.data = data;
            this.weight = weight;
        }

        public HuTNode() {
        }

        @Override
        public String toString() {
            return this.data + "\t\t" + this.weight + "\t\t" + this.parent + "\t\t" + this.lChild + "\t\t" + this.rChild;
        }
    }

    // 用于合并节点时，筛选出权重最小两个节点用的内部类，封装了节点在底层数组中的下标，以及权重
    static class IndexAndWeight{
        int index;// 下标
        int weight;// 权重

        public IndexAndWeight(int index, int weight) {
            this.index = index;
            this.weight = weight;
        }
    }

    // 编码类，封装了字符及对应的哈夫曼编码
    static class HuCode{
        char data;
        String code;

        public HuCode(char data, String code) {
            this.data = data;
            this.code = code;
        }

        @Override
        public String toString() {
            return data + "\t\t" + code;
        }
    }
}

三、测试

收起

展开全文

java 霍夫曼树

Python 代码实现哈夫曼编码
千次阅读 2022-03-22 21:23:02

一、哈夫曼编码是什么？ 哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，可变字长编码(VLC)的一种...二、Python 代码实现哈夫曼编码 代码如下（示例）： from math import inf #初始化哈夫曼结点 cla

收起

python 霍夫曼树
哈夫曼编码及Matlab实现.doc
2020-05-19 23:45:39

- 欢迎下载 哈夫曼编码及Matlab实现 哈夫曼编码是一种所得码字是异前置的变长码其平均码长最短被称为最佳变长码也称为哈夫曼编码 其具体编码方法如下 1将信源信息符号按概率大小排队 2从最小概率的两个消息开始编码...

收起
数据结构5 哈夫曼树与哈夫曼编码_数据结构哈夫曼编码例题
2020-03-13 01:39:32

哈夫曼树与哈夫曼编码;哈夫曼树与哈夫曼编码;编码;前缀编码;前缀编码;树的路径长度定义为;最优二叉树的定义;最优二叉树的定义;最优二叉树的定义;最优二叉树的定义;哈夫曼树; 2.在 F 中选取其根结点的权值为最小的两...

收起
哈夫曼编码C++实现
千次阅读 2021-11-20 10:37:04

使用数组存储哈夫曼树进行哈夫曼编码

收起

数据结构 c++
实现哈夫曼树和哈夫曼编码
多人点赞 热门讨论 2022-03-06 08:28:49

哈夫曼树在日常生活中可以用于文件的压缩，所以是我们程序员必不可少的基本功，下面跟着小编我一起来实现哈夫曼树和编码吧！一.哈夫曼树的实现 (一).实现原理 哈夫曼树是一种特殊的二叉树我们先假设有一个森林...

收起

霍夫曼树数据结构算法 c语言 c++
哈夫曼编码 java实现
2022-02-07 19:29:24

用哈夫曼树压缩一个字符串，解压以后再写

收起

java 霍夫曼树数据结构
图文详解JAVA实现哈夫曼树
2020-09-01 20:04:57

所谓哈夫曼树就是要求最小加权路径长度，这是什么意思呢？简而言之，就是要所有的节点对应的路径长度（高度-1）乘以该节点的权值，然后保证这些结果之和最小。下面这篇文章就给大家详细介绍

收起
java实现哈夫曼编码
2021-02-26 12:27:40

java实现哈夫曼编码哈夫曼树既然是学习哈夫曼编码，我们首先需要知道什么是哈夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman ...

收起
数据结构C语言实现哈夫曼编码、译码
千次阅读 2021-08-29 22:24:43

简单实现哈夫曼编码译码过程，简单易懂` #include<stdio.h> #include<string.h> #include<stdlib.h> #include<conio.h> typedef struct{ char ch; //字符 int weight; //权值 int ...

收起

数据结构 c语言算法
汇编32位实现哈夫曼编码（超详细）
2021-07-10 17:01:45

用汇编语言实现Huffman编码算法。要求输出给定字符集的Huffman编码及其Huffman树的带权路径长度WPL，假设用于通信的电文仅由a、b、c、d、e、f、g、h等字母组成，字母在电文中出现的频率分别为：0.07、0.19、0.02、...

收起
算法分析与设计实验报告——实现哈夫曼编码
千次阅读 2021-02-02 11:13:42

算法分析与设计实验报告——实现哈夫曼编码 目录：算法分析与设计实验报告——实现哈夫曼编码一、实验目的二、实验要求三、实验原理四、实验过程(步骤)五、运行结果六、实验分析与讨论七、实验特色与心得附件一 ...

收起

算法 c++ 数据结构贪心算法
C语言实现哈夫曼编码与译码
2021-05-20 11:23:25

字符集中的字符的使用频率是不同的(比如e和t的使用较之q和z要频繁得多)，哈夫曼编码可以使得编码的总长最短，从而相同的位长可以传送更多的信息。本程序以下面的字符及使用频率为例：字符权值a0.12b0.40c0.15d0.08e...

收起
哈夫曼编码及Matlab实现资料.docx
2020-06-02 06:29:47

哈夫曼编码及Matlab实现精品文档精品文档收集于网络如有侵权请联系管理员删除收集于网络如有侵权请联系管理员删除精品文档收集于网络如有侵权请联系管理员删除 哈夫曼编码及Matlab实现 哈夫曼编码是一种所得...

收起
哈夫曼编码的实现
千次阅读 2021-04-01 20:45:50

哈夫曼编码哈夫曼树简介哈夫曼编码的实现原理哈夫曼树的存储结构哈夫曼树简介 哈夫曼编码的实现原理哈夫曼树的存储结构

收起

数据结构队列二叉树
C++ 实现哈夫曼树和哈夫曼编码
2020-12-20 15:04:47

C++ 实现哈夫曼树哈夫曼树的定义 哈夫曼树的定义将树中的结点赋予一个有某种意义的数值，称此数值为该结点的权。从树根结点到该结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度。树中所有叶子结点...

收起
贪心算法：使用贪心算法实现哈夫曼编码
千次阅读 2021-04-02 15:41:48

这篇文章我们开始看看贪心算法和它的实际应用，贪心算法有很多经典的应用：哈夫曼编码、Prim和Kruskal最小生成树算法、Dijkstra单源最短路径算法 1、如何理解贪心算法贪心算法的思想是:每次都做出当前最优的选择，...

收起

算法
哈夫曼编码原理分析及代码实现（有注释）
千次阅读 2022-04-06 12:40:22

实现方法：构建哈夫曼树：每次从数的集合中取出没有双亲且权值最小的两棵树作为左右子树（贪心的思想），构建一棵新树，新树的根节点的权值为其左右孩子结点权值之和，将新数插入到数的集合中，通过n-1次这样的合并...

收起

c++ 算法
Python实现哈夫曼编码（Huffman code）
千次阅读 2021-12-15 14:53:43

如题，通过python实现哈夫曼编码，代码如下： 哈夫曼编码的思想为：在节点中每次找出两个出线频次最低的组合在一起，当迭代到最后只剩下一个节点时，该节点就为根节点，所有节点构成了huffman树，通过对树的左右孩子...

收起

python 开发语言
C语言哈夫曼树的实现及递归实现哈夫曼编码
千次阅读 2020-10-22 20:01:10

构建哈夫曼树算法的实现可以分为两大部分。（1）初始化：首先动态申请2n个单元；然后循环2n-1次，从1号单元开始，依次将1至2n-1所有单元中的双亲、左孩子、右孩子的下标都初始化为0；最后再循环n次，输入前n个单元...

收起

数据结构 c语言哈夫曼树递归
C++实现哈夫曼树与哈夫曼编码
千次阅读 多人点赞 2019-06-02 09:51:08

哈夫曼树的存储表示 typedef char ElemType; typedef struct { ElemType data; //结点存的数据 int weight; //结点的权值 int parent,lchild,rchild; //结点的双亲、左孩子、右孩子的下标 } HTNode,*HuffmanT...

收起

哈夫曼树

哈夫曼树：带权路径长度最小的二叉树（最优二叉树）

如何找到权值最小的结点？——最小堆

最小堆的数据结构定义

-生成一个空的最小堆

-创建最小堆

-最小堆的插入

-最小堆的删除

将找到的最小结点合并——哈夫曼树的构造

链表实现

数组实现

哈夫曼编码

利用最小堆实现哈夫曼树

最小堆实现哈夫曼树的构造及哈夫曼编码、解码

最小堆建哈夫曼树

测试用例：

增加了哈夫曼编码、解码

测试用例：

哈夫曼编码及Matlab实现.docx

C语言哈夫曼编码转换

堆排序实现哈夫曼树

哈夫曼树

解析C++哈夫曼树编码和译码的实现

Java实现哈夫曼编码

一、内容

二、代码

三、测试

Python 代码实现哈夫曼编码

哈夫曼编码及Matlab实现.doc

数据结构5 哈夫曼树与哈夫曼编码_数据结构哈夫曼编码例题

哈夫曼编码C++实现

实现哈夫曼树和哈夫曼编码

哈夫曼编码 java实现

图文详解JAVA实现哈夫曼树

java实现哈夫曼编码

数据结构C语言实现哈夫曼编码、译码

汇编32位实现哈夫曼编码（超详细）

算法分析与设计实验报告——实现哈夫曼编码

C语言实现哈夫曼编码与译码

哈夫曼编码及Matlab实现资料.docx

哈夫曼编码的实现

C++ 实现哈夫曼树和哈夫曼编码

贪心算法：使用贪心算法实现哈夫曼编码

哈夫曼编码原理分析及代码实现（有注释）

Python实现哈夫曼编码（Huffman code）

C语言 哈夫曼树的实现及 递归实现哈夫曼编码

C++实现哈夫曼树与哈夫曼编码

最小堆实现哈夫曼编码

C语言哈夫曼树的实现及递归实现哈夫曼编码