数据结构与算法课件：DS05_二叉树13

《数据结构与算法课件：DS05_二叉树13》由会员分享，可在线阅读，更多相关《数据结构与算法课件：DS05_二叉树13（54页珍藏版）》请在装配图网上搜索。

1、第第13讲讲 堆与优先队列与优先队列、Huffman树 本讲主要内容5.5 堆与优先队列堆与优先队列5.5.1 堆的定义及其堆的定义及其实现实现5.6 Huffman树及其应用树及其应用5.6.1 Huffman树树5.6.2 Huffman编码编码自测自测题题5.5.1 堆的定义及其实现堆的定义及其实现n最小值堆最小值堆：最小值堆是一个关键码序列：最小值堆是一个关键码序列K0，K1，Kn-1，它具有如下，它具有如下特性特性：qKiK2i+1 (i=0，1，n/2-1)qKiK2i十十25.5.1 堆的定义及其实现堆的定义及其实现堆的性质堆的性质n从逻辑的角度来讲，堆是一种树形结构，而且是从逻

2、辑的角度来讲，堆是一种树形结构，而且是一种特殊的完一种特殊的完全二叉树全二叉树。此完全二叉树的每个结点对应于序列中的一个关键。此完全二叉树的每个结点对应于序列中的一个关键码，根结点对应于关键码码，根结点对应于关键码K0，按层次从左至右依次类推。，按层次从左至右依次类推。n说其特殊，主要是因为堆序只是局部有序，即最小堆对应的完说其特殊，主要是因为堆序只是局部有序，即最小堆对应的完全二叉树中全二叉树中所有内部结点的值均不大于其左右孩子的关键码值所有内部结点的值均不大于其左右孩子的关键码值，而一个结点与其兄弟之间没有必然的联系。，而一个结点与其兄弟之间没有必然的联系。n最小堆不像二叉搜索树那样实现了

3、关键码的完全排序。相比较最小堆不像二叉搜索树那样实现了关键码的完全排序。相比较而言，只有当结点之间是父子关系的时候，才可以确定这两个而言，只有当结点之间是父子关系的时候，才可以确定这两个结点关键码的大小关系。结点关键码的大小关系。5.5.1 堆的定义及其实现堆的定义及其实现关键码序列关键码序列K=12，14，15，19，20，17，18，24，22，26所对所对应的最小堆形成的完全二叉树形式为图所示：应的最小堆形成的完全二叉树形式为图所示：121518171420192422265.5.1 堆的定义及其实现堆的定义及其实现图图5.15 在最小堆在最小堆5.14中中插入插入元素元素13，需从下至

4、上调堆，需从下至上调堆12151420191817132426225.5.1 堆的定义及其实现图图5.16 在最小堆在最小堆5.14中中删除删除元素元素14，需从上至下调堆需从上至下调堆12351420195847242622注意有些情况需，从下至上调堆，如删除注意有些情况需，从下至上调堆，如删除58删除删除元素元素14删除删除元素元素585.5.1 堆的定义及其实现堆的定义及其实现建堆过程：建堆过程：q首先将所有关键码放到一维数组中，这时形成的完首先将所有关键码放到一维数组中，这时形成的完全二叉树并不具备最小堆的特性，但是全二叉树并不具备最小堆的特性，但是仅包含叶子仅包含叶子结点的子树已经是

5、堆结点的子树已经是堆q即在有即在有n(编号从编号从0开始开始)个结点的完全二叉树中，当个结点的完全二叉树中，当i n/2-1时，以关键码时，以关键码Ki为根的子树已经是堆。为根的子树已经是堆。q这时从含有内部结点数最少的子树（这种子树在完这时从含有内部结点数最少的子树（这种子树在完全二叉树的倒数第二层，此时全二叉树的倒数第二层，此时i=n/2-1）开始，从）开始，从右至左依次调整右至左依次调整q对这一层调整完成之后，继续对上一层进行同样的对这一层调整完成之后，继续对上一层进行同样的工作，工作，直到整个过程到达树根时直到整个过程到达树根时，整棵完全二叉树，整棵完全二叉树就成为一个堆了就成为一个堆

