贵州民族学院数据结构课件 第十一章.ppt

第十一章 树形结构的其他应用 第11章 树形结构的应用 11.1 哈夫曼树 11. 2 堆排序 11. 3 决策树 11. 4 博弈树 11.1 Huffman树 主要内容： 什么是Huffman树 Huffman树的构造方法 Huffman树的两个应用： 字符编码 判定问题 11. 1 哈夫曼树(Huffman)——最优二叉树 带权路径长度最短的二叉树 定义 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径 路径长度：路径上的分支数 树的路径长度：从树根到每一个结点的路径长度之和 二叉树的带权路径长度：树中所有带权结点的路径长度之和 Huffman树 设有n个权值{w1,w2, …,wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树称Huffman树 构造Huffman树的方法(Huffman算法) 构造Huffman树步骤 根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令其权值为wj 在森林中选取两棵结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和 从森林中删除这两棵树，同时将新得到的二叉树加入森林中 重复上述两步，直到森林只含一棵树为止，这棵树即Huffman树 C语言描述的算法 void huffman(int n, int w[ ], HNode t[ ]) //数组w用于是已知的权值集合，数组t存放结果——Huffman树 { int i,j,k,x1,x2,m1,m2; //x1,x2分别存放左、右子子树的下标，m1,m2存放当前最小的两个权值 for(i=1;i(2*n);i++) // 初始化结果数组 { t[i].pa=0；t[i].lc=0；t[i].rc=0; if(i=n) t[i].data=w[i]; else t[i].data=0; } for(i=1;in;i++) //找最小的两个权值m1,m2，并用它们作为左右子树构造新的二叉树 { m1=MAX；m2=MAX; //MAX代表∞ x1=0；x2=0; for(j=1;j(n+i);j++) { if((t[j].datam1)(t[j].pa==0)) { m2=m1; x2=x1; m1=t[j].data; x1=j; } // if else if((t[j].datam2)(t[j].pa==0)) { m2=t[j].data; x2=j; } // else } // for(j) // 构造子树，根结点存于t[n+i]中 k=n+i; t[x1].pa=k; t[x2].pa=k; t[k].data=m1+m2; t[k].lc=x1; t[k].rc=x2; } //for(i) } //huffman 11. 2 堆排序 堆的定义：n个元素的序列(k1,k2,…,kn)，当且仅当满足下列关系时 称之为堆 堆排序： 将无序序列建成一个堆，得到关键字最小（或最大）的记录； 输出堆顶的最小（大）值后，对剩余的n-1个元素调整成一个堆，则可得到n个元素的次小值； 重复执行上两步，得到一个有序序列， 堆排序需解决的两个问题： 如何由一个无序序列建成一个堆？ 如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？ 第二个问题解决方法——筛选 方法(最小堆)： 输出堆顶元素之后，以堆中最后一个元素替代之； 然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换 对交换过的子树的根，重复上一步操作，直至叶子结点，得到新的堆 称这个从堆顶至叶子的调整过程为“筛选” 算法描述 typedef struct { int key; //排序码域 int link; //指针域 ··· ···; //其他域 }RcdType; //记录类型 typedef RcdType Rcdlist[M+1]; //用顺序表存放记录 int sift(Rcdlist r, int k, int n) { int i,j; RcdType x; i=k; x=r[i]; j=2*i; while(j=n) { if((jn){r[j].keyr[j+