哈夫曼树详解

wuchangjian2021-10-29 14:59:48编程学习

一:定义

        1:给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。                  2:赫夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

基本概念

       1: 路径和路径长度:在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1                                                                                                                                           2:结点的权及带权路径长度:若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积               3:树的带权路径长度:树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL(weighted path length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。 WPL最小的就是哈夫曼树

二:创建哈夫曼树

思路:

1:从小到大进行排序, 将每一个数据,每个数据都是一个节点 , 每个节点可以看成是一颗最简单的二叉树                                                                                                                                             2:取出根节点权值最小的两颗二叉树                                                                                               3:组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和               4:再将这颗新的二叉树,以根节点的权值大小 再次排序, 不断重复  1-2-3-4 的步骤,直到数列中,所有的数据都被处理,就得到一颗赫夫曼树

例如:13, 7, 8, 3, 29, 6, 1  排序 1, 3, 6, 7, 8, 13, 29

 前序遍历:67,29,38,15,7,8,23,10,4,1,3,6,13

package com.atgguigu.huffmanTree;

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

public class HuffmanTree {

    public static void main(String[] args) {
        int[] arr = {13, 7, 8, 3, 29, 6, 1};
        Node node = createHuffmanTree(arr);
        preOrder(node);
    }

    public static Node createHuffmanTree(int[] arr){
        //把数组放入Node集合便于管理
        List<Node> nodes = new ArrayList<>();
        for (int value : arr) {
            nodes.add(new Node(value));
        }

        while (nodes.size() > 1){
            // 1:排序
            Collections.sort(nodes);

            // 2:取出根节点权值最小的(节点)两颗二叉树
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);

            // 3:组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和
            Node parent = new Node(leftNode.value+ rightNode.value);
            parent.left = leftNode;
            parent.right = rightNode;

            nodes.remove(leftNode);
            nodes.remove(rightNode);
            // 4:再将这颗新的二叉树,以根节点的权值大小 再次排序
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    //前序遍历
    public static void preOrder(Node node){
        if(node != null){
            node.preOrder();
        }else {
            System.out.println("你玩我?空树还传过来");
        }
    }
}

//节点类
//Comparable<Node>集合排序
class Node implements Comparable<Node>{
    int value; //节点权值
    Node left;  //左子节点
    Node right;  //右子节点

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

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

    //Comparable<Node>集合排序
    @Override
    public int compareTo(Node o) {
        //表示从小到大排序
        //return -(this.value-o.value); 表示从大到小排序
        return this.value-o.value;
    }

    //前序遍历
    public void preOrder(){
        System.out.print("==>"+this);

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

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

 

相关文章

linux下的extcon驱动小析

      量产的项目遇到一个问题,10%的充电线不充电。将这些不良的充电...

如何让类不能被继承

方法一:借助 final 关键字,用该关键字修饰的类不能被继...

“21天好习惯”第一期-17

如果一个渔夫从 2011 年 1 月 1 日开始每三天打一次渔,两天晒一次...

发表评论    

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。