6、了5.5.1 堆的定义及其实现对于关键码集合对于关键码集合K=19，8，35，65，40，3，7，45，用筛选法，用筛选法建堆的过程。其中建堆的过程。其中n=8，n/2-1=3，所以从，所以从K3=65开始调整。开始调整。19835 7 3406545以以k3为根的子树为根的子树 6545 调整调整以以k2为根的子树为根的子树 353 调整调整以以k1为根的子树为根的子树 840,83 调整调整197 调整图图5.17 建堆过程示例建堆过程示例2022-11-610自测题自测题 n 9.已知关键字序列5,8,12,19,28,20,15,22是小根堆（最小堆）,插入关键字3,调整后得到的小根堆

7、是nA.3,5,12,8,28,20,15,22,19 nB.3,5,12,19,20,15,22,8,28nC.3,8,12,5,20,15,22,28,19 nD.3,12,5,8,28,20,15,22,19n【2009年全国硕士研究生入学计算机学科专业基础综合试题】n A堆的类定义和筛选法堆的类定义和筛选法(1)（略）（略）template class MinHeap /最小堆类定义最小堆类定义private:T*heapArray;/存放堆数据的数组存放堆数据的数组int CurrentSize;/当前堆中元素数目当前堆中元素数目int MaxSize;/堆所能容纳的最大元素数目堆所

8、能容纳的最大元素数目void swap(int pos_x,int pos_y);/交换位置交换位置x和和y的元素的元素void BuildHeap();/建堆建堆 public:MinHeap(const int n);/构造函数，构造函数，n表示表示 堆的最大元素数目堆的最大元素数目virtual MinHeap()delete heapArray;/析构函数析构函数bool isEmpty();/如果堆空，则返回真如果堆空，则返回真 bool isLeaf(int pos)const;/如果是叶结点，返回如果是叶结点，返回TRUE int leftchild(int pos)const;

9、/返回左孩子位置返回左孩子位置 int rightchild(int pos)const;/返回右孩子位置返回右孩子位置 int parent(int pos)const;/返回父结点位置返回父结点位置bool Remove(int pos,T&node);/删除给定下标的元素删除给定下标的元素bool Insert(const T&newNode);/向堆中插入新元素向堆中插入新元素newNodeT&RemoveMin();/从堆顶删除最小值从堆顶删除最小值void SiftUp(int position);/从从position向上开始调整，使序列成为堆向上开始调整，使序列成为堆void

10、SiftDown(int left);/向下筛选，参数向下筛选，参数left表示开始处理的数组下标表示开始处理的数组下标;堆的类定义和筛选法堆的类定义和筛选法(2)（略）（略）templateMinHeap:MinHeap(const int n)if(n=0)return;CurrentSize=0;MaxSize=n;/初始化堆容量为初始化堆容量为nheapArray=new TMaxSize;/创建堆空创建堆空 /此处，省略数组赋值部分此处，省略数组赋值部分BuildHeap();/此处（可进行堆元素的赋值工作），从下至上调整堆此处（可进行堆元素的赋值工作），从下至上调整堆堆的类定义和筛

11、选法堆的类定义和筛选法(3)（略）（略）templatebool MinHeap:isLeaf(int pos)const return(pos=CurrentSize/2)&(pos CurrentSize);templatevoid MinHeap:BuildHeap()for(int i=CurrentSize/2-1;i=0;i-)/反复调用筛选函数反复调用筛选函数SiftDown(i);堆的类定义和筛选法堆的类定义和筛选法(4)（略）（略）/从从0开始开始templateint MinHeap:leftchild(int pos)const return 2*pos+1;/返回左孩子

12、位置返回左孩子位置templateint MinHeap:rightchild(int pos)const return 2*pos+2;/返回右孩子位置返回右孩子位置templateint MinHeap:parent(int pos)const return(pos-1)/2;/返回父结点位置返回父结点位置堆的类定义和筛选法堆的类定义和筛选法(5)（略）（略）template/向堆中插入新元素向堆中插入新元素newNodebool MinHeap:Insert(const T&newNode)if(CurrentSize=MaxSize)/堆空间已经满堆空间已经满return FALSE;

