数据结构-哈弗曼树的创建

﹏ヽ暗。殇╰゛Y 2022-05-18 06:06 169阅读 0赞

1.  哈弗曼树的创建
2.  带权路径长度的计算

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include <iomanip>
    using namespace std;
    
    typedef struct{
    	//定义节点的结构体 
    	int weight;//权重 
    	int parent, lChild, rChild;//双亲节点的下标、左孩子下标、右孩子下标 
    }HTNode, *HuffmanTree;
    
    //选择所有节点中权重最小的两个节点的下标 
    void SelectMin(HuffmanTree hT, int n, int &s1, int &s2)
    {
    	s1 = s2 = 0;
    	int i;
    	for(i = 1; i < n; i++)
    	{
    		// 首先找到两个没有双亲节点的节点下标 
    		if(hT[i].parent == 0)
    		{
    			if(0 == s1)
    			{
    	            s1 = i;
    	        }
    	        else
    			{
    				s2 = i;
    				break;
    			}
    		}
    	}
    	if(hT[s1].weight > hT[s2].weight) 
    	{
    		// 保证s1所指节点的权重小于s2所指节点的权重 
    		int t = s1;
    		s1 = s2;
    		s2 = t;
    	}
    	for(i+=1; i < n; i++)
    	{
    		if(hT[i].parent == 0)
    		{
    			/*
    				遍历没有双亲节点的所有节点
    				找到的节点权重如果比s1所指节点权重小,则更新s1节点让其指向当前节点
    				保证s1指向的权重最小的节点 
    			*/ 
    			if(hT[i].weight < hT[s1].weight)
    			{
    				s2 = s1;
    				s1 = i;
    			}
    			else if(hT[i].weight < hT[s2].weight)
    			{
    				/*
    					如果当前节点的权重大于s1所指节点的权重，但是小于s2所指节点的权重
    					那么更新s2节点，让其指向当前节点
    					保证s2指向的除了s1之外最小的节点 
    				*/ 
    				s2 = i; 
    			}
    		}
    	}
    }
    
    void CreateHuffmanTree(HuffmanTree &ht)
    {
    	// 8 5 29 7 8 14 23 3 11
    	
    	// n:表示要构造的哈夫曼树的叶子节点个数 
    	// m:表示所有节点的个数 
    	int n, m;
    	// 输入叶子节点的个数 
    	cin>>n; 
    	m = 2 * n - 1; 
    	// 构造m+1个节点，其中下标为0的不用 
    	ht = (HuffmanTree)malloc((m+1) * sizeof(HTNode));
    	for(int i = 1; i <= m; i++)
    	{
    		/*
    			初始化所有节点的孩子节点和双亲节点为0 
    		*/ 
    		ht[i].parent = 0;
    		ht[i].lChild = 0;
    		ht[i].rChild = 0;
    	 } 
    	 for(int i = 1; i <= n; i++)
    	 {
    	 	cin>>ht[i].weight;
    	 }
    	 // 第一个节点的权重存储所有节点的个数 
    	 ht[0].weight = m;
    	 
    	 /***********初始化完成，开始构建哈夫曼树**********/
    	 for(int i = n + 1; i <= m; i++)
    	 {
    	 	// i表示现已有节点个数+1 ,新合成的节点就放在i的位置上 
    	 	int s1, s2;
    	 	SelectMin(ht, i, s1, s2);
    	 	
    	 	/*
    		 	s1和s2所指节点构成新的节点放在i的位置上
    			更新i的左孩子为s1，右孩子为s2，权重为s1的权重加上s2的权重 
    			更新s1和s2的双亲节点为i 	
    		*/ 
    	 	ht[s1].parent = ht[s2].parent = i; 
    		ht[i].lChild = s1;
    		ht[i].rChild = s2;
    		ht[i].weight = ht[s1].weight + ht[s2].weight; 
    	 }
    }
    
    int HuffmanTreeWPL_(HuffmanTree hT, int i, int deepth) 
    {
    	/*
    		递归计算某个节点的带权路径 
    	*/ 
    	if(hT[i].lChild == 0 && hT[i].rChild == 0)
    	{
    		return hT[i].weight * deepth;
    	}
    	else
    	{
    		return HuffmanTreeWPL_(hT, hT[i].lChild, deepth+1) + HuffmanTreeWPL_(hT, hT[i].rChild, deepth+1) ;
    	}
    }
    int HuffmanTreeWPL(HuffmanTree hT)
    {
    	// 返回整棵树的带权路径长度 WPL 
        return HuffmanTreeWPL_(hT, hT[0].weight, 0);
    }
    void Print(HuffmanTree hT)
    {
        cout << "index weight parent lChild rChild" << endl;
        cout << left;    // 左对齐输出 
        for(int i = 1, m = hT[0].weight; i <= m; ++ i){
        	//setw()函数表示固定输出字符的长度 
            cout << setw(5) << i << " ";
            cout << setw(6) << hT[i].weight << " ";
            cout << setw(6) << hT[i].parent << " ";
            cout << setw(6) << hT[i].lChild << " ";
            cout << setw(6) << hT[i].rChild << endl;
        }
    }
    void DestoryHuffmanTree(HuffmanTree &hT)
    {
    	//销毁哈夫曼树 
        free(hT);
    }
    int main()
    {
        HuffmanTree hT;
        CreateHuffmanTree(hT);
        Print(hT); 
        cout << "WPL = " << HuffmanTreeWPL(hT) << endl;
        DestoryHuffmanTree(hT);
        return 0;	
    }

