java哈夫曼树实例代码

java哈夫曼树实例代码

本文实例为大家分享了哈夫曼树java代码，供大家参考，具体内容如下

package boom;

import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

import java.util.Queue;

class Node implements Comparable>{

private T data;

private int weight;

private Node left;

private Node right;

public Node (T data,int weight){

this.data = data;

this.weight = weight;

}

public int compareTo(Node other) {

if(this.weight > other.getWeight()){

return -1;

}if(this.weight < other.getWeight()){

return 1;

}

return 0;

}

public T getData() {

return data;

}

public void setData(T data) {

this.data = data;

}

public int getWeight() {

return weight;

}

public void setWeight(int weight) {

this.weight = weight;

}

public Node getLeft() {

return left;

}

public void setLeft(Node left) {

this.left = left;

}

public Node getRight() {

return right;

}

public void setRight(Node right) {

this.right = right;

}

public String toString(){

return "data:"+this.data+";weight:"+this.weight;

}

}

public class huffuman {

static Node create(List> nodes){

while(nodes.size()>1){

Collections.sort(nodes);

Node left = nodes.get(nodes.size()-1);

Node right = nodes.get(nodes.size()-2);

Node parent = new Node(null,left.getWeight()+right.getWeight());

parent.setRight(right);

parent.setLeft(left);

nodes.remove(left);

nodes.remove(right);

nodes.add(parent);

}

return nodes.get(0);

}

static List> breadth(Node root){

List> list = new ArrayList>();

Queue<Node> queue = new ArrayDeque>();

queue.offer(root);

while(queue.size()>0){

Node out = queue.poll();

list.add(out);

if(out.getLeft()!=null){

queue.offer(out.getLeft());

}

if(out.getRight()!=null){

queue.offer(out.getRight());

}

}

return list;

}

public static void main(String[] args) {

// TODO Auto-generated method stub

List> list = new ArrayList>();

list.add(new Node("a",7));

list.add(new Node("b",5));

list.add(new Node("c",4));

list.add(new Node("d",2));

Node root =huffuman.create(list);

System.out.println(huffuman.breadth(root));

// System.out.println(list);

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。