13、heapArrayCurrentSize=newNode;SiftUp(CurrentSize);/向上调整向上调整CurrentSize+;return TRUE;堆的类定义和筛选法堆的类定义和筛选法(6)（略）（略）templateT&MinHeap:RemoveMin()/从堆顶删除最小值从堆顶删除最小值if(CurrentSize=0)cout1)SiftDown(0);/从堆顶开始筛选从堆顶开始筛选return heapArrayCurrentSize;堆的类定义和筛选法堆的类定义和筛选法(7)（略）（略）template/删除给定下标的元素删除给定下标的元素bool MinHeap

14、:Remove(int pos,T&node)if(pos=CurrentSize)return false;node=heapArraypos;/用最后的元素值替代删除位置的元素用最后的元素值替代删除位置的元素heapArraypos=heapArray-CurrentSize;if(heapArrayparent(pos)heapArraypos)SiftUp(pos);/当前元素小于父结点，需要上升调整当前元素小于父结点，需要上升调整else SiftDown(pos);/当前元素大于父结点，向下筛当前元素大于父结点，向下筛return true;堆的类定义和筛选法堆的类定义和筛选法(8

15、)（略）（略）templatevoid MinHeap:SiftUp(int position)/从从position向上开始调整向上开始调整int temppos=position;T temp=heapArraytemppos;while(temppos0)&(heapArrayparent(temppos)temp)/没到根结点且双亲的值大于孩子没到根结点且双亲的值大于孩子heapArraytemppos=heapArrayparent(temppos);temppos=parent(temppos);heapArraytemppos=temp;堆的类定义和筛选法堆的类定义和筛选法(9)

16、（略）（略）template void MinHeap:SiftDown(int position)int i=position;/标识父结点标识父结点int j=leftchild(i);/标识关键值较小的子结点标识关键值较小的子结点T temp=heapArrayi;/保存父结点保存父结点while(j CurrentSize)/向下过筛，所以向下过筛，所以j CurrentSize if(j heapArrayj+1)j+;/若有右子节点，且小于左子节点若有右子节点，且小于左子节点,j指向右子结点指向右子结点 if(tempheapArrayj)/若父节点大于子节点的值则交换位置若父节点

17、大于子节点的值则交换位置heapArrayi=heapArrayj;/子结点值赋给父结点子结点值赋给父结点i=j;j=leftchild(j);else break;/堆序满足，跳出堆序满足，跳出heapArrayi=temp;堆的类定义和筛选法堆的类定义和筛选法(10)（略）（略）建堆效率（略）建堆效率（略）n对于对于n个结点的堆，其对应的完全二叉树的层数为个结点的堆，其对应的完全二叉树的层数为logn。n设设i表示二叉树的层编号，则第表示二叉树的层编号，则第i层上的结点数最多为层上的结点数最多为2i(i 0)。n建堆的过程中，对每一个非叶子结点都调用了一次建堆的过程中，对每一个非叶子结点都

18、调用了一次SiftDown调调整算法，而每个数据元素最多向下调整到最底层，即第整算法，而每个数据元素最多向下调整到最底层，即第i层上的层上的结点向下调整到最底层的调整次数为结点向下调整到最底层的调整次数为logn i。因此，。因此，建堆的计建堆的计算时间算时间为为 （公式5.3）令j=logn i，代入5.3式得 （公式5.4）log02(log)niin iloglogloglog0002(log)222nnnin jjijjjn ijnn 建堆效率（略）建堆效率（略）n建堆算法的时间复杂度是建堆算法的时间复杂度是O(n)。这就说明可以。这就说明可以在线性时间内把一个无序的序列转化成堆序在线

19、性时间内把一个无序的序列转化成堆序n由于堆有由于堆有log n层深，层深，插入结点、删除普通元素插入结点、删除普通元素和和删除最删除最小元素的平均时间代价和小元素的平均时间代价和最最差时间代差时间代价都是价都是(log n)n最小堆只适合于查找最小值，查找任意值的效最小堆只适合于查找最小值，查找任意值的效率不高率不高5.5.2 优先队列（略）优先队列（略）n优先队列优先队列(priority queue)是一种有用的数据结构。它是一种有用的数据结构。它是是0个或多个元素的集合，个或多个元素的集合，每个元素都有一个关键码值每个元素都有一个关键码值，执行的操作有查找、插入和删除一个元素。，执行的操