运行结果如下：

![70][]

*参考：[https://blog.csdn.net/luoluozlb/article/details/52122874][https_blog.csdn.net_luoluozlb_article_details_52122874]*

[70]: /images/20220518/1d007c352dc9480db078a6ae702ef7a8.png
[https_blog.csdn.net_luoluozlb_article_details_52122874]: https://blog.csdn.net/luoluozlb/article/details/52122874

发表评论取消回复

表情：

评论列表（有 0 条评论，169人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构与算法-构造哈弗曼树【十二】

哈弗曼树的定义哈佛曼树的定义：带权路径长度最短的树。每一个叶子节点有一个权重值，权重值乘以路径长度【路径长度指的是根节点到该节点的路径长度】，所有叶子节

爱被打了一巴掌/ 2023年02月22日 08:14/ 0 赞/ 16 阅读

相关数据结构——哈弗曼编码问题

实验六基于哈夫曼树的数据压缩算法【实验目的】 1. 掌握哈夫曼树的构造算法。 2. 掌握哈夫曼编码的构造算法。【实验内容】问题描述

缺乏、安全感/ 2022年12月28日 06:58/ 0 赞/ 138 阅读

相关二叉树之_哈夫曼树_哈弗曼编码

哈夫曼树又称最优二叉树给定N个权值作为N个[叶子结点][Link 1]，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈

柔光的暖阳◎/ 2022年12月13日 14:13/ 0 赞/ 268 阅读

相关构造哈弗曼树

include<iostream> using namespace std; struct HTreeNode{ int weight;

太过爱你忘了你带给我的痛/ 2022年08月20日 12:24/ 0 赞/ 14 阅读

相关哈弗曼树

本文转载自他人 [原文链接][Link 1] 一、哈夫曼树的概念和定义什么是哈夫曼树？让我们先举一个例子。判定树：在很多问题的处理过程中，需要进行

野性酷女/ 2022年07月12日 08:00/ 0 赞/ 173 阅读

相关【数据结构】中的哈弗曼树-HuffmanTree

概念：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径

我不是女神ヾ/ 2022年06月18日 09:12/ 0 赞/ 190 阅读

相关数据结构：Huffman哈弗曼编码长度

Huffman哈弗曼编码长度直接排序然后做即可代码如下 include <iostream> include <vector> inc

水深无声/ 2022年05月31日 12:55/ 0 赞/ 210 阅读

相关数据结构-哈弗曼树的创建

1. 哈弗曼树的创建 2. 带权路径长度的计算 include<iostream> include<cstdio> include<cstring

﹏ヽ暗。殇╰゛Y/ 2022年05月18日 06:06/ 0 赞/ 170 阅读

相关 HDU5884 二分+哈弗曼树

[传送门][Link 1] huffman模板，如果每次取k个能取完，num=k，取不完先将n%（k-1）取完，再每次取k include<bits/stdc++.

深藏阁楼爱情的钟/ 2022年05月15日 09:56/ 0 赞/ 183 阅读

相关【数据结构】树：哈夫曼树（Huffman Tree，也称哈弗曼、赫夫曼树）、哈夫曼编码解析与实现（c++）

\笔记整理树的定义参照前文： [二叉树、遍历二叉树与线索二叉树等树的定义与解析、二叉树遍历实现][Link 1] 哈夫曼树（也称赫夫曼树）相

痛定思痛。/ 2021年12月04日 01:01/ 0 赞/ 319 阅读