构造哈夫曼树(数据结构实训)(难度系数85)

这篇具有很好参考价值的文章主要介绍了构造哈夫曼树(数据结构实训)(难度系数85)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

构造哈夫曼树
题目描述:
根据给定的叶结点字符及其对应的权值创建哈夫曼树。
输入:
第一行为叶子结点的数目n(1<=n<=100)。第二行为一个字符串,包含n个字符,每个字符对应一个叶子结点,第三行为每个叶子结点的概率(即权值),要求根据各叶结点构造哈夫曼树。构造哈夫曼树的原则是先两个最小的,构造一个父结点,其中最小的结点为左孩子,次小的为右孩子,如果两个最小的叶结点相等,则取排在前一个位置的为左孩子。
输出:
哈夫曼树的权值,左孩子,右孩子及其对应的父亲,相邻数据之间用空格隔开;

输入样例:
5
abcde
15 25 15 20 25

输出样例:
15 0 0 6
25 0 0 7
15 0 0 6
20 0 0 7
25 0 0 8
30 1 3 8
45 4 2 9
55 5 6 9
100 7 8 0 

构造哈夫曼树方法,即题目所示,分别找到最小的两个叶子结点,组成一个新的叶子结点,最后长度不超过2*n-1

import java.util.*;

public class Xingyuxingxi {
    public static class jgt {
        int qz, lc, rc, fq, dq;//权值,左孩子,右孩子,父结点,存储当前使用过的权值

        public jgt() {
            this.qz = 0;
            this.lc = 0;
            this.rc = 0;
            this.fq = 0;
            this.dq = 0;
        }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        String str=sc.next();
        int m=2*n-1;
        jgt [] tree=new jgt[m];
        for (int i = 0; i < n; i++) {
            tree[i]=new jgt();//每次都需要初始化
            tree[i].qz=tree[i].dq=sc.nextInt();//dq中储存的是没有使用过的权值,因为一个结点只能使用一次
        }
        while(n!=m) {//最多只有m的长度
            int min1 = 0,min2 = 0;//最小结点,和第二小结点
            for (int j = 0; j < n; j++) {
                if (tree[min1].dq > tree[j].dq)//如果比当前下标的大,则将当前下标保存下来
                {
                    min1 = j;
                }
            }
            tree[min1].dq=Integer.MAX_VALUE;//如果被使用则赋值一个无限大的数表示已经使用
            for (int j = 0; j < n; j++)
            {
                if(tree[min2].dq>tree[j].dq&&min1!=j)//j不能等于min1因为已经存储了这个最小结点,只能使用一次
                {
                    min2=j;
                }
            }
            tree[n]=new jgt();//初始化,不初始化会空指针异常
            tree[n].qz=tree[n].dq=tree[min1].qz+tree[min2].qz;//当前结点权值为最小的两个结点权值之和
            tree[n].lc=min1+1;//左孩子是最小叶子结点的下标,加1是因为从下标为0开始储存的,题目要求输出的下标是从1开始储存的
            tree[n].rc=min2+1;//右孩子是第二小叶子结点的下标
            tree[min1].fq=tree[min2].fq=n+1;//左孩子和右孩子的父结点都是n+1
            tree[min2].dq=Integer.MAX_VALUE;//如果被使用则赋值一个无限大的数表示已经使用
            n++;//每次会产生一个新的结点
        }
        for (int i = 0; i < m; i++) {
            System.out.println(tree[i].qz+" "+tree[i].lc+" "+tree[i].rc+" "+tree[i].fq);
        }
    }
}

注意:下标从同一个下标开始找时,找到第一个最小值要马上赋值一个很大的数,不然的话,最小叶子结点和第二小叶子结点都会是同一个下标,但是每个值只能用一次文章来源地址https://www.toymoban.com/news/detail-770055.html

到了这里,关于构造哈夫曼树(数据结构实训)(难度系数85)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构课程实验五:哈夫曼树与哈夫曼编码

    实验日期:2022-12-20   目录 一、实验目的 1、掌握哈夫曼树的建立 2、掌握哈夫曼编码方式 二、实验内容

    2024年02月05日
    浏览(50)
  • 【数据结构与算法】-哈夫曼树(Huffman Tree)与哈夫曼编码

    超详细讲解哈夫曼树(Huffman Tree)以及哈夫曼编码的构造原理、方法,并用代码实现。 路径 :从树中一个结点到另一个结点之间的 分支 构成这两个结点间的路径。 结点的路径长度 :两结点间路径上的 分支数 。 树的路径长度: 从树根到每一个结点的路径长度之和。记作: TL  权

    2024年02月06日
    浏览(53)
  • 数据结构【哈夫曼树】

    最优二叉树也称哈夫曼 (Huffman) 树 ,是指对于一组带有确定权值的叶子结点,构造的具有最小带权路径长度的二叉树。权值是指一个与特定结点相关的数值。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 涉及到的几个概念: 路径: 从树中一个结点到另一个结

    2024年02月14日
    浏览(41)
  • 数据结构-哈夫曼树

    介绍 哈夫曼树,指 带权路径长度最短的二叉树 ,通常用于数据压缩中 什么是带权路径长度? 假设有一个结点,我们为它赋值,这个值我们称为权值,那么从根结点到它所在位置,所经历的路径,与这个权值的积,就是它的带权路径长度。 比如有这样一棵树,D权值为2  从

    2024年02月20日
    浏览(44)
  • 数据结构----哈夫曼树

    哈夫曼树就是寻找构造最优二叉树,用于提高效率 各种路径长度 各种带权路径长度 结点的带权路径长度 树的带权路径长度 哈夫曼树 带权路径长度最短的树或者二叉树 也就是树的叶子结点带权路径长度之和 :也就是叶子结点的结点路径长度(根结点到叶子结点的路径数)

    2024年01月21日
    浏览(49)
  • 【数据结构实验】哈夫曼树

    为一个信息收发站编写一个哈夫曼码的编/译码系统。文末贴出了源代码。 完整的系统需要具备完整的功能,包含初始化、编码、译码、印代码文件和印哈夫曼树,因此需要进行相应的文件操作进行配合。 哈夫曼树的字符集和频度可以从文件中读入,也可以让用户手动输入,

    2023年04月22日
    浏览(45)
  • 【数据结构-树】哈夫曼树

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月08日
    浏览(47)
  • 【数据结构】实验十:哈夫曼编码

    实验十 哈夫曼编码 一、实验目的与要求 1 )掌握树、森林与二叉树的转换; 2 )掌握哈夫曼树和哈夫曼编码算法的实现; 二、 实验内容 1.  请编程实现如图所示的树转化为二叉树。 2.  编程实现一个哈夫曼编码系统,系统功能包括: (1)  字符信息统计:读取待编码的源文

    2024年02月15日
    浏览(48)
  • 数据结构—哈夫曼树及其应用

    5.6哈夫曼树及其应用 5.6.1哈夫曼树的基本概念 路径 :从树中一个结点到另一个结点之间的 分支 构成这两个结点间的路径。 结点的路径长度 :两结点间路径上的 分支数 。 树的路径长度 :从 树根 到每一个结点的 路径长度之和 。记作 TL 结点数目相同的二叉树中,完全二叉

    2024年02月14日
    浏览(38)
  • 数据结构—基础知识:哈夫曼树

    哈夫曼(Huffman)树 又称最优树,是一类带权路径长度最短的树,在实际中有广泛的用途。哈夫曼树的定义,涉及路径、路径长度、权等概念,下面先给出这些概念的定义,然后再介绍哈夫曼树 路径 :从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。 路

    2024年02月21日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包