欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java哈夫曼树实例代码

程序员文章站 2024-03-13 11:48:33
本文实例为大家分享了哈夫曼树java代码,供大家参考,具体内容如下 package boom; import java.util.arraydeque;...

本文实例为大家分享了哈夫曼树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<t> implements comparable<node<t>>{
  private t data;
  private int weight;
  private node<t> left;
  private node<t> right;
   
  public node (t data,int weight){
    this.data = data;
    this.weight = weight;
  }
   
  public int compareto(node<t> 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<t> getleft() {
    return left;
  }
 
  public void setleft(node<t> left) {
    this.left = left;
  }
 
  public node<t> getright() {
    return right;
  }
 
  public void setright(node<t> right) {
    this.right = right;
  }  
   
  public string tostring(){ 
    return "data:"+this.data+";weight:"+this.weight; 
  } 
}
 
public class huffuman<t> {
  static <t> node<t> create(list<node<t>> nodes){
    while(nodes.size()>1){
      collections.sort(nodes); 
      node<t> left = nodes.get(nodes.size()-1);
      node<t> right = nodes.get(nodes.size()-2);
      node<t> parent = new node<t>(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<t> list<node<t>> breadth(node<t> root){
    list<node<t>> list = new arraylist<node<t>>();
    queue<node<t>> queue = new arraydeque<node<t>>();
    queue.offer(root);
    while(queue.size()>0){
      node<t> 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<node<string>> list = new arraylist<node<string>>(); 
    list.add(new node<string>("a",7)); 
    list.add(new node<string>("b",5)); 
    list.add(new node<string>("c",4)); 
    list.add(new node<string>("d",2)); 
      
    node<string> root =huffuman.create(list); 
    system.out.println(huffuman.breadth(root)); 
//   system.out.println(list); 
  }
    
   
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。