赫夫曼树的实现---Java

       对于传进来的数组首先将其存入到ArrayList中，便于后续的删除操作，对ArrayList进行排序，将最小的两个节点Node取出来，其值相加得到父节点的值，让父节点的左右孩子分别指向前两个元素，将当前ArrayList中的前两个元素删除，将父节点添加到ArrayList中，并且重复该操作，知道ArrayList的长度为1结束，当前ArrayList中的元素就是赫夫曼树的根节点，将其返回。

public static Node HaffmanTree(int[] array) {
        List arrayList = new ArrayList();
        for (int e : array) {
            arrayList.add(new Node(e));
        }
        while (arrayList.size() > 1) {
            Collections.sort(arrayList);
            //将当前arrayList最小的两个元素添加到node中。
            Node node1 = new Node(arrayList.get(0).getValue() + arrayList.get(1).getValue());
            node1.setLeftNode(arrayList.get(0));
            node1.setRightNode(arrayList.get(1));
            //依次将最小的两个元素移除
            arrayList.remove(0);
            arrayList.remove(0);
            arrayList.add(node1);
        }
        return arrayList.get(0);


    }

package DataStructures.BinaryTree;

import com.mysql.jdbc.log.NullLogger;

import java.security.Principal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;


public class HaffmanTreeTes {
    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node node = HaffmanTree(arr);
        node.preShow();
    }

    public static Node HaffmanTree(int[] array) {
        List arrayList = new ArrayList();
        for (int e : array) {
            arrayList.add(new Node(e));
        }
        while (arrayList.size() > 1) {
            Collections.sort(arrayList);
            //将当前arrayList最小的两个元素添加到node中。
            Node node1 = new Node(arrayList.get(0).getValue() + arrayList.get(1).getValue());
            node1.setLeftNode(arrayList.get(0));
            node1.setRightNode(arrayList.get(1));
            //依次将最小的两个元素移除
            arrayList.remove(0);
            arrayList.remove(0);
            arrayList.add(node1);
        }
        return arrayList.get(0);


    }

}

class Node implements Comparable {
    private int value;
    private Node leftNode;
    private Node rightNode;

    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }

    public void preShow() {
        System.out.print(this.value + " ");
        if (this.leftNode != null) {
            this.leftNode.preShow();
        }
        if (this.rightNode != null) {
            this.rightNode.preShow();
        }
    }

    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }

    public int getValue() {
        return value;
    }

    public Node getLeftNode() {
        return leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public Node(int value) {
        this.value = value;
    }

    public Node() {
    }


    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Node node = (Node) o;

        return value == node.value;
    }

    @Override
    public int hashCode() {
        return value;
    }

    @Override
    public int compareTo(Node o) {
        //从小到大排序
        return this.value - o.value;
    }
}