package huffman;
/**
 * 節(jié)點(diǎn)類
 * @author yuxiu
 *
 */
public class Node {
 public String code;// 節(jié)點(diǎn)的哈夫曼編碼
 public int codeSize;// 節(jié)點(diǎn)哈夫曼編碼的長(zhǎng)度
 public String data;// 節(jié)點(diǎn)的數(shù)據(jù)
 public int count;// 節(jié)點(diǎn)的權(quán)值
 public Node lChild;
 public Node rChild;

 public Node() {
 }

 public Node(String data, int count) {
  this.data = data;
  this.count = count;
 }

 public Node(int count, Node lChild, Node rChild) {
  this.count = count;
  this.lChild = lChild;
  this.rChild = rChild;
 }

 public Node(String data, int count, Node lChild, Node rChild) {
  this.data = data;
  this.count = count;
  this.lChild = lChild;
  this.rChild = rChild;
 }
}

package huffman;

import java.io.*;
import java.util.*;

public class Huffman {
 private String str;// 最初用于壓縮的字符串
 private String newStr = "";// 哈夫曼編碼連接成的字符串 
 private Node root;// 哈夫曼二叉樹(shù)的根節(jié)點(diǎn)
 private boolean flag;// 最新的字符是否已經(jīng)存在的標(biāo)簽
 private ArrayList<String> charList;// 存儲(chǔ)不同字符的隊(duì)列 相同字符存在同一位置
 private ArrayList<Node> NodeList;// 存儲(chǔ)節(jié)點(diǎn)的隊(duì)列
 
  15  16  /**
  * 構(gòu)建哈夫曼樹(shù)
  * 
  * @param str
  */
 public void creatHfmTree(String str) {
  this.str = str;
  charList = new ArrayList<String>();
  NodeList = new ArrayList<Node>();
  // 1.統(tǒng)計(jì)字符串中字符以及字符的出現(xiàn)次數(shù)
  // 基本思想是將一段無(wú)序的字符串如ababccdebed放到charList里，分別為aa,bbb,cc,dd,ee
  // 并且列表中字符串的長(zhǎng)度就是對(duì)應(yīng)的權(quán)值
  for (int i = 0; i < str.length(); i++) {
   char ch = str.charAt(i); // 從給定的字符串中取出字符
   flag = true;
   for (int j = 0; j < charList.size(); j++) {
    if (charList.get(j).charAt(0) == ch) {// 如果找到了同一字符
     String s = charList.get(j) + ch;
     charList.set(j, s);
     flag = false;
     break;
    }
   }
   if (flag) {
    charList.add(charList.size(), ch + "");
   }
  }
  // 2.根據(jù)第一步的結(jié)構(gòu)，創(chuàng)建節(jié)點(diǎn)
  for (int i = 0; i < charList.size(); i++) {
   String data = charList.get(i).charAt(0) + ""; // 獲取charList中每段字符串的首個(gè)字符
   int count = charList.get(i).length(); // 列表中字符串的長(zhǎng)度就是對(duì)應(yīng)的權(quán)值
   Node node = new Node(data, count); // 創(chuàng)建節(jié)點(diǎn)對(duì)象
   NodeList.add(i, node); // 加入到節(jié)點(diǎn)隊(duì)列
  }

  // 3.對(duì)節(jié)點(diǎn)權(quán)值升序排序
  Sort(NodeList);
  while (NodeList.size() > 1) {// 當(dāng)節(jié)點(diǎn)數(shù)目大于一時(shí)
   // 4.取出權(quán)值最小的兩個(gè)節(jié)點(diǎn)，生成一個(gè)新的父節(jié)點(diǎn)
   // 5.刪除權(quán)值最小的兩個(gè)節(jié)點(diǎn)，將父節(jié)點(diǎn)存放到列表中
   Node left = NodeList.remove(0);
   Node right = NodeList.remove(0);
   int parentWeight = left.count + right.count;// 父節(jié)點(diǎn)權(quán)值等于子節(jié)點(diǎn)權(quán)值之和
   Node parent = new Node(parentWeight, left, right);
   NodeList.add(0, parent); // 將父節(jié)點(diǎn)置于首位

  }
  // 6.重復(fù)第四五步，就是那個(gè)while循環(huán)
  // 7.將最后的一個(gè)節(jié)點(diǎn)賦給根節(jié)點(diǎn)
  root = NodeList.get(0);
 }
 /**
  * 升序排序
  * 
  * @param nodelist
  */
 public void Sort(ArrayList<Node> nodelist) {
  for (int i = 0; i < nodelist.size() - 1; i++) {
   for (int j = i + 1; j < nodelist.size(); j++) {
    Node temp;
    if (nodelist.get(i).count > nodelist.get(j).count) {
     temp = nodelist.get(i);
     nodelist.set(i, nodelist.get(j));
     nodelist.set(j, temp);
    }

   }
  }

 }

 /**
  * 遍歷
  * 
  * @param node
  *   節(jié)點(diǎn)
  */
 public void output(Node node) {
  if (node.lChild != null) {
   output(node.lChild);
  }
  System.out.print(node.count + " "); // 中序遍歷
  if (node.rChild != null) {
   output(node.rChild);
  }
 }

 public void output() {
  output(root);
 }
/**
  * 主方法
  * 
  * @param args
  */
 public static void main(String[] args) {
  Huffman huff = new Huffman();//創(chuàng)建哈弗曼對(duì)象
  huff.creatHfmTree("sdfassvvdfgsfdfsdfs");//構(gòu)造樹(shù)
 }