Java--哈夫曼树创建和遍历

哈夫曼树的创建和遍历

import java.util.*;
public class huffman  
{
    public static void main(String[] args) 
    {
        int []arr={13,7,8,3,29,6,1};
        Node root=huff(arr);
        //前序遍历打印赫夫曼树
        if(root!=null){
            System.out.println("赫夫曼树前序遍历为:");
        root.preOrder();}
        else{
            System.out.println("赫夫曼树为空");
        }

    }
    //创建赫夫曼树
    public static Node huff(int []arr){
        //创建Node类型的集合，便于存取节点
        List<Node>nodes=new ArrayList<Node>();
        for(int a:arr){
            nodes.add(new Node(a));//注意：此处是把Node类型节点放入，所以构造新的对象
        }
        while(nodes.size()>1){
        //排序，小到大
        Collections.sort(nodes);//对集合内部元素排序
        //System.out.println(nodes);
        //(1)取两个节点最小的构建子树
        Node left=nodes.get(0);
        Node right=nodes.get(1);
        //(2)构造父节点
        Node parent=new Node(left.value+right.value);
        parent.left=left;
        parent.right=right;
        //(3)从集合中删除已经取出的节点
        nodes.remove(left);
        nodes.remove(right);
        //(4)将父节点加入到集合中
        nodes.add(parent);//默认在集合最后
        }
        return nodes.get(0);
    }
}

class Node implements Comparable<Node>
{
    int value;
    Node left;
    Node right;
    public Node(int value){
        this.value=value;
    }
    public String toString(){
        return "value="+value;
    }
    public int compareTo(Node o){
        return this.value-o.value;//实现从小到大排序
    }
    //前序遍历赫夫曼树
    public void preOrder(){
        System.out.println(this);
        if(this.left!=null){
            this.left.preOrder();
        }
        if(this.right!=null){
            this.right.preOrder();
        }
    }
}

原文：https://www.cnblogs.com/DongChenYi/p/12013527.html