欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

【数据结构】哈夫曼树

程序员文章站 2022-05-04 08:48:52
【数据结构】哈夫曼树1、基本概念2、什么是哈夫曼树?3、哈夫曼树构建图解4、代码实现哈夫曼树1、基本概念路径:一棵树中,从一个结点到另一个结点所经过的所有结点,被我们称为两个结点之间的路径,如图:从根节点1到叶子节点4的路径:1,2,4路径长度:在一棵树中,从一个结点到另一个结点所经过的“边”的数量,被我们称为两个结点之间的路径长度,还是上图,根节点1到叶子结点4的路径经过了2个边,也就是说,若规定根节点的层数为1,则从根节点到N层的结点的的路径长度为:N-1结点的带权路径长度:树的...

1、基本概念

  • 路径:一棵树中,从一个结点到另一个结点所经过的所有结点,被我们称为两个结点之间的路径,如图:
    【数据结构】哈夫曼树
    从根节点1到叶子节点4的路径:1,2,4

  • 路径长度:在一棵树中,从一个结点到另一个结点所经过的“边”的数量,被我们称为两个结点之间的路径长度,还是上图,根节点1到叶子结点4的路径经过了2个边,也就是说,若规定根节点的层数为1,则从根节点到N层的结点的的路径长度为:N-1

  • 结点的带权路径长度:树的每一个结点,都可以拥有自己的“权重”(Weight),权重在不同的算法当中可以起到不同的作用。结点的带权路径长度,是指树的根结点到该结点的路径长度,和该结点权重的乘积,还是上图,如结点4的权重是10,那结点4的带权路径长度就是10*2 = 20。

  • 树的带权路径长度:在一棵树中,所有叶子结点的带权路径长度之和,被称为树的带权路径长度,也被简称为WPL。

2、什么是哈夫曼树?

  • 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。
  • 哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

【数据结构】哈夫曼树

  • WPL最小的就是哈夫曼树

3、哈夫曼树构建图解

  • 给定一个数列:

【数据结构】哈夫曼树

  • 第一步:把每一个叶子结点,都当做树一颗独立的树(只有根结点的树),同时建个辅助队列,按照权值从小到大存储了所有叶子结点,用于后续哈夫曼树的构建辅助。

【数据结构】哈夫曼树

  • 第二步:选择当前权值最小的两个结点,生成新的父结点,借助辅助队列,我们可以找到权值最小的结点1和4,并根据这两个结点生成一个新的父结点,父节点的权值是这两个结点权值之和。

【数据结构】哈夫曼树

  • 第三步:从队列中移除上一步选择的两个最小结点,把新的父节点加入队列

也就是从队列中删除1和4,插入5,并且仍然保持队列的升序。

【数据结构】哈夫曼树

  • 第四步:继续选择当前权值最小的两个结点,生成新的父结点。

【数据结构】哈夫曼树

  • 第五步:继续移除上一步选择的两个最小结点,把新的父节点加入队列。

【数据结构】哈夫曼树

  • 第六步:继续选择当前权值最小的两个结点,生成新的父结点。

【数据结构】哈夫曼树

  • 第七步:继续移除上一步选择的两个最小结点,把新的父节点加入队列。

【数据结构】哈夫曼树

  • 第八步:继续选择当前权值最小的两个结点,生成新的父结点。

【数据结构】哈夫曼树

  • 第九步:继续移除上一步选择的两个最小结点,把新的父节点加入队列。

【数据结构】哈夫曼树

  • 第十步:继续选择当前权值最小的两个结点,生成新的父结点。

【数据结构】哈夫曼树

  • 此时,队列中仅有一个结点,说明整个森林已经合并成了一颗树,而这棵树就是我们想要的哈夫曼树:

【数据结构】哈夫曼树

4、代码实现哈夫曼树

  • 树节点
package com.data.structure.tree;

/**
 * 树节点
 *
 * @author wangjie
 * @version V1.0
 * @date 2020/7/20
 */
public class Node implements Comparable<Node>{
    /**
     * 节点权值
     */
    int value;
    /**
     * 指向左子结点
     */
    Node left;
    /**
     * 指向右子节点
     */
    Node right;

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

    /**
     * 前序遍历,先输出父结点,再遍历左子树和右子树
     */
    public  void preOrder(){

        System.out.println(this);

        if(null != this.left){
            this.left.preOrder();
        }
        if(null != this.right){
            this.right.preOrder();
        }
    }

    @Override
    public int compareTo(Node o) {
        return this.value - o.value;
    }

    @Override
    public  String toString(){
        return "Node[value="+value+"]";
    }



}

  • 哈夫曼树
package com.data.structure.tree;

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

/**
 * 哈夫曼树
 *
 * @author wangjie
 * @version V1.0
 * @date 2020/7/20
 */
public class HuffmanTree {


    public static void main(String[] args) {
        int arr[] = {2,3,7,9,18,25};
        Node root = createHuffmanTree(arr);
        preOrder(root);
    }
    /**
     * 前序遍历
     * @param root
     */
    public static void preOrder(Node root){
        if (null != root){
            root.preOrder();
        }else {
            System.out.println("该树为空!");
        }
    }

    /**
     * 构建哈夫曼树
     * @param arr
     * @return
     */
    public static Node createHuffmanTree(int[] arr){
        List<Node> nodes = new ArrayList<>();

        for(int value : arr){
            nodes.add(new Node(value));
        }

        while ((nodes.size() > 1)){
            Collections.sort(nodes);

            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);

            Node parent = new Node(leftNode.value+rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;

            nodes.remove(leftNode);
            nodes.remove(rightNode);
            nodes.add(parent);
        }
        return nodes.get(0);
    }
}

本文地址:https://blog.csdn.net/aaa_bbb_ccc_123_456/article/details/107462776

相关标签: 数据结构 java