哈夫曼樹(shù)又稱最優(yōu)二叉樹(shù)，是一類帶權(quán)路徑長(zhǎng)度最短的樹(shù)。

成都創(chuàng)新互聯(lián)主營(yíng)茶陵網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營(yíng)網(wǎng)站建設(shè)方案,成都app軟件開(kāi)發(fā),茶陵h5微信平臺(tái)小程序開(kāi)發(fā)搭建,茶陵網(wǎng)站營(yíng)銷推廣歡迎茶陵等地區(qū)企業(yè)咨詢

當(dāng)計(jì)算構(gòu)造哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度時(shí)我們可以使用常規(guī)方法進(jìn)行計(jì)算，這里就不展開(kāi)介紹了，我們?cè)谶@里給大家介紹一種簡(jiǎn)便方法，請(qǐng)看下圖：

通過(guò)這種簡(jiǎn)便方法，我們就可以很方便的設(shè)計(jì)相關(guān)算法了。

問(wèn)題描述

假設(shè)用于通信的電文由ｎ個(gè)字符組成，字符在電文中出現(xiàn)的頻度（權(quán)值）為w1,w2,…,wn，試根據(jù)該權(quán)值序列構(gòu)造哈夫曼樹(shù)，并計(jì)算該樹(shù)的帶權(quán)路徑長(zhǎng)度。

輸入說(shuō)明

第１行為ｎ的值，第２行為ｎ個(gè)整數(shù)，表示字符的出現(xiàn)頻度。

輸出說(shuō)明

輸出所構(gòu)造哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度。

輸入樣例

8

7 19 2 6 32 3 21 10

輸出樣例

261

#include#define INF 65535

struct huffman {
	int weight;
	int parent, lchild, rchild;
}HT[1001]; 

void createHT(int n);
int main()
{
	int n; 
	scanf("%d", &n);
	int i, sum = 0;
	createHT(n);
	for (i = n; i< 2 * n - 1; i++)		//由于新節(jié)點(diǎn)序號(hào)是從n->2n-1，由此確定累加范圍
		sum += HT[i].weight;
	printf("%d\n", sum);
	return 0;
}

void createHT(int n)
{
	int i, j;
	for (i = 0; i< 2 * n - 1; i++)
		HT[i].parent = HT[i].lchild = HT[i].rchild = -1;	//初始化 

	for (i = 0; i< n; i++)
		scanf("%d", &HT[i].weight);		//初始化 

	int a, b;		//表明第幾個(gè) 
	int a1, b1;		//表明對(duì)應(yīng)權(quán)重 
	for (i = 0; i< n - 1; i++)
	{
		a1 = b1 = INF;
		for (j = 0; j< n + i; j++)
		{
			if (HT[j].parent == -1 && HT[j].weight< a1)	//尋找比a1權(quán)重小，且沒(méi)有雙親結(jié)點(diǎn)的結(jié)點(diǎn) 
			{
				b = a;		//如果有，將次小的順序賦值給b 
				a = j;		//a變?yōu)樽钚〉男蛱?hào) 
				b1 = a1;	//次小權(quán)重賦值b1
				a1 = HT[j].weight;	//最小權(quán)重賦值a1 
			}
			else if (HT[j].parent == -1 && HT[j].weight< b1)		//有可能是權(quán)重大于a小于b,再次進(jìn)行判斷 
			{
				b = j;
				b1 = HT[j].weight;
			}
		}

		HT[n + i].weight = HT[a].weight + HT[b].weight;		//選用兩小造新樹(shù) 
		HT[n + i].lchild = a;		//雙親的孩子結(jié)點(diǎn) 
		HT[n + i].rchild = b;
		HT[a].parent = HT[b].parent = n + i;  	//雙親結(jié)點(diǎn)的序號(hào) 
	}
}

歡迎大家關(guān)注：https://github.com/XDUgaile

寫完的一些東西會(huì)不定時(shí)丟上去。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站欄目：XDOJ-275哈弗曼樹(shù)-創(chuàng)新互聯(lián)
分享地址：http://chinadenli.net/article42/cohgec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、自適應(yīng)網(wǎng)站、關(guān)鍵詞優(yōu)化、軟件開(kāi)發(fā)、企業(yè)網(wǎng)站制作、網(wǎng)站設(shè)計(jì)公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)