第6章 树和 与二叉树 数据结构课件.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 3. 哈夫曼树的应用 (1) 用于最佳判断过程。在考查课记分时往往把百分制转换成优(x≥90)、良(80x90)、中(70≤x80)、及格(60≤x70)、不及格(x60)五个等级。若不考虑学生考试分数的分布概率，程序判定过程很容易写成图6.23(a)所示的方法。我们知道，一般来讲学生考分大多分布在70～80分之间，从图6.23(a)可看出这种情况的x值要比较2～3次才能确定等级。而学生中考试不及格的人数很少，x值比较一次即可定等级。能否使出现次数多的在70～80分之间的x值比较次数减少些，而使很少出现的低于60分的x值比较次数多一些，以便提高程序的运行效率呢？假设学生成绩对于不及格、及格、中等、良好和优秀的分布概率分别为5%，15%，40%，30%，10%，以它们做为叶子的权值来构造哈夫曼树，如图6.23(b)所示。 此时带权路径长度最短，其值为205%。它可以使大部分的分数值经过较少的比较次数得到相应的等级。但是，事物往往不是绝对的，此时每个判断框内的条件较为复杂，比较两次，反而降低运行效率。所以我们采用折衷做法，调整后得图6.23(c)判定树。它更加切合实际。 图6.23 五分制不同规定 (2) 用于通信编码。在通信及数据传输中多采用二进制编码。为了使电文尽可能的缩短，可以对电文中每个字符出现的次数进行统计。设法让出现次数多的字符的二进制码短些，而让那些很少出现的字符的二进制码长一些。假设有一段电文，其中用到4个不同字符A、C、S、T，它们在电文中出现的次数分别为7、2、4、5。把7、2、4、5当做四个叶子的权值构造哈夫曼树如图6.24(a)所示。在树中令所有左分支取编码为0，令所有右分支取编码为1。将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列，就得这个叶子结点所代表的字符的二进制编码，如图6.24(b)所示。 图6.24 哈夫曼编码 6.7 有关二叉树实现的C语言源程序 6.7.1 二叉树的建立和遍历 在讨论了二叉树的各种算法之后，现在来构造设计完整的源程序。下列程序包含了丰富的内容，有利于拓宽视野，综合运用所学习的知识。在程序中增加了一个新的二叉树建立算法，提供了辅助于非递归遍历、按层二叉树的栈和队列的主要算法。读者可以从下列程序中选取少数几个函数模块(一个建立函数、一个递归遍历函数)进行上机练习。 # include stdio.h # include stdlib.h # define MAXSIZE 20 typedef int ElemType; typedef struct BNode /*二叉树结点结构*/ { ElemType data; struct BNode *lch, *rch; }BNode; typedef struct /*栈的顺序存储结构，服务于中序非递归遍历*/ { BNode *a[MAXSIZE]; int top; } sqstack; typedef struct /*循环队列顺序存储结构，服务于二叉树的按层遍历*/ { BNode *elem[MAXSIZE]; ? int front,rear; }squeue; BNode *creat_bt0(?); BNode *creat_bt1(?); void preorder(BNode *p); void inorder(BNode *p); void inorder2(BNode *t); void anceng(BNode *t); void push(sqstack *s,BNode *x); BNode *pop(sqstack *s); void enqueue(squeue *Q,BNode *x); BNode *deletqueue(squeue *Q); BNode *t, *p, *q;int z,i,j,k,e; main(?) { do { printf(\n\n); printf(\n\n 0. 建立二叉树(方法0) ); printf(\n\n 1. 建立二叉树(方法1 )); pri