最优二叉树的生成及应用

出租汽车驾驶员从业资格管理规定最优二叉树的生成及应用

作者：***

来源：《现代电子技术》2008年第10期

摘要：衡量一个算法的优劣有许多因素，效率就是其中之一。而效率指的就是算法的执行时间。提高效率是软件开发必须注重的问题。对同一个问题往往有多个算法可以解决，在同等条件下,执行时间短的算法其效率是最高的。从霍夫曼树的定义以及霍夫曼算法出发，介绍如何构造霍夫曼树以及利用霍夫曼算法优化程序设计的原理，重点讨论在判定类问题中利用霍夫曼树可以建立最佳判定算法，提高程序的执行速度。

喜剧世界关键词：霍夫曼树；霍夫曼算法；最佳判定算法；执行时间

中图分类号：TP183 文献标识码：B 现代教育管理

约翰萨顿文章编号：1004-373X(2008)10-112-02

Generation and Application of Optimal Binary Tree

ZHANG Guangxue

裸持资源 (Shaanxi Spinning and Weaving Clothing Occupation Technology,Xianyang,712000,China)

Abstract：Efficiency is one of factors to judge an algorithm,it refers to execution time of algorithm to improve the efficiency is important problem in software development.In the same condition,it has high efficient in a short execution time.According to Huffman algorithm and Huffman tree,how to build Huffman tree and using Huffman algorithm to optimize the program design are introduced,Huffman tree is applied to build best decision algorithm is discussed too.

Keywords：Huffman tree;Huffman algorithm;best decision algorithm;execution time

1 引言

衡量一个算法的优劣有许多因素，效率就是其中之一。而效率指的就是算法的执行时间。提高效率是软件开发必须注重的问题。对同一个问题往往有多个算法可以解决，在同

等条件下,执行时间短的算法其效率是最高的。最优二叉树最早是由霍夫曼于1952年提出的,所以被称为霍夫曼树,相应的算法称为霍夫曼算法。

霍夫曼树又称最优二叉树，是指带权路径长度最小的二叉树。在软件开发中，都要解决大量的判定类问题，解决这类问题的习惯做法常是自上而下(或自下而上)或由高到低(或由低到高)的逐个判断。而大量的判定问题中普遍存在着满足中间条件的多，满足两头条件的少的现象(近似于正态分布)。利用霍夫曼树可以建立最佳判定算法，大大提高程序的执行速度。

2 霍夫曼树定义及霍夫曼算法

2.1 霍夫曼树定义

一般地，假设有 n个权值{w1,w2,…,wn}，如何构造有n个叶子结点的二叉树，每个叶子结点带有权值wi且带权路径长度WPL最小，这是一个很有实际意义的问题，霍夫曼早在1952年就提出一个带有一般规律的算法，很好地解决这个问题，因此人们把这种具有最小路径长度的二叉树称为霍夫曼树或最优二叉树，相应的算法称为霍夫曼算法。其中：WPL

转矩测量仪

=∑ni=1wili，wi为第i个叶子结点的权值，li为从根结点到第i个叶子结点的路径长度，n 为二叉树的叶子个数。

2.2 霍夫曼算法

(1) 根据给定的 n个权值{w1,w2,…,wn}构造n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左、右子树均空；

本文发布于:2024-09-20 23:16:43，感谢您对本站的认可！

本文链接：https://www.17tex.com/xueshu/129265.html

上一篇：地产宝典：投资理财--肯恩·费雪拉拉·霍夫曼斯

下一篇：关于新疆工业化发展水平的测度及分析