Java实现哈夫曼树的构造 - 编程入门网

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.}

Java实现哈夫曼树的构造(2)

哈夫曼树构造类：

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 方法首先获取末尾两个节点，然后构造它们的父结点 ，接着在结点集合中将这两个节点删除，把父结点加进去。

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!