大话数据结构十六:哈夫曼树(最优二叉树)

1. 引子

当前素质教育的背景下,小学的学科成绩都改为了优秀、良好、及格、不及格这样的模糊词语,而不再通报具体的分数。

用代码可以表示如下:

if( a < 60 )
    System.out.print("不及格");
else if( a < 70 )
    System.out.print("及格");
else if( a < 90 )
    System.out.print("良好");
else
    System.out.print("优秀");

粗略看这样做是没问题的,但是一张好的试卷大部分学生成绩集中在"良好",而上面的程序需要判断两次才能到"良好",输入量很大的时候,在算法效率上其实是有问题的。所以应该做如下改进(① -> ②):

2. 哈夫曼树定义和原理

我们先把上图简化成叶子结点带权的二叉树(注:树结点间的连线相关的数叫做权,Weight)。

① 结点的路径长度:从根结点到该结点的路径上的连接数。

② 树的路径长度:树中每个叶子结点的路径长度之和。

③ 结点带权路径长度:结点的路径长度与结点权值的乘积。

④ 树的带权路径长度:WPL(Weighted Path Length)是树中所有叶子结点的带权路径长度之和。

WPL的值越小,说明构造出来的二叉树性能越优,这种最优二叉树又称为哈夫曼树。

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索证明 哈夫曼树
, 结点
, 路径
, 哈夫曼
, system
, 长度
, c++ 哈夫曼 数据结构
, print
, 哈夫曼树算法设计
哈夫曼算法
,以便于您获取更多的相关知识。

时间: 2016-12-30

大话数据结构十六:哈夫曼树(最优二叉树)的相关文章

编码-哈夫曼树,请问大神们,下面的译码部分怎么没有输出?请大神们帮我修改下~~~(最好再加个能有个文件输出)

问题描述 哈夫曼树,请问大神们,下面的译码部分怎么没有输出?请大神们帮我修改下~~~(最好再加个能有个文件输出) #include #include #include #define maxsize 100 #define max 100 typedef struct { char data; int weight; int parent; int lchild; int rchild; }huffnode; typedef struct { char cd[max]; int start; }

【算法导论】哈夫曼树及编译码

哈夫曼树及编译码 哈夫曼树,又称二叉树,是一类带权路径长度最短的树.所谓路径长度,就是节点到树根之间的路径长度与节点权值的乘积.哈夫曼本人曾在MIT的信息论研究生班学习.Robert Fano教授让学生们自己决定是参加期未考试还是做一个大作业.而哈夫曼选择了后者,原因很简单,因为解决一大作业可能比期未考试更容易通过.Robert Fano教授也是信息论的先驱,学过信息论的都知道有Fano不等式,Shannon-Fano编码.当时这个大作业,Fano也解决不了,哈夫曼并不知道,于是自己尝试,最终产

数据结构例程——哈夫曼树

本文是数据结构基础系列(6):树和二叉树中第15课时哈夫曼树的例程. #include <stdio.h> #include <string.h> #define N 50 //叶子结点数 #define M 2*N-1 //树中结点总数 //哈夫曼树的节点结构类型 typedef struct { char data; //结点值 double weight; //权重 int parent; //双亲结点 int lchild; //左孩子结点 int rchild; //右孩

数据结构哈夫曼树代码怎么写

问题描述 数据结构哈夫曼树代码怎么写 哈夫曼树:输入一串只包含abcdefg8种字符的字符串,统计每种字符出现的次数,并据此创建相应的哈夫曼树. 这怎么写 解决方案 统计字符个数这个简单,你创建一个数组,将每个字符的ascii-'a',得到下标,对应下标+1http://blog.csdn.net/yaoowei2012/article/details/18180769 解决方案二: http://www.cnblogs.com/shiyangxt/archive/2008/12/05/1348

数据结构——赫夫曼树

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

c++ 数据结构-一个程序,哈夫曼树的构造遍历打印,编码解码,缺少遍历和打印

问题描述 一个程序,哈夫曼树的构造遍历打印,编码解码,缺少遍历和打印 #include #include /* 数组头文件 / #include #define MAX 999 / 定义长度 / typedef struct{ / 定义哈夫曼编码的结构数组 / char data; int weight; / 定义权值 / int parent; int lchild; int rchild; }huffmannode; typedef struct{ / 定义保存哈夫曼结构体 / char b

数据结构-哈夫曼树运行错误 但调试却正确 一直找不成错误

问题描述 哈夫曼树运行错误 但调试却正确 一直找不成错误 估计问题是出在HuffmanCoding 但怎么都找不出来 #include "stdio.h" #include "stdlib.h" #include "string.h" char alphabet[]={'A','B','C','D'}; typedef struct { int weight; //权值 int parent; //父节点序号 int left ; int rig

数据结构-构造哈夫曼树的小问题

问题描述 构造哈夫曼树的小问题 完整程序在这里:http://wenku.baidu.com/view/dde580a9376baf1ffc4fadbf template class HfmTree :public BinaryTree { public: operator T()const { return weight; } T getW(){ return weight; } void putW(const T& x){ weight = x; } void SetNull(){ root

数据结构:哈夫曼树的应用

#include<stdio.h>#include<stdlib.h>#include<string.h>#include<conio.h>a#include<graphics.h>#define MAXVALUE 200           /*权值的最大值*/#define MAXBIT  30             /*最大的编码位数*/#define MAXNODE 30             /*初始的最大的结点数*/ struct