wuliaonimei博客
随机文章
随机文章

哈夫曼树的java实现

时间:2016年03月27日  分类:算法  标签:java,算法,哈夫曼  评论:0




前言

0T[LRFC5OA[H2~_N2J$SZQP.jpg妈蛋一篇文章写了3便都没保存。。  之所以这么久都没写文章一是因为工作。二是因为现在看看看以前写的东西实在是太屎了。

下面给出实现的过程。

(1)对List集合中所有节点进行排序。

(2)找出List集合中权值最小的两个节点

(3)以权值最小的两个节点作为子节点创建新节点。

(4)从List集合中删除权值最小的两个节点,将新节点添加到List集合中。


import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;


public class HuffmanTree {
	
	public static class Node<E> {
		private Node lchild;
		private Node rchild;
		private E data;
		private double weight;
		
		public Node() {
			
		}
		
		public Node(E data, double d) {
			this.data = data;
			this.weight = d;
		}

		public String toString()  
        {  
            return "Node[data=" + data  
                + ", weight=" + weight + "]";  
        }
	}
	
	public HuffmanTree2() {
		// TODO Auto-generated constructor stub
	}
	
	public static Node createTree(List<Node> nodes) {
		//节点数大于2时才开始创建
		if(nodes.size() > 1) {
			//获取最小的两个几点
			Node lchild = nodes.get(0);
			Node rchild = nodes.get(1);
			//创建新节点
			Node parent = new Node(null, lchild.weight + rchild.weight);
			parent.lchild = lchild;
			parent.rchild = rchild;
			//删除节点
			nodes.remove(0);
			nodes.remove(0);
			nodes.add(parent);
			createTree(nodes);
		}
		return nodes.get(0);
	}
	
	/**
	 * 对节点快速排序 实现节点从小到大排序
	 * @param list
	 * @param l 
	 * @param r
	 */
	public static void subSort(List<Node> list, int l, int r) {
		if(l < r) {
			int i = l;
			int j = r;
			Node base = list.get(i);
			
			//从右向左遍历找出第一个小于基准的节点
			while(i < j && list.get(j).weight >= base.weight) j--;
			
			//将查找到小于基准的节点调换到左边
			if(i < j) list.set(i++, list.get(j));
			
			//从左向右找到第一个大于基准权重的节点
			while(i < j && list.get(i).weight < base.weight) i++;
			
			//将查找到的大权重节点调换到右边 
			if(i < j) list.set(j--, list.get(i));
			
			//经过前面的排序我们能得到base.weight<lise.get(j)=list.get(i)
			list.set(i, base);
			//递归调用
			subSort(list, l, i-1);
			subSort(list, i+1, r);
		}
	}
	
	public static void quickSort(List<Node> list) {
		subSort(list, 0, list.size() - 1);
	}
	
	//前序遍历
	public static void preSort(Node node) {
		if(node != null) {
			System.out.println(node.toString());
			preSort(node.lchild);
			preSort(node.rchild);
		}
	}

	public static void main(String[] args) {
	    // TODO Auto-generated method stub
	    HuffmanTree huf = new HuffmanTree();
	    List<Node> nodes = new ArrayList<>();
	    nodes.add(new Node("A" , 40.0));
            nodes.add(new Node("B" , 8.0));
            nodes.add(new Node("C" , 10.0));
            nodes.add(new Node("D" , 30.0));
            nodes.add(new Node("E" , 10.0));
            nodes.add(new Node("F", 2.0));
            
            Node node = huf.createTree(nodes);
            preSort(node);
    //        huf.quickSort(nodes);
    //        for (Iterator iterator = nodes.iterator(); iterator.hasNext();) {
    //			Node node = (Node) iterator.next();
    //	        System.out.println(node.toString());
    //        }
	}

}







你可能也喜欢

评论列表

回复

你正在以游客身份访问网站,请输入你的昵称和 E-mail

Copyright ©2014-2015 Develop by Skilly. Go to the Top