Java實現哈夫曼樹的構造

哈夫曼樹的內容這裡不作解釋，請自己搜索。下面給出哈夫曼樹構造過程的 Java 實現。

結點類：

1./**
2. * 二叉樹節點
3. */
4.public class Node implements Comparable {
5.
6.    private int value;
7.
8.    private Node leftChild;
9.
10.    private Node rightChild;
11.
12.    public Node(int value) {
13.        this.value = value;
14.    }
15.
16.    public int getValue() {
17.        return value;
18.    }
19.
20.    public void setValue(int value) {
21.        this.value = value;
22.    }
23.
24.    public Node getLeftChild() {
25.        return leftChild;
26.    }
27.
28.    public void setLeftChild(Node leftChild) {
29.        this.leftChild = leftChild;
30.    }
31.
32.    public Node getRightChild() {
33.        return rightChild;
34.    }
35.
36.    public void setRightChild(Node rightChild) {
37.        this.rightChild = rightChild;
38.    }
39.
40.    public String toString(int level) {
41.        String indent = "";
42.        for (int i = 0; i < level; i++) {
43.            indent += "  ";
44.        }
45.
46.        return indent + value + "\n" +
47.                (leftChild != null ? leftChild.toString(level + 1) 

: "") +
48.                (rightChild != null ? rightChild.toString(level + 

1) : "");
49.    }
50.
51.    public int compareTo(Object o) {
52.        Node that = (Node) o;
53.        double result = this.value - that.value;
54.        return result > 0 ? 1 : result == 0 ? 0 : -1;
55.    }
56.}

哈夫曼樹構造類：

1.public class HuffmanTreeBuilder {
2. 
3.    public static void main(String[] args) {
4.        List<Node> nodes = Arrays.asList(
5.                new Node(40),
6.                new Node(8),
7.                new Node(10),
8.                new Node(30),
9.                new Node(10),
10.                new Node(2)
11.        );
12. 
13.        Node node = HuffmanTreeBuilder.build(nodes);
14.        System.out.println(node.toString(0));
15.    }
16. 
17.    /**
18.     * 構造哈夫曼樹
19.     *
20.     * @param nodes 結點集合
21.     *
22.     * @return 構造出來的樹的根結點
23.     */24.    private static Node build(List<Node> nodes) {
25.        nodes = new ArrayList<Node>(nodes);
26.        sortList(nodes);
27.        while (nodes.size() > 1) {
28.            createAndReplace(nodes);
29.        }
30.        return nodes.get(0);
31.    }
32. 
33.    /**
34.     * 組合兩個權值最小結點，並在結點列表中用它們的父結點替換它們
35.     *
36.     * @param nodes 結點集合
37.     */
38.    private static void createAndReplace(List<Node> nodes) {
39.        Node left = nodes.get(nodes.size() - 1);
40.        Node right = nodes.get(nodes.size() - 2);
41.        Node parent = new Node(left.getValue() + right.getValue());
42.        parent.setLeftChild(left);
43.        parent.setRightChild(right);
44.        nodes.remove(nodes.size() - 1);
45.        nodes.remove(nodes.size() - 1);
46.        nodes.add(parent);
47.        sortList(nodes);
48.    }
49. 
50.    /**
51.     * 將結點集合由大到小排序
52.     *
53.     * @param nodes 結點集合
54.     */
55.    private static void sortList(List<Node> nodes) {
56.        Collections.sort(nodes);
57.    }
58.}

說明：

1、HuffmanTreeBuilder 的 25 行新建了一個結點集合，以免對參數進行修 改。

2、createAndReplace 方法首先獲取末尾兩個節點，然後構造它們的父結點 ，接著在結點集合中將這兩個節點刪除，把父結點加進去。