20、作有查找、插入和删除一个元素。n优先队列的主要特点是支持从一个集合中快速地查找并优先队列的主要特点是支持从一个集合中快速地查找并移出具有最大值或最小值的元素。最小优先队列，适合移出具有最大值或最小值的元素。最小优先队列，适合查找和删除最小元素；最大优先队列中，适合查找和删查找和删除最小元素；最大优先队列中，适合查找和删除最大元素。除最大元素。2022-11-624 已知关键字序列已知关键字序列(K1,K2,K3,Kn-1)是大根堆。是大根堆。(1)试写出一算法将试写出一算法将(K1,K2,K3,Kn-1,Kn)调整为大调整为大根堆；根堆；(2)利用利用(1)的算法写一个建大根堆的算法。的算法写

21、一个建大根堆的算法。【中科院软件所中科院软件所 1999 七七.2(7分分)】堆排（略）（略）序算法举例 2022-11-625大根堆，双亲的值比孩子大（略）大根堆，双亲的值比孩子大（略）(1)void sift(RecType R,int n)(1)void sift(RecType R,int n)假设假设 R1.n-1R1.n-1是大堆是大堆 ,本算法把本算法把R1.nR1.n调成大堆调成大堆 j=n;j=n;R0=Rj;R0=Rj;for(i=n/2;i=1;i=i/2)for(i=n/2;i=1;i=i/2)/向上调整向上调整 if(R0.keyRi.key)if(R0.keyRi.

22、key)/孩子值大于双亲孩子值大于双亲 Rj=Ri;j=i;Rj=Ri;j=i;else break;else break;已满足堆定义已满足堆定义 Rj=R0;Rj=R0;sift sift(2)void HeapBuilder(RecType R,int n)(2)void HeapBuilder(RecType R,int n)for(i=2;i=n;i+)for(i=2;i=n;i+)sift(R,i);sift(R,i);5.6 Huffman树及其应用 n5.6.1 Huffman树树n5.6.2 Huffman编码编码哈夫曼树的概念 n路径路径：从树中一个结点到另一个结点之间的分

23、支从树中一个结点到另一个结点之间的分支构成两个结点之间的构成两个结点之间的路径。路径。n路径长度路径长度：路径上的分支数目称为路径上的分支数目称为路径长度。路径长度。n树的路径长度树的路径长度：树的根结点到树中每一个结点的树的根结点到树中每一个结点的路径长度的和。路径长度的和。n结点的带权的路径长度结点的带权的路径长度：该结点到根结点之该结点到根结点之间的路程长度与该结点上权的乘积间的路程长度与该结点上权的乘积n树的带权的路径长度树的带权的路径长度：树中树中所有叶子结点的所有叶子结点的带 权 的 路 径 长 度 的 和。通 常 记 为：带 权 的 路 径 长 度 的 和。通 常 记 为：WPL

24、(Weighted Path Length)。n由由n个带权值的叶子结点构成的二叉树中个带权值的叶子结点构成的二叉树中，WPL最小的二叉树称为最小的二叉树称为最优二叉树最优二叉树，或哈夫曼（Huffman）树。）树。哈夫曼树的概念（续）常用该定义！常用该定义！5.6.1 Huffman树n假设有假设有n n个权值分别为个权值分别为w w0 0，w w1 1，w wn-1n-1(n2)(n2)的结点，求的结点，求带权外带权外部路径长度部路径长度就是要构造一棵具有就是要构造一棵具有n n个外部结点的个外部结点的扩充二叉树扩充二叉树，每，每一个外部结点一个外部结点k ki i取取w wi i作为它的

25、权，作为它的权，l li i表示该外部结点的路径长度表示该外部结点的路径长度，则带权外部路径长度可记作，则带权外部路径长度可记作 其中带权外部路径长度最小的二叉树称为其中带权外部路径长度最小的二叉树称为HuffmanHuffman树树10niiilw该定义并非该定义并非公认！公认！5.6.1 Huffman树下图表示了三棵具有下图表示了三棵具有4个外部结点的二叉树，各外部结点个外部结点的二叉树，各外部结点的权值分别为的权值分别为6，2，3，4（即这（即这4个结点做叶子）。个结点做叶子）。它们的带权外部路径长度分别为：它们的带权外部路径长度分别为：(a)6(a)62+22+22+32+32+42

