第四篇数据结构-树

页眉内容第十章非线性结构—树和图第九章讨论的线性表（包括栈、队列、与串）属于线性结构。在这种结构中，不管其存储方式如何，数据元素的逻辑位置之间呈线性关系，每一个数据元素通常只有一个前件（除第一个元素外）和一个后件（除最后一个元素外）。在实际生活中，可以用线性结构描述数据元素之间逻辑关系的问题是很广泛的，但也有很多问题不能依靠线性结构来解决，因此在这类问题中，数据元素间的逻辑关系不能用线性结构明确、方便地描述出来。一般来说，至少存在一个结点（数据元素）有多于一个前件或后件的数据结构称为非线性结构。具有非线性结构特征的数据结构有两种⑴树⑵图10.1树例如某学校试图将学生成绩表中的百分制成绩转换成五个等级，其中成绩0～59分为不及格，60～69分为及格，70～79分为中，80～89分为良，90～100分为优。现有个学生的百分制成绩，如何将他们的成绩转换成五级分制。下图揭示了一个百分制成绩的判定转换过程。对于这样一张简单的表，已经不能用线性结构来表示。因为表中数据元素可能有两个后件，它们之间的关系已经不是线性的了。上图中所示的表是一个非线性结构。由该图可以看出，虽然每一个结点可能有多个后件，但它们的前件却只有一个（第一个结点无前件）。这种非线性结构称为树，树表示了数据元素之间的层次关系，而这种层次关系仿佛像一棵倒长的树。下面讨论树的基本概念，其中重点讨论的是二叉树。一、.树的概念1、树的定义树是一种常见的非线性的数据结构。树的递归定义如下：树是n(n>0)个结点的有限集，这个集合满足以下条件：⑴有且仅有一个结点没有前件（父亲结点），该结点称为树的根；⑵除根外，其余的每个结点都有且仅有一个前件；⑶除根外，每一个结点都通过唯一的路径连到根上。这条路径由根开始，而未端就在该结点上，且除根以外，路径上的每一个结点都是前一个结点的后件（儿子结点）；由上述定义可知，树结构没有封闭的回路。下图给出了树的几个示例：１页眉内容2、结点的分类在树中，一个结点包含一个元素以及所有指向其子树的分支。结点一般分成三类⑴根结点：没有前件的结点。在树中有且仅有一个根结点。如上图（b）中的r；⑵分支结点：除根结点外，有后件的结点称为分支结点。如上图（b）中的a，b，c，x，t，d，i。分支结点亦是其子树的根；⑶叶结点：没有后件的结点称为树叶。如上图（b）中的w，h，e，f，s，m，o，n，j，u为叶结点。由树的定义可知，树叶本身也是其父结点的子树。根结点到每一个分支结点或叶结点的路径是唯一的。例如上图（b）中，从根r到结点i的唯一路径为rcti。3、有关度的定义⑴结点的度：一个结点的子树数目称为该结点的度。在上图（b）中，结点i度为3，结点t的度为2，结点b的度为1。显然，所有树叶的度为0。⑵树的度：所有结点中最大的度称为该树的度。图（b）中的树的度为3。4、树的深度（高度）树是分层次的。结点所在的层次是从根算起的。根结点在第一层，根的后件在第二层，其余各层依次类推。即若某个结点在第k层，则该结点的后件均处在第k+1层。图（b）中的树共有五层。在树中，父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度，亦称高度。图（b）中树的深度为5。5、森林所谓森林，是指若干棵互不相交的树的集合。如图（b）去掉根结点r，其原来的三棵子树Ta，Tb，Tc的集合{Ta，Tb，Tc}就为森林，这三棵子树的具体形态如图（c）。6、有序树和无序树按照树中同层结点是否保持有序性，可将树分为有序树和无序树。如果树中同层结点从左而右排列，其次序不容互换，这样的树称为有序树；如果同层结点的次序任意，这样的树称为无序树。二、树的表示 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 和存储结构1、树的表示方法树的表示方法一般有两种：页眉内容⑴自然界的树形表示法：用结点和边表示树，例如上图采用的就是自然界的树形表示法。树形表示法一般用于 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 问题。⑵括号表示法：先将根结点放入一对圆括号中，然后把它的子树按由左而右的顺序放入括号中，而对子树也采用同样方法处理：同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。例如图（b）可写成如下形式r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））2、树的存储结构树的存储结构一般有两种⑴静态的 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 数组。所有结点存储在一个数组中，数组元素为记录类型，包括数据域和长度为n(n为树的度)的数组，分别存储该结点的每一个儿子的下标Constn=树的度；max=结点数的上限；Typenode=record{结点类型}data：datatype；{数据域}ch：array[1‥n]ofinteger；{指向各儿子的下标}end；treetype=array[1..max]ofnode；Vartree：treetype；{树数组}例如图（b）的树，其记录数组如下。由于未规定同层结点的次序，因此每个结点儿子的下标序列（Tree[i].ch）任意。其中Tree[i].ch[j]=0 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 结点i的第j个儿子不存在。３页眉内容⑵动态的多重链表。由于树中结点可以有多个元素，所以可以用多重链表来描述比较方便。所谓多重链表，就是每个结点由数据域和n(n为树的度)个指针域共n+1个域组成，其表示方法如下：Constn=树的度；Typetreetype=↑node；{结点类型}node=recorddata：datatype；{数据域}next：array[1‥n]oftreetype；{指向各儿子的指针域}end；Varroot：treetype；{根结点指针}例如上图（b）中的树，其多重链表如下页眉内容显然，取树的度作为每个结点的链域数（即指向儿子结点的指针数）虽使各种算法简化，但会造成存储空间的大量浪费。因为可能有很多结点中存在空链域。空链域的个数x为多少呢？设树的结点数为n度为k。由于除根外的n-1个结点，每一个结点有且仅有一个前件，因此x+n-1=nk。X=n*(k-1)+1。能不能在减少浪费的空链域的前提下，寻找一种既使得每个结点的结构相同、又方便运算的树形式呢。下面将要看到，用二叉树来表示树，就能达到这个目的。三、二叉树的概念二叉树是一种很重要的非线性数据结构，它的特点是每个结点最多有两个后件，且其子树有左右之分（次序不能任意颠倒）。1、二叉树的递归定义和基本形态二叉树是以结点为元素的有限集，它或者为空，或者满足以下条件：⑴有一个特定的结点称为根；⑵余下的结点分为互不相交的子集L和R，其中R是根的左子树；L是根的右子树；L和R又是二叉树；由上述定义可以看出，二叉树和树是两个不同的概念⑴树的每一个结点可以有任意多个后件，而二叉树中每个结点的后件不能超过2；⑵树的子树可以不分次序（除有序树外）；而二叉树的子树有左右之分。我们称二叉树中结点的左后件为左儿子，右后件为右儿子。前面引入的有关树的一些基本术语对二叉树仍然适用。下图列出二叉树的五种基本形态：2、二叉树的两个特殊形态⑴满二叉树：如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。（例如下图(a)）可以验证具有n个叶结点的满二叉树共有2n-1个结点。⑵完全二叉树：如果一棵二叉树最多只有最下面两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树（例如下图(b)）3、二叉树的三个主要性质性质1：在二叉树的第i（≥1）层上，最多有2i-1个结点证明：我们采用数学归纳法证明：５页眉内容当i=1时只有一个根结点，即2i-1=20=1，结论成立。假设第k(i=k)层上最多有2k-1个结点，考虑i=k+1。由归纳假设，在二叉树第k层上最多有2k-1个结点，而每一个结点最多有两个子结点，因此在第k+1层上最多有2．2k-1=2(k+1)-1=2i，结论成立。综上所述，性质1成立。性质2：在深度为k(k≥1)的二叉树中最多有2k-1个结点。证明：由性质1，在二叉树第i层上最多有i-11层‥第k层的2个结点，显然，第k2i12k1个结点。证毕。最多结点数为i1性质3：在任何二叉树中，叶子结点数总比度为2的结点多1。证明：设n0为二叉树的叶结点数；n1为二叉树中度为1的结点数；n2为二叉树中度为2的结点数，显然（1）n=n+n+n012由于二叉树中除了根结点外，其余每个结点都有且仅有一个前件。设b为二叉树的前件个数，n=b+1（2）所有这些前件同时又为度为1和度为2的结点的后件。因此又有b=n1+2n2(3)例如下图除v0没有前件外，v1、v2、v3、v4、v5都有一个前件，b=5。而v1和v2为v0的后件，v3为v1的后件，v4和v5为v2的后件，因此b=b=n1+2n2=1+2*2=5。我们将（3）代入（2）得出n=n1+2n2+1(4)比较（1）和（4），得出n0=n2+1,即叶子数比度为2的结点数多1四、树或森林转换成二叉树1、普通有序树转换成二叉树我们在前面中曾讲过，在用多重链表示普通树时，会浪费存储空间。另外，由于树中各结点的度各不相同，因此对树中各结点的搜索比较困难。在实际应用中，往往将普通树转化成二叉树，这种处理既减少了存储空间的浪费又便于搜索。假设所讨论的普通树为有序树T，则将其转化成二叉树T’的规则如下：T中的结点与T’中的结点一一对应，即T中每个结点的序号和值在T’中保持不变；⑵T中某结点v的第一个儿子结点为v1，则在T’中v1为对应结点v的左儿子结点；⑶T中结点v的儿子序列，在T’中被依次链接成一条开始于v1的右链；由上述转化规则可以看出，一棵有序树转化成二叉树的根结点是没有右子树的，并且除保留每个结点的最左分支外，其余分支应去掉，然后从最左的儿子开始沿右儿子方页眉内容向依次链接该结点的全部儿子。例如将下图（a）所示的普通有序树转换成二叉树(下图（b）)。2、森林转换成二叉树如果m棵互不相交的普遍有序树组成了森林F={T1，Tm}。我们可以按下述规则将森林F转换成一棵二叉树b={R，LB，RB}：⑴若F为空（m=0），则b为空树；⑵若F非空（m≠0），则b的根R即为森林中第一棵树的根R(T1)；b的左子树LB是从T1的根结点的子树森林F1={T11，T12，T1k}转换而成的二叉树；其右子树RB是从森林F2={T2，T3，，Tm}转换成的二叉树。下图给出了森林转换成二叉树的示例由此可见，森林转换成二叉树的方法为⑴将各棵树的根相连；⑵将森林中的每棵树转换成相应的二叉树；0五、二叉树的存储结构二叉树的存储结构有两种形式⑴顺序存储结构⑵链式存储结构1、顺序存储结构将每个结点依次存放在一维数组中，用数组下标指示结点编号，编号的方法是从根结点开始编号1，然后由左而右进行连续编号。每个结点的信息包括⑴一个数据域（data）；⑵三个指针域，其中有父结点编号（prt）、左儿子结点编号（lch）和右儿子结点编号（rch）。满二叉树和完全二叉树一般采用顺序存储结构Constm=树中结点数上限；７页眉内容Typenode=record{结点类型}data：datatype；{数据值}prt，lch，rch：0‥m；{父结点、左儿子、右儿子编号}end；treetype=array[1‥m]ofnode；{二叉树的顺序表类型}VarTree：treetype；{二叉树}例如，采用数组tree存储二叉树（如下图）2、链式存储结构对于一般的二叉树，通常采用链式分配，即用二重链表表示一般的二叉树。这种链式分配即可以采用静态数据结构（数组），又可以采用动态数据结构（指针）。如果二叉树的存储需求量超过64Kb，则采用后者。由于二叉树中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域：⑴值域：data⑵左指针域：lch⑶右指针域：rch这种链表也称为二叉链表。二叉链表头指针bt指向二叉树的根结点Typebitrpetr=benode=record{data：datatype；lch，rch：bitreptrend；Var↑bnode；{结点指针类型}结点类型}{值域}{左指针域和右指针域}bt：bitreptr；{头指针}例如用下图（b）所示的二叉链表存储二叉树（下图（a））页眉内容六、树或森林的遍历1、二叉树的遍历所谓二叉树的遍历是指按照一定的规律不重复地访问二叉树中的每一个结点。在访问到每个结点时，可以取出结点中的信息，亦可以对结点作其它的处理，对于线性结构来说，遍历并非难事，但对二叉树来说，由于它是一种非线性结构，必须要找到一种完全而有规则的遍历方法，通过遍历得到二叉树中各个结点信息的线性序列。如果用L、D、R分别表示遍历左子树、访问根结点、遍历右子树，则对二叉树的遍历可以有下列六种（3!=6）组合：LDR、LRD、DLR、DRL、RDL、RLD若再限定先左后右的次序，则只剩下三种组合LDR、LRD、DLR这三种遍历规则分别称为中序遍历。后序遍历和前序遍历。下面分别介绍这三种遍历的方法。在讲解过程中，二叉树的存储采用动态的二重链表形式。为了方便叙述，我们以下图为例解释三种遍历规则，并且分别以二叉链表和数组两种存储结构给出三种遍历的程序。⑴前序遍历前序遍历的规则如下：若二叉树为空，则退出。否则⑴访问处理根结点；⑵前序遍历左子树；⑶前序遍历右子树；例如对于如上图所示的二叉树，前序遍历的过程为：先访问根结点a，再遍历其左子树，然后遍历其右子树。在遍历其左子树时，也按照前序规则，即先访问根结点b，然后遍历其左子树，最后遍历右子树，，依次类推，直到根结点a的左子树的所有结点全部被访问完毕；再以同样的规则访问a的右子树中的所有结点；最后可以得到如下的前序遍历序列（简称前序序列）abdehicfg算法如下：９页眉内容⑵中序遍历中序遍历的规则如下：若二叉树为空，则退出；否则⑴中序遍历左子树；⑵访问处理根结点；⑶中序遍历右子树；若中序遍历上图中的二叉树，可以得到如下的中序序列：dbheiafcg算法如下：⑶后序遍历后序遍历的规则如下：若二叉树为空，则退出；否则⑴后序遍历左子树；⑵后序遍历右子树；⑶访问处理根结点；若后序遍历上图中的二叉树，可以得到如下的后序序列dhiebfgca算法如下：页眉内容2、普遍有序树的遍历仿照二叉树的前序遍历和中序遍历，可以定义普遍有序树的两种遍历顺序。由于普遍有序树中的子女数可能多于两个，因此不好仿照二叉树遍历中序与其女子的对称次序。下面，给出普遍有序树转化为二叉树的一个例子，看一看，普遍有序树的遍历顺序可借用二叉树的哪一种遍历顺序实现。⑴先根次序遍历树先根次序遍历的规则如下：若树为空，则退出；否则先根访问树的根结点，然后先根遍历根的每棵子树。例如，对上图(a)中的普遍有序树进行先根遍历，可得到树的先根序列为rawxdhebfcstimonju若对上图(b)中的二叉树进行前序遍历，得到的前序序列与之相同。由此可见，当普遍有序树转化为二叉树时，可借用二叉树的前序遍历实现普遍有序树的先根遍历。⑵后根次序遍历树后根次序遍历的规则如下：若树为空，则退出；否则先依次后根遍历每棵子树，然后访问根结点。例如对上图(a)中的普遍有序树进行后根遍历，可得到树的后根序列为whdexafbsmonijtucr若对上图(b)中的二叉树进行中序遍历，得到的中序序列与之相同。由此可见，当普遍有序树转化为二叉树时，可借用二叉树的中序遍历实现普遍有序树的后根遍历。【例题输入一棵普通有序树，输出该树的先根次序和后根次序。输入：１１页眉内容顶点个数n（1≤n≤200）以下含n行，其中第i行（1≤i≤n）的元素依次为结点i的数据值ai。以后各元素为结点i的儿子序列，以0结束。若ai后仅含一个0，则说明结点i为叶子。例如对于下图（ａ）的多叉树对应的输入信息为18’r’4203’a’560’b’70’c’89100’w’0’x’11120’f’0’s13’140’t0’00’u’0’’d’150’e’0’i’1617180’j’0’h’0’m’0’o’0’h’0输出：两行，分别为普通有序树的先根次序和后根次序分析：“四、树或森林转换成二叉树”一节中介绍了普通有序树转换成二叉树的规则。我们在输入普通有序树的同时，按照规则进行转换：fillchar（tree，sizeof（tree），0）；readln(n)；fori←1tondo{{二叉树初始化}{读入普通有序树的结点个数}依次读入普通有序树中每个结点的信息}beginread(tree[i]．data)；read(j)；ifj<>0then{读结点i的第一个儿子序号{若结点j非叶子}j}begin页眉内容tree[i]．lch←j；tree[j]．prt←i；{结点j作为结点i的左儿子}p←j；{从结点j出发转换其它兄弟结点}repeatread(j)；{读结点i的下一个儿子序号j}ifj<>0thenbegintree[p]．rch←j；tree[j]．prt←p；{结点j作为结点p的右儿子}←j；end；{then}untilj=0；{直至处理完结点i的所有儿子信息}end；{then}writeln；{准备输入结点i+1的儿子信息}end；{for}W（n2）。例如下图上述转换算法的时间复杂度为图（ａ）的普通有序树经转换运算后得出的tree数组如下Dataprtlchrch1’r’0202’a’1533’b’2744’c’3805’w’2066’x’51107’f’3008’s’4099’t’801010’u’90011’d’6151212’e’110013’i’8161414’j’130015’h’110016’m’1301717’o’1601818’n’1700该数组正好对应图（b）的二叉树。１３页眉内容在得出二叉树tree后，我们分别调用过程preorder(1)和过程inorder(1)，对其进行前序遍历和中序遍历，得出普通有序树的先根次序和后根次序。由此得出主程序输入普通有序树并转换成二叉树tree；preorder(1)；{对二叉树tree进行前序遍历}inorder(1)；{对二叉树tree进行中序遍历}3、森林的遍历若有多棵互不相交的普通有序树组成森林，则同样可以导出森林的两种遍历规则。由森林与二叉树之间的转换规则可知，当森林转换成二叉树时，其第一棵树根结点的子树森林转换成左子树，剩余树的森林转换成右子树。由此得出森林的遍历和转化后二叉树的遍历有对应关系。下面，给出森林转化为二叉树的一个例子，看一看，森林遍历顺序可借用二叉树的哪一种遍历顺序实现。⑴先根遍历森林若森林非空，则可按下述规则遍历之访问森林中第一棵树的根结点；先根遍历第一棵树中根结点的子树森林；先根遍历其余树构成的森林；IJ若对上图(a)中的森林进行先根遍历，则得到森林的先根序列为。森林的先根遍历即为其对应的二叉树的前序遍历。例如对上图abCDEFGH(c)中的二叉树进行前遍历，结果是相同的。⑵后根遍历森林若森林非空，则可按下述规则遍历之①后根遍历森林中第一棵树的根结点的子树森林；②访问第一棵树的根结点；③后根遍历其余树构成的森林；若对上图(a)中的森林进行先根遍历，则得到森林的后根序列为bCDaFEHJIG。森林的后根遍历即为其对应的二叉树的中序遍历。例如，对上图(c)中的二叉树进行中序遍历，亦可得出对应森林（上图(a)的后根遍历序列。七、由二叉树的两种遍历顺序确定树结构遍历二叉树（如下图）有三种规则：前序遍历：根—左子树—右子树；中序遍历：左子树—根—右子树；后序遍历：左子树—右子树—根；页眉内容从上述遍历规则可以看出，前序遍历的第一个字符和后序遍历的最后一个字符为根，中序遍历中位于根左方的子串和位于根右方的子串分别反映了左子树和右子树的结构，因此二叉树的形态可以由其中序与后序或者前序与中序唯一确定。但无法反映左子树和右子树结构的前序遍历与后序遍历却不能做到这一点，因此这两个遍历顺序可对应多种二叉树的形态。【例题输入：二叉树的中序遍历顺序与后序遍历顺序输出：二叉树的前序遍历顺序输入：二叉树的中序遍历顺序与前序遍历顺序输出：二叉树的后序遍历顺序分析：二叉树的形态可以由其中序与后序或者前序与中序唯一确定，因此可以由中序与后序得出前序，由前序与中序得出后序。1、由二叉树的中序遍历顺序与后序遍历顺序确定树结构由二叉树的遍历规则可以看出，后序遍历的最后一个字符为根，中序遍历中位于该字符左侧的子串为左子树中序遍历的结果；中序遍历中位于该字符右侧的子串为右子树中序遍历的结果。设中序遍历s’=s1’sk’sn’后序遍历s”=s1”sn”显然，后序遍历中的sn”为二叉树的根。按照前序遍历的规则输出sn”。在中序遍历中与sn”相同的字符为sk’。若k>1，说明左子树存在，位于sk’左侧的子串s1’sk-1’为左子树中序遍历的结果，后序遍历中的前缀s1”sk-1”为左子树后序遍历的结果；若k1{若左子树存在，则递归遍历左子树}thensolve1(copy(s1ifk 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 一个递归过程solve2。该过程输入的值参为前序序列s2和中序序列s1两个字串，计算和输出s1和s2对应的后序遍历。proceduresolve2(s1，s2:string)；{计算和输出中序遍历s1和前序遍历s2对应的后序遍历}vark:integer；beginiflength(s2)=1{若当前子树仅剩一个节点，则输出}页眉内容then输出s2elsebegink←pos(s2[1]，s1)；{在中序遍历中寻找子树根}ifk>1{若左子树存在，则递归遍历左子树}thensolve2(copy(s1，1，k-1)，copy(s2，2，k-1))；ifk0thenp←b[p]．lelsebeginb[p]．l←i；break；end{else}else{若ai≥b[p]．data时顺右指针方向寻找顶点i的插入位置}ifb[p]．r<>0thenp←b[p]．relsebeginb[p]．r←i；break；end；{else}endend；{while}；{for}end；{createtree}对以bt为根的二叉排序树进行中序遍历（inorder(bt)），便可以得到a表的递增序列。构造二叉排序树的平均时间复杂度为a(n*log2n)。当二叉排序树退化成一条链时，最坏的时间复杂度为W((1n)*n)。2显然，在各种排序方法中，二叉排序树的时间效率比较理想。由此得出主程序readln(n){fori←1tondoread(ai)；{}输入a序列}writelncreatetreeinorder(bt)；；；{{构造二叉排序树}中序遍历二叉排序树}页眉内容２、最优二叉树【例题全校学生的成绩由百分制转换成五等分制，在五个等次以上的分布不均匀，分布规律如下表：百分制分数范0～5960～6970～7980～8990～围100分布情况%515403010现有10000个数据。下图分别列出两种判定转化过程：若按照上图(a)的判定过程进行转换，则有80%的数据至少要进行3次比较才能得出结果。完成10000个数据转换的比较次数k=10000*（1*5%+2*15%+3*40%+4*(30%+10%)）=31500次。若按照上图(b)的判定过程进行转换，则有20%的数据需要进行3次比较才能得出结果，而有80%的数据至多仅需要进行2次比较就可得出结果。完成10000个数据转换的比较次数k=10000*（2*（10%+30%+40%）+3*（5%+15%））=22000次显然后者的判定过程的效率比前者高。还有没有更好的判定过程可使比较次数进一步减少呢？回答是否定的，即上图(b)所示的判定过程是最优的。现在的问题是，如果给出n（1≤n≤1000000）个学生的百分制成绩，要将它们转换成五分制成绩，至少要经过多少次比较。其中每个等次成绩的最少比较多少次输入：nw1w2w3w4w5(五个等次的成绩分布规律)输出：最少比较次数个整数，分别为每个等次成绩的最少比较次数分析：⑴最优二叉树的定义在具有n个带权叶结点的二叉树中，使所有叶结点的带权路径长度之和（即二叉树的带权路径长度）为最小的二叉树，称为最优二叉树（又称最优搜索树或哈夫曼树），即最优二叉树使nWkPk（wk—第k个叶结点的权值；pk—第k个叶结点的带权路径长度）k1达到最小。例如下图为三棵二叉树，它们都有5个叶结点a、b、c、d，e其权值分别为7、5、2、4、6。１９页眉内容显然图(b)所示的二叉树的带权路径长度和最小，并且可以验证，它恰为最优二叉树。在实际生活中,最优二叉树很有应用价值，例题就是一个生动的示例。最优判定过程即为一棵最优二叉树，这棵树的带权路径长度为（2*（10%+30%+40%）+3*5%+15%））=2.2，显然，要求转换的百分制成绩数愈多，比较次数愈少。由此可见，如果给出数据表中每一个数据的分布情况，则以每一个数据及其分布情况为为带权叶结点构造最优二叉树，是最优的查找方法。⑵最优二叉树的构造方法假定给出n个结点ki(i=1‥n)，其权值分别为wi(i=1‥n)。要构造以此n个结点为叶结点的最优二叉树，其构造方法如下：首先，将给定的n个结点构成n棵二叉树的集合F={T1，T2，，Tn}。其中每棵二叉树Ti中只有一个权值为wi的根结点ki，其左、右子树均为空。然后做以下两步⑴在F中选取根结点权值最小的两棵二叉树作为左右子树，构造一棵新的二叉树，并且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和；⑵在F中删除这两棵二叉树，同时将新得到的二叉树加入F中；重复⑴、⑵，直到在F中只含有一棵二叉树为止。这棵二叉树便是最优二叉树。以上构造最优二叉树的方法称为哈夫曼（huffmann）算法。例如：给定五个结点k1，k2，k3，k4，k5，其权值分别为16、2、18、16、23。构造最优二叉树的过程如下：⑴构造初始集合F，F中各二叉树根结点的权值分别为16，2，18，16，23（如下图）：⑵以具有权值16及2的根结点的两棵二叉树为左、右子树，构造一棵根权值为18的新二叉树，并从F中删去这两棵二叉树（如下图）：页眉内容⑶以同样的方法，得到一个新二叉树的集合F，其根结点的权值分别为23，18，34（如下图）：⑷又得到一个新二叉树的集合F，其根结点的权值分别为34，41（如下图）：⑸最后得到最优二叉树（如下图），其根结点的权值为75，结点数为2*5-1=9。在最优二叉树中非叶结点的度均为2，为满二叉树，因此采用顺序存储结构为宜。如果带权叶结点数为n个，则最优二叉树的结点数为2n-1个。由此得出最优二叉树的数据类型定义Constn=叶结点数的上限；m=2*n-1；{最优二叉树的结点数}Typenode=record{结点类型}data：integer；{权值}prt，lch，rch,lth：0‥m；{父指针、左、右指针和路径长度end；}wtype=array[1‥n]ofintegertreetype=array[1‥m]ofnode；；{n{个叶结点权值的类型}最优二叉树的数组类型}Vartree：treetype；{其中tree[1‥n]为叶结点，tree[n+1‥2n-1]为中间结点，根为tree[2n-1]}在最优二叉树的顺序存储结构中前n个结点为叶结点。构造最优二叉树的算法如下：procedurehufm(w：wtype；vartree：treetype；varbt：integer)；functionmin(h：integer)：integer；{在前h个结点中选择父指针为0且权值最小的结点min}begin２１页眉内容ml←∞；forp←1tohdoif(tree[p]．prt=0)and(m1>tree[p]．data)thenbeginiend←p；m1←tree[p]；{then}．data；min←i；end；{min}beginfillchar(tree，sizeof(tree)，0)；{构造初始集合fori←1tondoread(tree[i]．Data)；fork←n+1tomdo{构造最优二叉树}F}begin{计算k为根的左儿子和右儿子}i←min(k-1)；tree[i]．prt←k；tree[k]．lch←i；j←min(k-1)；tree[j]．prt←k；tree[k]．rch←jtree[k]．data←tree[i]．data+tree[j]．data；；end；{for}bt←m；end；{hufm}计算最优二叉树的时间复杂度为W（n2）。我们可以通过调用ht(m)计算每一个叶结点的路径长度procedureht(t:integer);{通过前序遍历计算每一个叶结点的路径长度}beginift=m{若结点t为根，则路径长度为0；否则结点t的路径长度为其父结点的路径长度+1}thentree[t].lthelsetree[t].lth←0←tree[tree[t].prt].lth+1；iftree[t].lch<>0thenbeginht(tree[t].lch)；ht(tree[t].rch)；end；{then}{分别递归左右子树}end；{ht}由此可见，叶结点t（1≤t≤5）的带权路径长度即为tree[t].lth*tree[t].data。在主程序中，首先输入要求转换的百分制成绩数n和五个等次的成绩分布规律w1w2w3w4w5，然后调用hufm(w，tree，bt)，计算最优二叉树tree和根序号bt，调用ht(bt)计算每个等次成绩的最少比较次数（tree[1].lth‥tree[5].lth）。由此得出，n个数据的最少比较次数为n*tree[bt].data。其中第i个等次的成绩（1≤i≤5）需要比较n**tree[i].data*tree[i].lth次。Readln(n)；{输入要求转换的百分制成绩数}页眉内容Fori←1to5doReadln(wi)；{输入五个等次的成绩分布规律}hufm(w，tree，bt)；{计算最优二叉树tree和根序号bt}ht(bt)；{计算每个等次成绩的比较次数}Writeln(n*tree[bt].data)；{输出n个数据的最少比较次数}Fori←1to5Write（n*tree[i].lth*tree[i].data）；{输出每个等次成绩的比较次数}２３