【哈夫曼树】一道奇怪的哈夫曼编码题目 - 木东驿站 - Powered by MoodBlog

CONTENT

【哈夫曼树】一道奇怪的哈夫曼编码题目

上学期数据结构上机课上,我用很简单的方法实现了哈夫曼树和哈夫曼编码。最近在C语言网刷题,遇到了一道关于哈夫曼编码的题目,输出的结果一直和题目不一致,我一度怀疑自己写错了算法。

折腾了一晚上,发现算法并没有错,是那道题采用的左右子节点判断相当奇怪。

一般而言,哈夫曼树对于左右节点并无要求,谁左谁右都可以,只不过一般情况下我们让左节点小于右节点,或者右节点小于左节点。

可是那道题并不是这样的结果,而是:搜索2个权重最低的没有父节点的节点,先搜到谁,谁就在左边,后搜到谁,谁就在右边。幸好我特么机智,发现了这个规律,成功AC。


以下为原题:

输入

输入的第一行包含一个正整数n,表示共有n个字符需要编码。其中n不超过100。

第二行中有n个用空格隔开的正整数,分别表示n个字符的权值。

输出

共n行,每行一个字符串,表示对应字符的赫夫曼编码。

样例输入

8
5 29 7 8 14 23 3 11

样例输出

0110
10
1110
1111
110
00
0111
010

JAVA代码

import java.util.Scanner;
public class Main{ 
	public static void main(String[] args){
		int n=0,temp=0;
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		String[] res = new String[n];
		HTNode[] nodes = new HTNode[n*2];
		for(int i=0;i<n*2;i++){
			nodes[i] = new HTNode();
			if(i<n){
				temp = scanner.nextInt();
				nodes[i].data = nodes[i].weight = temp;				
			}
		}
		HTree.CreateHT(nodes);
		HTree.getHCode(nodes,res);
		for(int i=0;i<res.length;i++){
			System.out.println(res[i]);
		}
		
	}
}
class HTNode{
	 int data;
	 int weight;
	 int parent;
	 int lchild;
	 int rchild;
}
class HTree{
	static void CreateHT(HTNode ht[]){
		int n = ht.length/2;
		int lnode=0,rnode=0;
		int min1=0,min2=0;
		for(int i=0;i<2*n-1;i++){
			ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
		}
		for(int i=n;i<n*2-1;i++){
			min1 = min2 = 32250;
			lnode = rnode = -1;
			for(int k=0;k<i;k++){
				if(ht[k].parent==-1){
					if(ht[k].weight<min1){
						min2 = min1;
						rnode = lnode;
						min1 = ht[k].weight;
						lnode = k;
					}else if(ht[k].weight<min2){
						min2 = ht[k].weight;
						rnode = k;
					}
				}
			}
			if(lnode>rnode){
				int temp = lnode;
				lnode = rnode;
				rnode = temp;
			}
			ht[i].weight = ht[lnode].weight + ht[rnode].weight;
			ht[i].lchild = lnode;
			ht[i].rchild = rnode;
			ht[lnode].parent = ht[rnode].parent = i;
		}
	}
	static void getHCode(HTNode[] ht,String[] res){
		for(int i=0;i<ht.length/2;i++){
			char[] data = new char[100]; 
			int start = 99;
			int temp1 = i;
			int temp2 = ht[i].parent;
			while(temp2!=-1){
				if(ht[temp2].lchild==temp1){
					data[start--] = '0';
				}else{
					data[start--] = '1';
				}
				temp1 = temp2;
				temp2 = ht[temp2].parent;
			}
			res[i] = new String(data,start+1,99-start);
		}
	}
}


个快快 2017年11月11日 天气 晴

REMARKS

© 2018 MoodBlog 0.2 个快快 作品 | 参考主题: mathilda by fuzzz. | 鲁ICP备16047814号