26、+42=302=30(b)6(b)62+22+23+33+33+43+41=311=31(c)6(c)61+21+23+33+33+43+42=292=29其中，其中，5.18(c)5.18(c)中所示的二叉树外部带权路径长度最小。可以验证，中所示的二叉树外部带权路径长度最小。可以验证，它就是一棵它就是一棵HuffmanHuffman树，也就是说，这棵树在所有的具有树，也就是说，这棵树在所有的具有6 6，2 2，3 3，4 4权值的叶结点的二叉树中带权外部路径长度最小。权值的叶结点的二叉树中带权外部路径长度最小。6234(a)2364(b)4236(c)5.6.1 Huffman树树建立建立H

27、uffman编码树：编码树：(1)对于给定的对于给定的n个权值个权值w0，w1，wn-1(n2)，构，构成成n棵二叉树的集合棵二叉树的集合T=T0，T1，T2，Tn1，使得每一棵扩充二叉树只具有一个带权为，使得每一棵扩充二叉树只具有一个带权为wi的的根结点。根结点。(2)构造一棵新的扩充二叉树，在集合构造一棵新的扩充二叉树，在集合T中找出两个中找出两个权值最小的树作为新树根结点的左右子树，把新权值最小的树作为新树根结点的左右子树，把新树根结点的权值赋为其左右子树根结点的和。树根结点的权值赋为其左右子树根结点的和。(3)在集合在集合T中删除这两棵树，并把得到的新扩充二中删除这两棵树，并把得到的新

28、扩充二叉树加入到集合中。叉树加入到集合中。(4)重复步骤重复步骤(2)、(3)的操作，直到集合的操作，直到集合T中只含有一中只含有一棵树为止。棵树为止。5.6.1 Huffman树图5.19 Huffman树的构造过程 2 3 6 4 9 5 15 2 3 6 42364哈夫曼树的性质n1、哈夫曼树只有度为哈夫曼树只有度为0和和2的结点，无度为的结点，无度为1的结点；的结点；n2、权值大的结点离根结点近；、权值大的结点离根结点近；n3、n个叶子的哈夫曼树的形态一般不唯一，个叶子的哈夫曼树的形态一般不唯一，但但WPL是相同的；是相同的；n4、n个叶子的哈夫曼树共有个叶子的哈夫曼树共有2n-1个结

29、点。个结点。例例 w=5,29,7,8,14,23,3,1151429 7823 3111429 7823 1153887151429235381111538191429238715115381929 23148715292914871529115381923421153819234229148715295811538192342291487152958100哈夫曼树的形态是不唯一的哈夫曼树的形态是不唯一的2022-11-635自测题自测题 n给定权值给定权值7，6，3，32，5，26，12，9，构造相，构造相应的哈夫曼树，并计算其带权路径长度。为使结应的哈夫曼树，并计算其带权路径长度。为使结

30、果答案唯一，请用果答案唯一，请用左结点的值小于等于右结点的左结点的值小于等于右结点的值值来构造哈夫曼树。来构造哈夫曼树。HuffmanHuffman树结点类定义树结点类定义（略）（略）template class HuffmanTreeNode friend class HuffmanTree;private:T info;HuffmanTreeNode*parent;HuffmanTreeNode*left;HuffmanTreeNode*right;public:HuffmanTreeNode();HuffmanTreeNode*leftchild()return left;Huffman

31、TreeNode*rightchild()return right;bool operator (HuffmanTreeNode&HN)return info HN.info;/注意要重载运算符bool operator (HuffmanTreeNode&HN)return info HN.info;bool operator=(HuffmanTreeNode&HN)return info=HN.info;HuffmanHuffman树的类定义树的类定义（略）（略）templateclass HuffmanTree private:HuffmanTreeNode*root;/Huffman树的

32、根结点树的根结点void MergeTree(HuffmanTreeNode&ht1,HuffmanTreeNode&ht2,HuffmanTreeNode*parent);/把以把以ht1和和ht2为根的两棵为根的两棵Huffman树合并成一棵以树合并成一棵以parent为根的二叉树为根的二叉树void DeleteTree(HuffmanTreeNode*root);/删除删除Huffman树或其子树树或其子树public:HuffmanTree(T weight,int n);/构造构造Huffman树，参数树，参数weight为权值数组，为权值数组，n为数组长度为数组长度virtual

