我是爱种树的好菇凉之哈夫曼树

1、哈夫曼树及其构建

哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+ Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。

他的构建方式为：

首先先将离散节点从小到大升序排序

第二从离散节点中在挑选排序前两个节点当做一个新的父节点的两个子节点

第三从离散的节点中去除刚刚使用的两个节点

第四重复第二和第三步骤，直到所有离散节点剔除完毕。哈夫曼树就构建完成

 2、哈夫曼树的编码方式

遵循左子树编号为0，右子树编号为1的方式

3、实现哈弗曼树的构建，遍历，编码

 

package Huffman;



public class Node<T> {

	// 数据
	T data;
	// 权重
	int power;
	//编码，初始化为空
	String coding = "";
	Node<T> leftNode;

	Node<T> rightNode;
	

	public Node(T data,int power) {
		this.power = power;
		this.data = data;
	}
	public String toString() {
		// TODO Auto-generated method stub
		return "[data:" + data + "   power:" + power + "]";
	}

	@SuppressWarnings("unchecked")
	public boolean compareTo(Node node) {

		if (this.power < node.power) {
			return true;
		}

		return false;
	}
	public Node<T> getLeftNode() {
		return leftNode;
	}
	public void setLeftNode(Node<T> leftNode) {
		this.leftNode = leftNode;
	}
	public Node<T> getRightNode() {
		return rightNode;
	}
	public void setRightNode(Node<T> rightNode) {
		this.rightNode = rightNode;
	}
	public String getCoding() {
		return coding;
	}
	public void setCoding(String coding) {
		this.coding = coding;
	}
}

 创建哈夫曼树

/**
	 * 创建哈夫曼树
	 * 
	 * @param list
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public static  Node createHuffmanTree(List<Node> list) {

		while (list.size() > 1) {
			sort(list);
			//实例化左节点，此时list中存储的已经是排好序的数据
			Node left = list.get(list.size() - 1);
            //实例化右节点
			Node right = list.get(list.size() - 2);
            //构造父节点，节点中存储的字符为空，权值为两子树权值之和
			Node parent = new Node(null,left.power + right.power);
            //将两子节点与parent连接
			parent.leftNode = left;
			parent.rightNode = right;
            //把最小的两个删除
			list.remove(list.size() - 1);
			list.remove(list.size() - 1);
            //将parent添加到队列中
			list.add(parent);
		}
		//返回第一个节点
		return list.get(0);
	}

 **关于list.remove(int i);

是 java.util.List<E>中的一种方法，其中List<E>接口是有序的 collection（也称为序列）。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。

它允许重复的元素存在。

它中间一些常用的方法
 

boolean

add(E e)           向列表的尾部添加指定的元素（可选操作）。

 

void	clear()           从列表中移除所有元素（可选操作）。

boolean

isEmpty()           如果列表不包含元素，则返回 true。

 

E	remove(int index)           移除列表中指定位置的元素（可选操作）。

 

这些在API文档中均可以查找到

接下来是遍历输出

//中序遍历输出，两个字母合成的父节点的data为0
	public static void inOrder(Node root){  
        if(root==null){return;}  
        inOrder(root.getLeftNode());  
        System.out.println("data is:  "+root.data+"    power is:  "+root.power);  
        inOrder(root.getRightNode());  
    }  

 编码

//对list中的元素进行编码
	public  static< T> void generateHuffmanCode(Node< T> root){
		if (root==null) return;
		
	       if(root.getLeftNode()!=null) 
	           root.getLeftNode().setCoding(root.getCoding()+"0");
	       if(root.getRightNode()!=null) 
	          root.getRightNode().setCoding(root.getCoding()+"1");
	       if(root.data != null)       
	       System.out.println(root.data+"的编码是"+root.coding);
	       generateHuffmanCode(root.getLeftNode());
		generateHuffmanCode(root.getRightNode());
	    }

//冒泡排序，将哈夫曼树中的节点按权值大小排序
	public static  void sort(List<Node> list) {  
  
        for (int i = 0; i < list.size() - 1; i++) {  
  
            for (int j = i + 1; j < list.size(); j++) {  
  
                if (list.get(i).compareTo(list.get(j))) {
                    // 交换数组中的元素位置
                    Node node = list.get(i);  
  
                    list.set(i, list.get(j));
                    list.set(j, node);
                }
            }  
        }  
  
	}

 梅梅发现我没有把sort（）方法贴过来。。。现在来补上~~~

主函数，注意要定义一个全局的变量private static int[] array = new int[256];

还要注意，非静态的变量不能用于静态的方法，或者主函数中！！会报错

public  static void main(String[] args) {
		List<Node> list = new ArrayList<Node>();
		String st = new String();
		// 实例化一个接受命令行输入信息的对象
		java.util.Scanner sc = new java.util.Scanner(System.in);
		System.out.println("请输入要统计的字符串：");
		// 获取输入的一行字符串
		String temp = sc.nextLine();

		// 循环遍历字符串
		for (int i = 0; i < temp.length(); i++) {
			// 获取指定索引位置的字符
			char c = temp.charAt(i);
			// 将字符转换为对应的ascii
			int ascii = c;
			// 将对应的ascii位置的数组元素加1
			array[ascii]++;
		}

		// 输出
		for (int i = 0; i < array.length; i++) {
			// 如果统计个数部位0则输出
			if (array[i] != 0) {
				char c = (char) i;
				Node nod = new Node(c,array[i]);
				list.add(nod);
				System.out.println("字符" + c + "出现的次数是" + array[i]);
			}
		}
		
        //根据list创建哈夫曼树，并且将createHuffmanTree
		//返回的第一个值作为根节点
		Node root = createHuffmanTree(list);
		generateHuffmanCode(root);
		inOrder(root);
	}

 下面是运行结果~~

 

 

 编码的实现

 

遍历输出

 

 
 种树收官~~~