c语言-关于科夫曼树的一个小问题

问题描述

关于科夫曼树的一个小问题

在看到最优二叉树的时候有关于树的路径有这个个定义:树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中,完全二叉树的路径长度最短。

这里我一直不理解,如下图,一个是完全二叉树,一个是普通的二叉树。可是他们的路径长度不是完全一样吗?

另外,还有一个问题,就是在生成科夫曼树的时候,假如在取2个最小权值的时候,发现此时有3数在范围内,即一个刚刚生成的权值和一个处在森林里的只有根结点的权值相等,同为次小的数。此时应如何取舍,为什么?

解决方案

最短的含义就是没有比它更短,不一定说一定它是唯一最短的。除非是满二叉树。
只要是带权路径最短,都可以。哈夫曼树也未必有唯一解。

解决方案二:

1、完全二叉树:除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点。
这是完全二叉树的定义,满足该定义的才是完全二叉树。路径长度最短只是完全二叉树的一个性质,不能作为判断依据(必要非充分条件)。
2、其一,你想说的是“哈夫曼树”吧?
其二,正如楼上所说,楼主应该目前还没学到组成原理等专业课吧?如果学过前缀编码就会理解了,哈夫曼树只是为了生成一棵带权路径长度最小的树,并不唯一,比如用于前缀编码,只要能最大程度地节约存储空间就可以了,无所谓生成的哈夫曼树具体是什么样的。

时间: 2024-05-21 20:25:27

c语言-关于科夫曼树的一个小问题的相关文章

c语言-C语言文件/哈夫曼树/算法/二叉树

问题描述 C语言文件/哈夫曼树/算法/二叉树 在一个函数中,下面这两行运行无错误 fp=fopen("CodeFile.dat","wb"); fwrite(HC[i],sizeof(char),strlen(HC[i])+1,fp); //其中HC的类型是char ** //然后在另外一个函数中加入 fp=fopen("CodeFile.dat","rb"); for(int i=1;i<=n;i++) fread(H

C++实现哈夫曼树简单创建与遍历的方法_C 语言

本文以实例形式讲述了C++实现哈夫曼树简单创建与遍历的方法,比较经典的C++算法. 本例实现的功能为:给定n个带权的节点,如何构造一棵n个带有给定权值的叶节点的二叉树,使其带全路径长度WPL最小. 据此构造出最优树算法如下: 哈夫曼算法: 1. 将n个权值分别为w1,w2,w3,....wn-1,wn的节点按权值递增排序,将每个权值作为一棵二叉树.构成n棵二叉树森林F={T1,T2,T3,T4,...Tn},其中每个二叉树都只有一个权值,其左右字数为空 2. 在森林F中选取根节点权值最小二叉树,

数据结构——赫夫曼树

1 基本概念 赫夫曼树(Huffman Tree)又称为最优树,是一类带权路径长度最短的树.本文仅讨论最优二叉树. 树的路径长度是指从树根到树中其余各个结点的路径长度之和.对具有n个结点的二叉树而言,完全二叉树具有最短的树的路径长度. 若在二叉树中,树叶结点带有权值,则有:结点的带权路径长度定义为从树根到该结点之间的路径长度与该结点上所带权值之积. 若树中有n个树叶结点,且每个树叶结点均带有权值,则有:树的带权路径长度定义为树中所有树叶结点的带权路径长度之和,可记为: 有时,也将树的路径长度称为

解析C++哈夫曼树编码和译码的实现_C 语言

一.背景介绍: 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 二.实现步骤: 1.构造一棵哈夫曼树 2.根据创建好的哈夫曼树创建一张哈夫曼编码表 3.输入一串哈夫曼序列,输出原始字符 三.设计思想: 1.首先要构造一棵哈夫曼树,哈夫曼树的结点结构包括权值,双亲,左右孩子:假如由n个字符来构造一棵哈夫曼树,则共有结点2n-1个:在构造前,先初始化

哈夫曼树(一) C语言详解

哈夫曼树的介绍 Huffman Tree,中文名是哈夫曼树或霍夫曼树,它是最优二叉树. 定义:给定n个权值作为n个叶子结点,构造一棵二叉树,若树的带权路径长度达到最小,则这棵树被称为哈夫曼树.这个定义里面涉及到了几个陌生的概念,下面就是一颗哈夫曼树,我们来看图解答. (01) 路径和路径长度 定义:在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径.通路中分支的数目称为路径长度.若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1. 例子:100和80的路径长度是

编码-霍夫曼树程序,输入字符串统计字符出现次数并译码。请问如何改成从文件读入字符串?

问题描述 霍夫曼树程序,输入字符串统计字符出现次数并译码.请问如何改成从文件读入字符串? //生成HuffmanCode文件的两个函数void HuffmanEncoding(HuffmanTree HTHuffmanCode HC){//根据HuffmanTreeHT求HuffmanCode表HC int cpi; char cd[n]; int start; cd[num] = ''; for(i = 1;i <= num;i++){ start = num; c = i; while((p

九度题目1172:哈夫曼树

题目1172:哈夫曼树 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:4366 解决:1827 题目描述: 哈夫曼树,第一行输入一个数n,表示叶结点的个数.需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题 目需要输出所有结点的值与权值的乘积之和. 输入: 输入有多组数据. 每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不超过100,2<=n<=1000). 输出: 输出权值. 样例输入: 5  1 2 2 5 9 样例输出: 37 来源:

HDU2527 构建哈夫曼树的灵巧运用

上课老师说了知道哈夫曼树叶子 不构图求二叉树的权 就是在构造哈夫曼树的时候运用构图的方法 把 每个结点的值加起来就是该数的权 证明 W=∑叶子权*该叶子层数 除了叶子的结点和就是这个树的权  构造一个树就知道了 结点的权 肯定是下一层结点的和 就好像  W=∑叶子权*该叶子层数 这个公式运用了 乘法分配律一样=  =  #include <iostream> #include<cstdio> #include<cstring> #include<algorithm

哈夫曼树以及哈夫曼编码

哈夫曼树简介 哈夫曼树(哈夫曼树),又称最优二叉树,是一类带权路径长度最短的树.假设有n个权值{w1,w2,...,wn},如果构造一棵有n个叶子节点的二叉树,而这n个叶子节点的权值是{w1,w2,...,wn},则所构造出的带权路径长度最小的二叉树就被称为哈夫曼树. 这里补充下树的带权路径长度的概念.树的带权路径长度指树中所有叶子节点到根节点的路径长度与该叶子节点权值的乘积之和,如果在一棵二叉树中共有n个叶子节点,用Wi表示第i个叶子节点的权值,Li表示第i个也叶子节点到根节点的路径长度,则该