33、 HuffmanTree()DeleteTree(root);/析构函数析构函数;析构函数析构函数（略）（略）template void HuffmanTree:DeleteTree(HuffmanTreeNode*root)if(root)DeleteTree(root-left);DeleteTree(root-right);delete root;templateHuffmanTree:HuffmanTree(T weight,int n)MinHeap HuffmanTreeNode heap(n);/最小值堆最小值堆HuffmanTreeNode*parent,firstchild,

34、secondchild;HuffmanTreeNode*NodeList=new HuffmanTreeNoden;for(int i=0;i n;i+)/初始化初始化NodeListi.info=weighti;NodeListi.parent=NodeListi.left=NodeListi.right=NULL;heap.Insert(NodeListi);/向堆中添加元素向堆中添加元素HuffmanHuffman树的构造树的构造（略）（略）for(i=0;i n-1;i+)/通过通过n-1次合并建立次合并建立Huffman树树 parent=new HuffmanTreeNode;/申

35、请一个分支结点申请一个分支结点firstchild=heap.RemoveMin();/选择权值最小的结点选择权值最小的结点secondchild=heap.RemoveMin();/选择权值次小的结点选择权值次小的结点MergeTree(firstchild,secondchild,parent);/将权值最小的两棵树合并到将权值最小的两棵树合并到parent树树heap.Insert(*parent);/把把parent插入到堆中去插入到堆中去root=parent;/Huffman树的根结点赋为树的根结点赋为parentdelete NodeList;HuffmanHuffman树的构造

36、树的构造(续续)（略）（略）合并函数合并函数（略）（略）template void HuffmanTree:MergeTree(HuffmanTreeNode&ht1,HuffmanTreeNode&ht2,HuffmanTreeNode*parent)HuffmanTreeNode*l=new HuffmanTreeNode();HuffmanTreeNode*r=new HuffmanTreeNode();*l=ht1;*r=ht2;parent-parent=NULL;parent-left=l;parent-right=r;parent-info=ht1.info+ht2.info;l

37、-parent=r-parent=parent;/指向父节点哈夫曼编码n哈夫曼编码的由来哈夫曼编码的由来n1、通讯使用电报码；、通讯使用电报码；n2、如何避免一个编码是另一个编码的前、如何避免一个编码是另一个编码的前缀；缀；哈夫曼编码哈夫曼编码 n字符串：字符串：“CATCATTCPPCTCAC”,n编码：编码：C:00 A:01 T:10 P:11，则报文为：则报文为：“000110000110100011110010000100”n考虑到出现频率，考虑到出现频率，C:0 A:00 T:1 P:01 则报文为：则报文为：“00010001100101010000”。n但：译码有困难：但：译码

38、有困难：“0001”有多种译法：有多种译法：CCP,AP,CAT,u前缀码前缀码哈夫曼编码哈夫曼编码n前缀码前缀码*指的是，任何一个字符的编码都指的是，任何一个字符的编码都不不是是前一字符集中另一个字符的编码的前缀。前一字符集中另一个字符的编码的前缀。n用二叉树可以构造前缀码；用二叉树可以构造前缀码；n哈夫曼树可以构造最短的前缀码（哈夫曼树可以构造最短的前缀码（哈夫曼编码）哈夫曼编码）5.6.2 Huffman编码编码 nHuffman树的一个重要应用就是解决数据通信中的二进制编码树的一个重要应用就是解决数据通信中的二进制编码问题。问题。设设D=d0，dn1，W=W0，Wn1D为需要编码的字符

39、集合，为需要编码的字符集合，W为为D中各字符出现的频率，要对中各字符出现的频率，要对D里的字符进行二进制编码，使得：里的字符进行二进制编码，使得：最小，其中，最小，其中，li为第为第i个字符的二进制编码长度个字符的二进制编码长度。n由此可见，设计电文总长度最短的编码问题就转化成了设计字由此可见，设计电文总长度最短的编码问题就转化成了设计字符出现频率作为外部结点权值的符出现频率作为外部结点权值的Huffman树的问题。树的问题。10niiiwl根据字符出现频率编码，使电文总长最短根据字符出现频率编码，使电文总长最短例例 要传输的字符集要传输的字符集 D=a,b,c,d,e 字符出现字符出现次数次

