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);   }       }