首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构09 哈夫曼树

数据结构09 哈夫曼树

作者头像
nnngu
发布2018-03-15 15:57:46
7290
发布2018-03-15 15:57:46
举报
文章被收录于专栏:nnngunnngu

这一篇要总结的是树中的哈夫曼树(Huffman Tree),我想从以下几点对其进行总结:

1、什么是哈夫曼树

2、如何构建哈夫曼树

3、哈夫曼编码

4、代码实现

1、什么是哈夫曼树

什么是哈夫曼树呢?

哈夫曼树是一种带权路径长度最短的二叉树,也称为最优二叉树。下面用一幅图来说明。

它们的带权路径长度分别为:

图a: WPL=5*2+7*2+2*2+13*2=54

图b: WPL=5*3+2*3+7*2+13*1=48

可见,图b的带权路径长度较小,我们可以证明图b就是哈夫曼树(也称为最优二叉树)。

2、如何构建哈夫曼树

一般可以按下面步骤构建:

(1)将所有左,右子树都为空的节点作为根节点。

(2)在森林中选出两棵根节点的权值最小的树作为一棵新树的左,右子树,且置新树的根节点的权值为其左,右子树上根节点的权值之和。注意,左子树的权值应小于右子树的权值。

(3)从森林中删除这两棵树,同时把新树加入到森林中。

(4)重复2、3步骤,直到森林中只有一棵树为止,此树便是哈夫曼树。

下面是构建哈夫曼树的图解过程:

3、哈夫曼编码

利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子节点都有一条路径,对路径上的各分支约定指向左子树的分支表示”0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为各个叶子节点对应的字符编码,即是哈夫曼编码。

就拿上图例子来说:

A,B,C,D对应的哈夫曼编码分别为:111,10,110,0

用图说明如下:

4、代码实现

代码:

节点类 Node.java

/**
 * 节点类
 */
public class Node implements Comparable {
    private int value;
    private Node leftChild;
    private Node rightChild;

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

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(Node leftChild) {
        this.leftChild = leftChild;
    }

    public Node getRightChild() {
        return rightChild;
    }

    public void setRightChild(Node rightChild) {
        this.rightChild = rightChild;
    }

    public int compareTo(Object o) {
        Node that = (Node) o;
        double result = that.value - that.value;
        return result > 0 ? 1 : result == 0 ? 0 : -1;
    }
}

HuffmanTreeBuilder.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 哈夫曼树构造类
 */
public class HuffmanTreeBuilder {
    public static void main(String[] args) {
        List<Node> nodes = Arrays.asList(
                new Node(1),
                new Node(3),
                new Node(5),
                new Node(7)
        );
        Node node = HuffmanTreeBuilder.build(nodes);
        printTree(node);
    }

    /**
     * 构造哈夫曼树
     *
     * @param nodes 节点集合
     * @return 构造出来的树的根节点
     */
    private static Node build(List<Node> nodes) {
        nodes = new ArrayList<Node>(nodes);
        sortList(nodes);
        while (nodes.size() > 1) {
            createAndReplace(nodes);
        }
        return nodes.get(0);
    }

    /**
     * 组合两个权值最小节点,并在节点列表中用它们的父节点替换它们
     *
     * @param nodes 节点集合
     */
    private static void createAndReplace(List<Node> nodes) {
        Node left = nodes.get(0);
        Node right = nodes.get(1);
        Node parent = new Node(left.getValue() + right.getValue());
        parent.setLeftChild(left);
        parent.setRightChild(right);
        nodes.remove(0);
        nodes.remove(0);
        nodes.add(parent);
        sortList(nodes);
    }

    /**
     * 将节点集合由小到大排序
     *
     * @param nodes
     */
    private static void sortList(List<Node> nodes) {
        Collections.sort(nodes);
    }

    /**
     * 打印树结构,显示的格式是node(left,right)
     *
     * @param node
     */
    public static void printTree(Node node) {
        Node left = null;
        Node right = null;
        if (node != null) {
            System.out.print(node.getValue());
            left = node.getLeftChild();
            right = node.getRightChild();
            System.out.println("(" + (left != null ? left.getValue() : " ") + "," + (right != null ? right.getValue() : " ") + ")");
        }
        if (left != null) {
            printTree(left);
        }
        if (right != null) {
            printTree(right);
        }
    }
}

运行结果:

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1、什么是哈夫曼树
  • 2、如何构建哈夫曼树
  • 3、哈夫曼编码
  • 4、代码实现
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档