数据结构与算法之Huffman tree(赫夫曼树 / 霍夫曼树 / 哈夫曼树 / 最优二叉树)

简介: HuffmanTree因为翻译不同所以有其他的名字:赫夫曼树、霍夫曼树、哈夫曼树

常用数据结构与算法实现

以下博客根据B站罗召勇老师视频:数据结构与算法基础-Java版(罗召勇)写的详细笔记


数据结构与算法基础:


数据结构与算法之基础概述


数据结构:


(一)数据结构与算法之数组

(二)数组结构与算法之栈

(三)数据结构与算法之队列

(四)数据结构与算法之链表

(五)数据结构与算法之树结构基础

(六)数据结构与算法之二叉树大全

(七)数据结构与算法之Huffman tree(赫夫曼树 / 霍夫曼树 / 哈夫曼树 / 最优二叉树)

(八)数据结构与算法之多路查找树(2-3树、2-3-4树、B树、B+树)

(九)数据结构与算法之图结构


十大经典算法:


(一)数据结构与算法之冒泡排序(含改进版)

(二)数据结构与算法之选择排序(含改进版)

(三)数据结构与算法之插入排序(含改进版)

(四)数据结构与算法之希尔排序

(五)数据结构与算法之归并排序

(六)数据结构与算法之快速排序

(七)数据结构与算法之堆排序

(八)数据结构与算法之计数排序

(九)数据结构与算法之桶排序

(十)数据结构与算法之基数排序


赫夫曼树概述

HuffmanTree因为翻译不同所以有其他的名字:赫夫曼树、霍夫曼树、哈夫曼树


赫夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1L1+W2L2+W3L3+…+WnLn),N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明赫夫曼树的WPL是最小的。


定义

路径: 路径是指从一个节点到另一个节点的分支序列。


路径长度: 指从一个节点到另一个结点所经过的分支数目。 如下图:从根节点到a的分支数目为2

image.png


树的路径长度: 树中所有结点的路径长度之和为树的路径长度PL。 如下图:PL为10

image.png


节点的权: 给树的每个结点赋予一个具有某种实际意义的实数,我们称该实数为这个结点的权。如下图:7、5、2、4

image.png

带权路径长度: 从树根到某一结点的路径长度与该节点的权的乘积,叫做该结点的带权路径长度。如下图:A的带权路径长度为2*7=14

image.png


树的带权路径长度(WPL): 树的带权路径长度为树中所有叶子节点的带权路径长度之和


最优二叉树:权值最大的节点离跟节点越近的二叉树,所得WPL值最小,就是最优二叉树。如下图:(b)

image.png


(a)WPL=9*2+4*2+5*2+2*2=40

(b)WPL=9*1+5*2+4*3+2*3=37

(c) WPL=4*1+2*2+5*3+9*3=50

构造赫夫曼树步骤

对于数组{5,29,7,8,14,23,3,11},我们把它构造成赫夫曼树


第一步:使用数组中所有元素创建若干个二叉树,这些值作为节点的权值(只有一个节点)。

image.png

第二步:将这些节点按照权值的大小进行排序。

image.png


第三步:取出权值最小的两个节点,并创建一个新的节点作为这两个节点的父节点,这个父节点的权值为两个子节点的权值之和。将这两个节点分别赋给父节点的左右节点

image.png

第四步:删除这两个节点,将父节点添加进集合里

image.png


第五步:重复第二步到第四步,直到集合中只剩一个元素,结束循环

image.png


代码实现

节点类

//接口实现排序功能
public class Node implements Comparable<Node> {
    int value;
    Node left;
    Node right;
    public Node(int value) {
        this.value = value;
    }
    @Override
    public int compareTo(Node o) {
        return -(this.value - o.value); //集合倒叙,从大到小
    }
    @Override
    public String toString() {
        return "Node value=" + value ;
    }
}

测试类

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Demo {
    public static void main(String[] args) {
        int[] arr = {5, 29, 7, 8, 14, 23, 3, 11};
        Node node = createHuffmanTree(arr);
        System.out.println(node); //Node value=100
    }
    //创建赫夫曼树
    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 left = nodes.get(nodes.size() - 1); //权值最小
            Node right = nodes.get(nodes.size() - 2); //权值次小
            //创建一个新的二叉树
            Node parent = new Node(left.value + right.value);
            //删除原来的两个节点
            nodes.remove(left);
            nodes.remove(right);
            //新的二叉树放入原来的二叉树集合中
            nodes.add(parent);
            //打印结果
            System.out.println(nodes);
        }
        return nodes.get(0);
    }
}

循环次数结果

[Node value=29, Node value=23, Node value=14, Node value=11, Node value=8, Node value=7, Node value=8]
[Node value=29, Node value=23, Node value=14, Node value=11, Node value=8, Node value=15]
[Node value=29, Node value=23, Node value=15, Node value=14, Node value=19]
[Node value=29, Node value=23, Node value=19, Node value=29]
[Node value=29, Node value=29, Node value=42]
[Node value=42, Node value=58]
[Node value=100]
Node value=100
Process finished with exit code 0
目录
打赏
0
0
0
0
64
分享
相关文章
|
2月前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
65 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
2月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
53 12
|
2月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
52 10
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
54 2
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
104 5
|
4月前
|
数据结构之文件系统模拟(树数据结构)
本文介绍了文件系统模拟及其核心概念,包括树状数据结构、节点结构、文件系统类和相关操作。通过构建虚拟环境,模拟文件的创建、删除、移动、搜索等操作,展示了文件系统的基本功能和性能。代码示例演示了这些操作的具体实现,包括文件和目录的创建、移动和删除。文章还讨论了该算法的优势和局限性,如灵活性高但节点移除效率低等问题。
95 0
|
4月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
364 9
|
4月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
63 1
|
2月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
157 77
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等