哈夫曼树

          

 

     国庆七天过去了。。哈夫曼本应该是国庆节之前的任务，可是我拖到现在才写完。。

 

     切入正题：哈夫曼编码~~~

 

     刚开始写的很晕呼呼的，不知道从何入手，然后多亏了大辉的提点，我开始找到了思路。感谢大辉~

 

     我的哈夫曼树~~有好几个函数

 

     1、输入字符串。。。。。不多说了

 

     2、统计字符串

 

               我用的方法是循环遍历那个输入的字符串，把他们放到一个Node的队列里面，如果遍历到重复的字符，就把那个字符所在结点的Amount加一。但是我遇到好几个问题。刚开始我统计字符串的时候，比如说abbcbb，那就会出现两个b结点，只要相同的字符中间还有字符隔着，就不会在原先的结点里把Amount加一，后来经过翔同学的细心检查，发现是我在进行是否有相同元素判断的时候忘记加了break。多谢翔同学。还有个问题，我现在也不知道为什么，就是第一次遇到这个字母的时候，他的Amount得设为0，而不是1，否则出来的结果会比实际总数多1。

 

          

	//对输入的字符串进行统计
	public void Summary(String string){
	
		NL = new LinkedList<Node>();
		//把第一个字母放到结点里
		char c = string.charAt(0);
		
		Node node = new Node();	
		
		node.setContent(c);
		
		node.setAmount(0);
		
		NL.add(node);
		//遍历剩下的字母
		for(int i =0;i<string.length();i++){
			
			c = string.charAt(i);
			
			for(int j =0;j<NL.size();j++){
				
				char t = NL.get(j).getContent();
				
				//如果有重复的元素,则结点里的总数加一
				if(c==t){
					
					NL.get(j).setAmount(NL.get(j).getAmount()+1);	
					break;
				
				}
				
				//遍历到底并且还是没有重复的元素
				else if(j==NL.size()-1){
					Node n = new Node();	
					
					n.setContent(c);
					
					n.setAmount(0);
					
					NL.add(n);
				}
			}	
			}	
	}

 

          

 

     3、排序

 

                    我用了冒泡排序，简单便捷的排序~你值得拥有。

 

 

     4、建树

 

                 建树什么的太头疼了。建了好几遍都错。后来发现不是我建树的问题。。是我遍历的问题。所以才会让输出结果有问题。。所以建树也没什么问题了。。

 

                 我是新建了一个名为‘#’的结点，让他的Amount等于两个结点的和，然后给他赋了左右孩子。然后把他加到队列里面再进行排序。

 

   5、编码

 

                  编码其实主要就是遍历，刚开始思路不清晰，不知道遍历什么乱七八糟的。所以输出来也不知道是什么东西。后来理清思路，用中序遍历遍历了那个树

	public boolean Code_1(Node root,String s){
		
		
		if (root!=null) {
			
			if (Code_1(root.getLchildNode(),s+'0')) {
				
					root.getLchildNode().setCode(s+'0');
					
				if (Code_1(root.getRchildNode(),s+'1')) {
					
					root.getRchildNode().setCode(s+'1');	
					
						return true;			
				}
				}
		}else {
			return false;
		}
		
		return true;
		
		}