package com;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Stack;
/**
* 类说明: 哈夫曼树的创建遍历查找当前节点的编码
*/
public class HaffmanTree {
TreeNode root;
/**
* @version 创建时间: 2017-11-21 下午8:57:01
* 类说明:声明一个类,
*/
public static class TreeNode<T> implements Comparable<TreeNode<T>>{
T data;
int weight;
TreeNode leftChild;
TreeNode rightNode;
TreeNode parent;
public TreeNode(T data, int weight) {
super();
this.data = data;
this.weight = weight;
this.leftChild = null;
this.rightNode = null;
this.parent = null;
}
@Override
public int compareTo(TreeNode<T> o) {
//根据weight来排序
if(this.weight>o.weight){
return -1;
}else if(this.weight<o.weight){
return 1;
}
return 0;
}
}
/**
* 创建haffman树
* @param list
* @return
*/
public TreeNode createHaffManTree(ArrayList<TreeNode> list){
while (list.size()>1) {
//取最小的两个值,构建新的节点,进行排序
Collections.sort(list);//从大到小排序
TreeNode leftNode=list.get(list.size()-1);//取最小的值
TreeNode rightNode=list.get(list.size()-2);//取第二小的值
TreeNode parent=new TreeNode("data", leftNode.weight+rightNode.weight);
parent.leftChild=leftNode;
parent.rightNode=rightNode;
leftNode.parent=parent;
rightNode.parent=parent;
list.remove(leftNode);
list.remove(rightNode);
list.add(parent);
}
//最终list里面只剩下一个元素
root=list.get(0);
return list.get(0);
}
/**
* 遍历哈夫曼树
* @param root
* 思路:循环 每次取parent,取出来后,添加leftChild rightChild
*/
public void showHaffman(TreeNode root){
LinkedList<TreeNode> list = new LinkedList<>();
ArrayList<TreeNode> arrayList = new ArrayList<>();
list.offer(root);//队列为空时候,使用add方法会报错,而offer方法会返回false,Queue使用时,才会采用 offer/poll/take等方法作为链表对象时,offer等方法相对来说没有什么意义这些方法是用于支持队列应用的。
while(!list.isEmpty()){
TreeNode node=list.pop();//取出栈顶元素
System.out.print(node.data+" ");
if(node.leftChild!=null){
list.offer(node.leftChild);
}
if(node.leftChild!=null){
list.offer(node.rightNode);
}
}
}
/**
* 获得当前的节点编码 (左子为0 右子为1)
* @param node
*/
public void getCode(TreeNode node){
Stack<String> stack = new Stack<>();
TreeNode treeNode = node;
while(treeNode!=null && treeNode.parent !=null){
//left 0 right 1
if(treeNode.parent.leftChild == treeNode){
stack.push("0");
}else if(treeNode.parent.rightNode == treeNode){
stack.push("1");
}
treeNode=treeNode.parent;
}
while (!stack.isEmpty()) {
System.out.print(stack.pop());
}
}
public static void main(String[] args) {
ArrayList<TreeNode> list = new ArrayList<>();
TreeNode<String> node = new TreeNode("good", 54);
list.add(node);
list.add(new TreeNode("morning", 10));
list.add(new TreeNode("afternoon", 20));
list.add(new TreeNode("hello", 100));
list.add(new TreeNode("hi", 200));
HaffmanTree tree = new HaffmanTree();
tree.createHaffManTree(list);
tree.showHaffman(tree.root);
System.out.println();
tree.getCode(node);
}
}
运行结果如下:
data data hi data hello data good morning afternoon
000