40、数w=12,40,15,8,25HuffmanHuffman编码：数据通信用的二进制编码编码：数据通信用的二进制编码字符字符概率概率编码编码1编码编码2编码编码3a120000001111b40001110c1501001110d80110111110e251001010编码编码1：3*(12+40+15+8+25)=300编码编码2:3*(12+8)+2*(40+15+25)=220编码编码3:4*(12+8)+3*15+2*25+40=1905.6.2 Huffman编码编码 nHuffman编码过程如下：编码过程如下：q用用d0，d1，dn1作为外部结点构造具有最小带权作为外部结点构造具

41、有最小带权外部路径长度的扩充二叉树外部路径长度的扩充二叉树q把从每个结点引向其把从每个结点引向其左子结点的边标上号码左子结点的边标上号码0，从每个，从每个结点引向其结点引向其右子结点的边标上号码右子结点的边标上号码1q从根结点到每个叶结点路径上的编号连接起来就是这从根结点到每个叶结点路径上的编号连接起来就是这个外部结点所代表字符的编码。得到的二进制前缀码个外部结点所代表字符的编码。得到的二进制前缀码就称作就称作Huffman编码编码图图5.20 Huffman编码示例编码示例5.6.2 Huffman编码编码例如，在一个数据通信系统中例如，在一个数据通信系统中使用的字符是使用的字符是a，b，c

42、，d，e，f，g，对应的频率分别为，对应的频率分别为15，2，6，5，20，10，18各字符的二进制编码为：各字符的二进制编码为：a：00 b：11110 c：1110 d：11111 e：10 f：110 g：0172576613bdcaefg10232043331518000000111111ACBDEF160000111364125736912G0112801字符字符 出现次数出现次数 编码编码A 3 100B 6 11C 4 011D 2 1011E 1 1010F 5 000G 7 01例子：例子：5.6.2 Huffman编码编码n用用Huffman算法构造出的扩充二叉树给出了各字

43、符的算法构造出的扩充二叉树给出了各字符的编编码码，同时也用来，同时也用来译码译码n从二叉树的根开始，把二进制编码每一位的值与从二叉树的根开始，把二进制编码每一位的值与Huffman树边上标记的树边上标记的0，1相匹配，确定选择左分支还相匹配，确定选择左分支还是右分支，直至确定一条到达树叶的路径。一旦到达树是右分支，直至确定一条到达树叶的路径。一旦到达树叶，就译出了一个字符。然后继续用这棵二叉树继续译叶，就译出了一个字符。然后继续用这棵二叉树继续译出其它二进制编码出其它二进制编码 n编码：从叶子结点编码：从叶子结点向上向上构造构造Huffman的过程，边上要标识的过程，边上要标识0，1n译码：从

44、根结点译码：从根结点向下向下直到叶子结点读取路径上的数字直到叶子结点读取路径上的数字2022-11-652算法举例算法举例 哈夫曼树哈夫曼树 设计一个递归算法求一个设计一个递归算法求一个哈夫曼树的带权路径长哈夫曼树的带权路径长度度。二叉树的每个结点有三个域。二叉树的每个结点有三个域:lchild,rchild 和和element。算法可用。算法可用PASCAL语言或语言或C语言描述，要求语言描述，要求写出类型说明。写出类型说明。【南京邮电学院南京邮电学院2002五五(14分分)】2022-11-653求哈夫曼求哈夫曼 树的带权路径长度树的带权路径长度nvoid HuffmanWPl(BiTre

45、e t)n 求哈夫曼树的带权路径长度求哈夫曼树的带权路径长度n if(t)n HuffmanWPl(t-lchild);HuffmanWPl(t-rchild);n if(!t-lchild&!t-rchild)n h=height(t);求叶子结点高度，前面有算法，不再重写求叶子结点高度，前面有算法，不再重写 n wpl+=t-element*h;wpl为全局变量，初值为为全局变量，初值为0.0 n if n n 5.7 二叉树知识点总结二叉树知识点总结n二叉树的概念及主要性质二叉树的概念及主要性质 n二叉树的抽象数据类型及周游方法二叉树的抽象数据类型及周游方法 n二叉树的存储结构二叉树的存储结构 n二叉搜索树及其应用二叉搜索树及其应用n堆的概念、性质与构造堆的概念、性质与构造n Huffman树的主要思想与具体应用树的主要思想与具体应用