《数据结构第部分》由会员分享，可在线阅读，更多相关《数据结构第部分（260页珍藏版）》请在金锄头文库上搜索。
1、第二部分第二部分 树树树形结构式处理具有层次关系的数据元素树形结构式处理具有层次关系的数据元素这部分将介绍这部分将介绍树树二叉树二叉树堆堆1第五章第五章 树树树的概念树的概念二叉树二叉树表达式树表达式树哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码树和森林树和森林2树的概念树的概念树的定义树的定义树的术语树的术语树的运算树的运算3树的定义树的定义树是树是n (n1) n (n1) 个结点的有限集合个结点的有限集合T T，并且满足：并且满足： (1)(1)有一个被称之为根有一个被称之为根(root)(root)的结点的结点 (2)(2)其余的结点可分为其余的结点可分为m(m0)m(m0)个互不相交的个
2、互不相交的集合集合T Tl l，T T2 2，T Tm m，这些集合本身也是一棵这些集合本身也是一棵树，并称它们为根结点树，并称它们为根结点的子树的子树( (SubreeSubree) )。每棵每棵子树同样有自己的根结子树同样有自己的根结点。点。ADCBFEGJIHLKM4树的概念树的概念树的定义树的定义树的术语树的术语树的运算树的运算5根结点、叶结点、内部节点根结点、叶结点、内部节点结点的度和树的度结点的度和树的度儿子结点儿子结点父亲结点父亲结点兄弟结点兄弟结点祖先结点祖先结点子孙结点子孙结点结点所处层次结点所处层次树的高度树的高度有序树有序树无序树无序树森林森林 树的术语树的术语ADCBF
3、EGJIHLKM6树的概念树的概念树的定义树的定义树的术语树的术语树的运算树的运算7树的常用操作树的常用操作建树建树create()create()：创建一棵空树；：创建一棵空树；清空清空clear()clear()：删除树中的所有结点；：删除树中的所有结点；判空判空IsEmptyIsEmpty()()：判别是否为空树；：判别是否为空树；找根结点找根结点root()root()：找出树的根结点。如果树是空：找出树的根结点。如果树是空树，则返回一个特殊的标记；树，则返回一个特殊的标记；找父结点找父结点parent(xparent(x) )：找出结点：找出结点x x的父结点；的父结点；找子结点找子
4、结点child(x,ichild(x,i) )：找结点：找结点x x的第的第i i个子结点；个子结点；剪枝剪枝delete(x,i)delete(x,i)：删除结点：删除结点x x的第的第i i棵子树；棵子树；构建一棵树构建一棵树MakeTreeMakeTree（x,T1, T2, ,x,T1, T2, ,TnTn）：）：构建一棵以构建一棵以x x为根结点，以为根结点，以T1, T2, ,T1, T2, ,TnTn为第为第i i棵子树的树；棵子树的树；遍历遍历traverse()traverse()：访问树上的每一个结点。：访问树上的每一个结点。 8第五章第五章 树树树的概念树的概念二叉树二叉
5、树表达式树表达式树哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码树和森林树和森林9二叉树二叉树二叉树的概念二叉树的概念二叉树的性质二叉树的性质二叉树的基本运算二叉树的基本运算二叉树的遍历二叉树的遍历二叉树的实现二叉树的实现二叉树类二叉树类二叉树遍历的非递归实现二叉树遍历的非递归实现10二叉树二叉树的定义的定义 二叉树（二叉树（Binary TreeBinary Tree）是结点的有限集合，是结点的有限集合，它或者为空，或者由一个根结点及两棵互不它或者为空，或者由一个根结点及两棵互不相交的左、右子树构成，而其左、右子树又相交的左、右子树构成，而其左、右子树又都是二叉树。都是二叉树。 注意：二叉树必须严
6、格区分左右子树。即使只有一棵子注意：二叉树必须严格区分左右子树。即使只有一棵子树，也要说明它是左子树还是右子树。交换一棵二叉树树，也要说明它是左子树还是右子树。交换一棵二叉树的左右子树后得到的是另一棵二叉树。的左右子树后得到的是另一棵二叉树。11二叉树的基本形态二叉树的基本形态 (a)空二叉树空二叉树 (b)根和空的根和空的左右子树左右子树 (c)根和左右子树根和左右子树 (d)根和左子树根和左子树 (e)根和右子树根和右子树左左子子树树右右子子树树左左子子树树右右子子树树12结点总数为结点总数为3 的所有二叉的所有二叉树的不同形状树的不同形状13l一棵高度为一棵高度为k k并具有并具有2 2
7、k k1 1个结点的二叉个结点的二叉树称为满二叉树。树称为满二叉树。l一棵二叉树中任意一层的结点个数都达一棵二叉树中任意一层的结点个数都达到了最大值到了最大值满二叉树满二叉树14DCGEFBAHKIJOLNM满二叉树实例满二叉树实例不是满二叉树不是满二叉树DCGEFBAHIJ15完全二叉树完全二叉树在在满满二二叉叉树树的的最最底底层层自自右右至至左左依依次次( (注注意意：不不能能跳跳过过任任何何一一个个结结点点) )去去掉掉若若干干个个结结点点得得到到的的二二叉叉树树也也被被称称之之为为完完全全二二叉叉树树。满满二二叉叉树树一一定定是是完完全全二二叉叉树树，但但完全二叉树不一定是满二叉树。完
8、全二叉树不一定是满二叉树。完全二叉树的特点是：完全二叉树的特点是： （1 1）所有的叶结点都出现在最低的两层上。）所有的叶结点都出现在最低的两层上。 （2 2）对任一结点，如果其右子树的高度为）对任一结点，如果其右子树的高度为k k，则其则其左子树的高度为左子树的高度为k k或或k k1 1。 1601234完全二叉树完全二叉树非完全二叉树非完全二叉树DCGEFBAHIJ17二叉树二叉树二叉树的概念二叉树的概念二叉树的性质二叉树的性质二叉树的基本运算二叉树的基本运算二叉树的遍历二叉树的遍历二叉树的实现二叉树的实现二叉树类二叉树类二叉树遍历的非递归实现二叉树遍历的非递归实现18二叉树的性质二叉树
9、的性质1 1 一棵非空二叉树的第一棵非空二叉树的第 i 层上最多有层上最多有2i-1个结点（个结点（i1）。）。BCDEFLA1层：结点个数层：结点个数 21-1=1个个2层：结点个数层：结点个数 22-1=2 个个3层：结点个数层：结点个数 23-1=4 个个19证明：当证明：当i=1i=1时，只有一个根结点，时，只有一个根结点，2 2i-1i-1=2=20 0 =1, =1,命题成立。命题成立。 假定对于所有的假定对于所有的j j，1jk,1jk,命题成立。命题成立。 即第即第j j层上至多有层上至多有2 2j-1j-1个结点。个结点。 由归纳假设可知，第由归纳假设可知，第j = kj =
10、 k层上至多有层上至多有2 2k-1k-1个结点。个结点。 若要使得第若要使得第k+1k+1层上结点数为最多，那么，第层上结点数为最多，那么，第k k层上层上 的每个结点都必须有二个儿子结点。的每个结点都必须有二个儿子结点。 因此，第因此，第k+1k+1层上结点数最多为为第层上结点数最多为为第k k层上最多结点数层上最多结点数 的二倍，即：的二倍，即：2 22 2k-1k-12 2k+1-1k+1-12 2k k。 所以，命题成立。所以，命题成立。 20二叉树的性质二叉树的性质2 2 一一棵棵高高度度为为k k的的二二叉叉树树，最最多多具具有有2 2k k1 1个个结结点点。证明：这棵二叉树中
11、的每一层的结点个数必须最多。证明：这棵二叉树中的每一层的结点个数必须最多。 根据性质根据性质1 1，第，第i i层的结点数最多为等于层的结点数最多为等于2 2i-1i-1， 因此结点个数因此结点个数 N N 最多为：最多为：21对对于于一一棵棵非非空空二二叉叉树树，如如果果叶叶子子结结点点数数为为n n0 0，度数为度数为2 2的结点数为的结点数为n n2 2，则有则有: : n n0 0n n2 21 1 成立。成立。 二叉树的性质二叉树的性质3 322证明：设证明：设n n为二叉树的结点总数，为二叉树的结点总数，n n1 1为二叉树中度数为为二叉树中度数为 1 1的结点数。的结点数。 二叉
12、树中所有结点均小于或等于二叉树中所有结点均小于或等于2 2，所以有：，所以有： n n n n0 0 n n1 1 n n2 2 再看二叉树中的树枝再看二叉树中的树枝( (父结点和儿子结点之间的父结点和儿子结点之间的 线段线段) )总数。总数。 在二叉树中，除根结点外，其余结点都有唯一在二叉树中，除根结点外，其余结点都有唯一 的一个树枝进入本结点。的一个树枝进入本结点。性质性质3证明证明23设设B B为二叉树中的树枝数，那么有下式成立：为二叉树中的树枝数，那么有下式成立： B B n n1 1 这些树枝都是由度为这些树枝都是由度为1 1和度为和度为2 2的结点发出的，的结点发出的，一个度为一个
13、度为1 1的结点发出一个树枝，一个度为的结点发出一个树枝，一个度为2 2的结点的结点发出两个树枝，所以有：发出两个树枝，所以有： B B n n1 12n2n2 2 因此，因此， n n0 0n n2 21 124二叉树的性质二叉树的性质4 4具有具有n n个结点的完全二叉树的高度个结点的完全二叉树的高度 k = k = log2nlog2n + 1 + 1 证明证明 根据完全二叉树的定义和性质根据完全二叉树的定义和性质2可知，高度为可知，高度为k的的 完全二叉树的第一层到第完全二叉树的第一层到第k-1层具有最多的结点个层具有最多的结点个 数，总数为数，总数为 2k-1- 1个，第个，第k层至
14、少具有一个结点，层至少具有一个结点， 至多有至多有2k-1个结点。因此，个结点。因此， 2k-1 1 n 2k - 1 即即 2k-1 n 2k 对不等式取对数，有对不等式取对数，有 k -1 log2n 1i1，则其父亲结点的编号为，则其父亲结点的编号为 i/2i/2 。（2 2）如果）如果2i n2i n，则编号为，则编号为i i的结点为叶子结点，的结点为叶子结点，没有儿子；否则，其左儿子的编号为没有儿子；否则，其左儿子的编号为2i2i。（3 3）如果）如果2i + 1 n2i + 1 n，则编号为，则编号为i i的结点无右儿子；的结点无右儿子；否则，其右儿子的编号为否则，其右儿子的编号为
15、2i+12i+1。 26BDEFLAPSQRU121110987654321C27二叉树二叉树二叉树的概念二叉树的概念二叉树的性质二叉树的性质二叉树的基本运算二叉树的基本运算二叉树的遍历二叉树的遍历二叉树的实现二叉树的实现二叉树类二叉树类二叉树遍历的非递归实现二叉树遍历的非递归实现28二叉树常用操作二叉树常用操作建树建树create()create()：创建一棵空的二叉树；：创建一棵空的二叉树；清空清空clear()clear()：删除二叉树中的所有结点；：删除二叉树中的所有结点；判空判空IsEmptyIsEmpty()()：判别二叉树是否为空树；：判别二叉树是否为空树；找根结点找根结点roo
16、t()root()：找出二叉树的根结点。：找出二叉树的根结点。找父结点找父结点parent(xparent(x) )：找出结点：找出结点x x的父结点；的父结点；找左孩子找左孩子lchild(xlchild(x) )：找结点：找结点x x的左孩子结点；的左孩子结点；找右孩子找右孩子rchild(xrchild(x) )：找结点：找结点x x的右孩子结点；的右孩子结点；删除左子树删除左子树delLeft(x)delLeft(x)：删除结点：删除结点x x的左子树；的左子树；删除右子树删除右子树delRight(x)delRight(x)：删除结点：删除结点x x的右子树；的右子树；构建一棵树构建
17、一棵树MakeTreeMakeTree（x,TLx,TL, TR, TR）：构建一棵以）：构建一棵以x x为根结点，以为根结点，以TLTL， TRTR为左右子树的二叉树；为左右子树的二叉树；遍历遍历traverse()traverse()：访问二叉树上的每一个结点。：访问二叉树上的每一个结点。29二叉树二叉树二叉树的概念二叉树的概念二叉树的性质二叉树的性质二叉树的基本运算二叉树的基本运算二叉树的遍历二叉树的遍历二叉树的实现二叉树的实现二叉树类二叉树类二叉树遍历的非递归实现二叉树遍历的非递归实现30二叉树的遍历二叉树的遍历二叉树的遍历讨论的是如何访问到树上的二叉树的遍历讨论的是如何访问到树上的每
18、一个结点每一个结点在线性表中，我们可以沿着后继链访问到在线性表中，我们可以沿着后继链访问到所有结点。而二叉树是有分叉的，因此在所有结点。而二叉树是有分叉的，因此在分叉处必须确定下一个要访问的节点：是分叉处必须确定下一个要访问的节点：是根结点、左结点还是右结点根结点、左结点还是右结点根据不同的选择，有三种遍历的方法：前根据不同的选择，有三种遍历的方法：前序、中序和后序序、中序和后序31前序遍历前序遍历如果二叉树为空，则操作为空如果二叉树为空，则操作为空否则否则访问根结点访问根结点前序遍历左子树前序遍历左子树前序遍历右子树前序遍历右子树32中序遍历中序遍历如果二叉树为空，则操作为空如果二叉树为空，
19、则操作为空否则否则中序遍历左子树中序遍历左子树访问根结点访问根结点中序遍历右子树中序遍历右子树33后序遍历后序遍历如果二叉树为空，则操作为空如果二叉树为空，则操作为空否则否则后序遍历左子树后序遍历左子树后序遍历右子树后序遍历右子树访问根结点访问根结点34前序：前序：A、L、B、E、 C、D、W、X中序：中序：B、L、E、A、 C、W、X、D后序：后序：B、E、L、X、 W、D、C、ABCDELAXW35前序前序 中序中序 唯一确定一唯一确定一棵二叉树棵二叉树 前序前序: A、B、D、E、F、C 中序中序: D、B、E、F、A、C 前序前序: B、D、E、F 中序中序: D、B、E、F 前序前序
20、: E、F 中序中序: E、FD、B、E、FA CACBABCD E、FEFABCD36同理，由二叉树的后序序列和中序序列同样可同理，由二叉树的后序序列和中序序列同样可以唯一地确定一棵二叉树以唯一地确定一棵二叉树 但是，已知二叉树的前序遍历序列和后序遍历但是，已知二叉树的前序遍历序列和后序遍历序列却无法确定一棵二叉树。比如：已知一棵序列却无法确定一棵二叉树。比如：已知一棵二叉树的前序遍历序列为二叉树的前序遍历序列为A A、B B，后序遍历序列，后序遍历序列为为B B、A A，我们虽然可以很容易地得知结点，我们虽然可以很容易地得知结点A A为为根结点，但是无法确定结点根结点，但是无法确定结点B
21、B是结点是结点A A的左儿子的左儿子还是右儿子，因为还是右儿子，因为B B无论是结点无论是结点A A的右儿子还是的右儿子还是左儿子都是符合已知条件的。左儿子都是符合已知条件的。 37二叉树二叉树二叉树的概念二叉树的概念二叉树的性质二叉树的性质二叉树的基本运算二叉树的基本运算二叉树的遍历二叉树的遍历二叉树的实现二叉树的实现二叉树类二叉树类二叉树遍历的非递归实现二叉树遍历的非递归实现38二叉树的实现二叉树的实现顺序实现顺序实现链接实现链接实现39完全二叉树完全二叉树的顺序存储的顺序存储 BCDEFLAPSQRU212111098765431根据编号性质，根据编号性质，可以省略左右可以省略左右孩子字
22、段孩子字段01A2L3B4B5E6F7D8P9Q10R11S12U40普通二叉树的顺序存储普通二叉树的顺序存储 DBAHI将普通的树修将普通的树修补成完全二叉补成完全二叉树树01A2B3 4D5 6 7 8H9I41右单支树的实例右单支树的实例 CGA01A23C C45 6 7G G 42顺序实现的特点顺序实现的特点存储空间的浪费。存储空间的浪费。一般只用于一些特殊的场合，如静态的一般只用于一些特殊的场合，如静态的并且结点个数已知的完全二叉树或接近并且结点个数已知的完全二叉树或接近完全二叉树的二叉树。完全二叉树的二叉树。 43二叉树的实现二叉树的实现顺序实现顺序实现链接实现链接实现44链链接
23、接存储结构存储结构ABCDEFGHIL标准形式：（二叉链表）标准形式：（二叉链表）广义标准形式：（三叉链表）广义标准形式：（三叉链表）LEFTDATARIGHTLEFTDATARIGHT PARENT45标准形式的实例标准形式的实例 AL/C/ B/E/D/W/XrootALCXEBWD46广义标准形式的实例广义标准形式的实例 ALCXEBWDArootLCE B DW X 47二叉树基本运算的实现二叉树基本运算的实现 由于二叉树是一个递归的结构，因此二叉树中的许由于二叉树是一个递归的结构，因此二叉树中的许多运算的实现都是基于递归函数。多运算的实现都是基于递归函数。create()create
24、()：将指向根结点的指针设为空指针就可以：将指向根结点的指针设为空指针就可以了，即了，即root = NULLroot = NULL。 isEmptyisEmpty()()：只需要判别：只需要判别rootroot即可。如果即可。如果rootroot等于等于空指针，返回空指针，返回truetrue，否则，返回，否则，返回falsefalse。root()root()：返回：返回rootroot指向的结点的数据部分。如果二指向的结点的数据部分。如果二叉树是空树，则返回一个特殊的标记。叉树是空树，则返回一个特殊的标记。48clear() 从递归的观点看，一棵二叉树由三部分组从递归的观点看，一棵二叉树
25、由三部分组成：根结点、左子树、右子树。删除一棵成：根结点、左子树、右子树。删除一棵二叉树就是删除这三个部分。二叉树就是删除这三个部分。根结点的删除很简单，只要回收根结点的根结点的删除很简单，只要回收根结点的空间，把指向根结点的指针设为空指针。空间，把指向根结点的指针设为空指针。如何删除左子树和右子树呢？记住左子树如何删除左子树和右子树呢？记住左子树也是一棵二叉树，右子树也是一棵二叉树，也是一棵二叉树，右子树也是一棵二叉树，左右子树的删除和整棵树的删除过程是一左右子树的删除和整棵树的删除过程是一样的。样的。 49if （左子树非空）（左子树非空） 递归删除左子树；递归删除左子树；if （右子树非
26、空）（右子树非空） 递归删除右子树；递归删除右子树；delete root指向的结点；指向的结点；root = NULL；50parent(xparent(x) )：在二叉链表的实现中一般不实：在二叉链表的实现中一般不实现这个操作现这个操作lchild(xlchild(x) )：返回结点：返回结点x x的的leftleft值值rchild(xrchild(x) )：返回结点：返回结点x x的的rightright值值delLeft(x)delLeft(x)：对左子树调用对左子树调用clearclear函数删除函数删除左子树，然后将结点左子树，然后将结点x x的的leftleft置为置为NULL
27、NULL。delRight(x)delRight(x)：对右子树调用：对右子树调用clearclear函数删除函数删除右子树，然后将结点右子树，然后将结点x x的的rightright置为置为NULLNULL。makeTreemakeTree（x,TLx,TL, TR, TR）：为）：为x x申请一个结点，申请一个结点，让它的让它的leftleft指向指向TLTL的根结点，的根结点，rightright指向指向TRTR的根结点。的根结点。 51二叉树的遍历二叉树的遍历 前序：前序：访问根结点；访问根结点；if if （左子树非空）（左子树非空） 前序遍历左子树；前序遍历左子树；if if （右
28、子树非空）前序遍历右子树；（右子树非空）前序遍历右子树；其他两种遍历只要调整一下次序即可。其他两种遍历只要调整一下次序即可。52二叉树二叉树二叉树的概念二叉树的概念二叉树的性质二叉树的性质二叉树的基本运算二叉树的基本运算二叉树的遍历二叉树的遍历二叉树的实现二叉树的实现二叉树类二叉树类二叉树遍历的非递归实现二叉树遍历的非递归实现53二叉树类二叉树类由于二叉树的顺序实现仅用于一些特殊由于二叉树的顺序实现仅用于一些特殊的场合。大多数情况下，二叉树都是用的场合。大多数情况下，二叉树都是用二叉链表实现，所以仅介绍用二叉链表二叉链表实现，所以仅介绍用二叉链表实现的二叉树类。实现的二叉树类。54二叉树类的设
29、计二叉树类的设计标准的链接存储由两个类组成：结点类和标准的链接存储由两个类组成：结点类和树类。树类。和线性表的实现类似，这个结点类是树类和线性表的实现类似，这个结点类是树类专用的，因此可作为树类的私有内嵌类。专用的，因此可作为树类的私有内嵌类。55结点类结点类Node的设计的设计存储和处理树上每一个结点的类。存储和处理树上每一个结点的类。数据成员包括：结点的数据及左右孩子的数据成员包括：结点的数据及左右孩子的指针。指针。结点的操作包括：结点的操作包括：构造和析构构造和析构56二叉树类的设计二叉树类的设计树的存储：存储指向根结点的指针树的存储：存储指向根结点的指针树的操作：树的操作：树的标准操作
30、树的标准操作增加了一个建树的函数增加了一个建树的函数57递归函数的设计递归函数的设计对于二叉树类的用户来说，他并不需要知道这对于二叉树类的用户来说，他并不需要知道这些操作时用递归函数实现的。些操作时用递归函数实现的。对用户来说，调用这些函数并不需要参数对用户来说，调用这些函数并不需要参数但递归函数必须有一个控制递归终止的参数但递归函数必须有一个控制递归终止的参数设计时，我们将用户需要的函数原型作为公有设计时，我们将用户需要的函数原型作为公有的成员函数。每个公有成员函数对应一个私有的成员函数。每个公有成员函数对应一个私有的、带递归参数的成员函数。公有函数调用私的、带递归参数的成员函数。公有函数调
31、用私有函数完成相应的功能。有函数完成相应的功能。58二叉树类的定义二叉树类的定义 template class BinaryTree private: struct Node Node *left , *right ; / 结点的左、右儿子的地址结点的左、右儿子的地址 Type data; / 结点的数据信息结点的数据信息 Node() : left(NULL), right(NULL) Node(Type item, Node *L = NULL, Node * R =NULL ): data(item), left(L), right(R) Node() ; Node *root; / 二
32、叉树的根结点。二叉树的根结点。 59public: BinaryTree() : root( NULL) / 构造空二叉树构造空二叉树BinaryTree(const Type & value ) root = new Node(value); BinaryTree(Node *p) root = p; BinaryTree() clear(); Type getRoot() const return root-data;Type getLeft() const return root-left-data;Type getRight() const return root-right-data
33、;60void makeTree(const Type &x, BinaryTree <, BinaryTree &rt) root = new Node( x, lt.root, rt.root); lt.root = NULL; rt.root = NULL; void delLeft() BinaryTree tmp = root-left; root-left = NULL； tmp.clear(); void delRight() BinaryTree tmp = root-right; root-right = NULL; tmp.clear(); 61 bool isEmpt
34、y () const return root = NULL; void clear() if (root != NULL) clear(root); root = NULL; int size() const return size(root); int height() const return height(root); void preOrder() const； void postOrder() const； void midOrder() const； void createTree(Type flag);62private: void clear( Node *t ) ； int
35、height( Node *t ) const； int size( Node *t ) const； void preOrder( Node *t ) const； void postOrder( Node *t ) const； void midOrder( Node *t ) const； ; 63求规模操作的实现求规模操作的实现用递归的观点来看，二叉树是由根结点和左用递归的观点来看，二叉树是由根结点和左右子树构成。因此，树的规模应该为：右子树构成。因此，树的规模应该为： 左子树的规模左子树的规模 + + 右子树的规模右子树的规模 + 1+ 1（根）（根）64size () int si
36、ze() const return size(root); int size(Node *t) const if (t = NULL) return 0; return 1 + size(t-left) + size(t-right); 65求高度操作求高度操作的实现的实现用递归的观点来看，二叉树是由根结点用递归的观点来看，二叉树是由根结点和左右子树构成。因此，树的高度应该和左右子树构成。因此，树的高度应该为：为：1 1maxmax（左子树高度，右子树高度）（左子树高度，右子树高度）66height()int height() const return height(root); int he
37、ight(Node *t) const if (t = NULL) return 0; else int lt = height(t-left), rt = height(t-right); return 1 + ( (lt rt) ? lt : rt); 67三种遍三种遍历的实现的实现树的遍历本身就是用递归形式描述的，树的遍历本身就是用递归形式描述的，因此用递归函数实现是很自然的因此用递归函数实现是很自然的68preOrder()void preOrder() const if (root != NULL) cout n前序遍历：前序遍历：; preOrder(root); void pre
38、Order(Node *t) const if (t != NULL) cout data left); preOrder(t-right); 69midOrder()void midOrder() const if (root != NULL) cout left); cout data right); 70postOrder() void postOrder() const if (root != NULL) cout left); postOrder(t-right); cout data left != NULL) clear(t-left); if (t-right != NULL)
39、 clear(t-right); delete t; 73创建一棵树创建一棵树创建过程：创建过程：先输入根结点的值，创建根节点先输入根结点的值，创建根节点对已添加到树上的每个结点，依次输入它的两对已添加到树上的每个结点，依次输入它的两个儿子的值。如果没有儿子，则输入一个特定个儿子的值。如果没有儿子，则输入一个特定值值实现工具：实现工具：使用一个队列，将新加入到树中的结点放入队使用一个队列，将新加入到树中的结点放入队列列依次出队。对每个出队的元素输入它的儿子依次出队。对每个出队的元素输入它的儿子74BCDEFLAPSQRU212111098765431队列的变化队列的变化ACLEBCDFEBPD
40、FEQQPDFSRRQPDUSSRQPUUSRQ USR US U 75createTreetemplate void BinaryTree:createTree(Type flag) linkQueue que; Node *tmp; Type x, ldata, rdata; /创建树，输入创建树，输入flag表示空表示空 cout x; root = new Node(x); que.enQueue(root); 76while (!que.isEmpty() tmp = que.deQueue();cout n输入输入 data 的两个儿子的两个儿子( flag ldata rdata
41、;if (ldata != flag) que.enQueue(tmp-left = new Node(ldata);if (rdata != flag) que.enQueue(tmp-right = new Node(rdata);cout create completed!n; 77二叉树类的应用二叉树类的应用创建一棵由整型值组成的二叉树创建一棵由整型值组成的二叉树求高度求高度求规模求规模按前序、中序和后序遍历按前序、中序和后序遍历归并两棵树归并两棵树78int main() BinaryTree tree, tree1(M), tree2; tree.createTree(); cou
42、t 高度为：高度为： tree.height() endl; cout 规模为：规模为： tree.size() endl; tree.PreOrder(); tree.MidOrder(); tree.PostOrder(); 79 tree2.makeTree(Y, tree, tree1); cout endl; cout 高度为：高度为： tree2.height() endl; cout 规模为：规模为： tree2.size() endl; tree2.PreOrder(); tree2.MidOrder(); tree2.PostOrder(); return 0; 80BCDE
43、LAXW执行实例执行实例输入根结点：输入根结点：A输入输入A的两个儿子的两个儿子(表示空结点表示空结点)：LC输入输入L的两个儿子的两个儿子(表示空结点表示空结点)：BE输入输入C的两个儿子的两个儿子(表示空结点表示空结点)：D输入输入B的两个儿子的两个儿子(表示空结点表示空结点)：输入输入E的两个儿子的两个儿子(表示空结点表示空结点)：输入输入D的两个儿子的两个儿子(表示空结点表示空结点)：W输入输入W的两个儿子的两个儿子(表示空结点表示空结点)：X输入输入X的两个儿子的两个儿子(表示空结点表示空结点)： 81高度为：高度为：5规模为：规模为：8前序遍历：前序遍历：A L B E C D W
44、 X中序遍历：中序遍历：B L E A C W X D后序遍历：后序遍历：B E L X W D C A高度为：高度为：6规模为：规模为：10前序遍历：前序遍历：Y A L B E C D W X M中序遍历：中序遍历：B L E A C W X D Y M后序遍历：后序遍历：B E L X W D C A M Y BCDELAXWMY82二叉树二叉树二叉树的概念二叉树的概念二叉树的性质二叉树的性质二叉树的基本运算二叉树的基本运算二叉树的遍历二叉树的遍历二叉树的实现二叉树的实现二叉树类二叉树类二叉树遍历的非递归实现二叉树遍历的非递归实现83二叉树遍历的非递归实现二叉树遍历的非递归实现递归是程序
45、设计中强有力的工具。递归是程序设计中强有力的工具。递归程序结构清晰、明了、美观，递归程序结构清晰、明了、美观，递归程序的弱点：它的时间、空间的效率递归程序的弱点：它的时间、空间的效率比较低。比较低。所以在实际使用中，我们常常希望使用它所以在实际使用中，我们常常希望使用它的非递归版本的非递归版本二叉树的遍历也是如此。尽管二叉树遍历二叉树的遍历也是如此。尽管二叉树遍历的递归函数非常简洁，但有时我们还是希的递归函数非常简洁，但有时我们还是希望使用速度更快的非递归函数。望使用速度更快的非递归函数。84二叉树遍历的非递归实现二叉树遍历的非递归实现前序遍历前序遍历中序遍历中序遍历后序遍历后序遍历85前序遍
46、历的非递归实现前序遍历的非递归实现 前序遍历第一个被访问的结点是根结点，然后前序遍历第一个被访问的结点是根结点，然后访问左子树，最后访问右子树。访问左子树，最后访问右子树。可以设置一个栈，保存将要访问的树的树根。可以设置一个栈，保存将要访问的树的树根。开始时，把二叉树的根结点存入栈中。然后重开始时，把二叉树的根结点存入栈中。然后重复以下过程，直到栈为空：复以下过程，直到栈为空：从栈中取出一个结点，输出根结点的值；从栈中取出一个结点，输出根结点的值；然后把然后把右子树，左子树右子树，左子树放入栈中放入栈中86前序遍历的过程前序遍历的过程BCDELAXWA输出：ALBECDWXLCBECECCDW
47、X87template void BinaryTree:preOrder() const linkStack s; Node *current; cout 前序遍历前序遍历: ; s.push( root ); while ( !s.isEmpty() ) current = s.pop(); cout data; if ( current-right != NULL ) s.push( current-right ); if ( current -left != NULL ) s.push( current-left ); 88二叉树遍历的非递归实现二叉树遍历的非递归实现前序遍历前序遍历中序
48、遍历中序遍历后序遍历后序遍历89中序遍历的非递归实现中序遍历的非递归实现采用一个栈存放要遍历的树的树根采用一个栈存放要遍历的树的树根中序遍历中，先要遍历左子树，接下去才能访中序遍历中，先要遍历左子树，接下去才能访问根结点，因此，当根结点出栈时，我们不能问根结点，因此，当根结点出栈时，我们不能访问它，而要访问它的左子树，此时要把树根访问它，而要访问它的左子树，此时要把树根结点暂存一下。结点暂存一下。存哪里？由于左子树访问完后还要访问根结点，存哪里？由于左子树访问完后还要访问根结点，因此仍可以把它存在栈中，接着左子树也进栈。因此仍可以把它存在栈中，接着左子树也进栈。此时执行出栈操作，出栈的是左子树
49、。左子树此时执行出栈操作，出栈的是左子树。左子树问结束后，再次出栈的是根结点，此时根结点问结束后，再次出栈的是根结点，此时根结点可被访问。根结点访问后，访问右子树，则将可被访问。根结点访问后，访问右子树，则将右子树进栈。右子树进栈。90栈元素的设计栈元素的设计在中序遍历中根结点要进栈两次。在中序遍历中根结点要进栈两次。当要遍历一棵树时，将根结点进栈。当要遍历一棵树时，将根结点进栈。根结点第一次出栈时，它不能被访问，必须重根结点第一次出栈时，它不能被访问，必须重新进栈，并将左子树也进栈，表示接下去要访新进栈，并将左子树也进栈，表示接下去要访问的是左子树。问的是左子树。根结点第二次出栈时，才能被访
50、问，并将右子根结点第二次出栈时，才能被访问，并将右子树进栈，表示右子树可以访问了。树进栈，表示右子树可以访问了。在中序遍历时不仅要记住需要访问哪一棵树，在中序遍历时不仅要记住需要访问哪一棵树，而且还必须记住根结点是在第几次进栈。而且还必须记住根结点是在第几次进栈。91中序遍历的过程中序遍历的过程BCDELAXW0A01LA011BLA111BLA11LA输出：输出：01EABL11EAE1AA0C1CC0D01WD11WDW01XD11XDX1DD92StNode类的定义类的定义 struct StNode Node *node; int TimesPop; StNode ( Node *N
51、= NULL ):node(N), TimesPop(0) ; 93中序遍历的非递归实现中序遍历的非递归实现 template void BinaryTree:midOrder() const linkStack s; StNode current(root); cout 中序遍历中序遍历: ; s.push(current); 94while (!s.isEmpty() current = s.pop(); if ( +current.TimesPop = 2 ) cout data; if ( current.node-right != NULL ) s.push(StNode(curre
52、nt.node-right ); else s.push( current ); if ( current.node-left != NULL ) s.push(StNode(current.node-left) ); 95二叉树遍历的非递归实现二叉树遍历的非递归实现前序遍历前序遍历中序遍历中序遍历后序遍历后序遍历96后序遍历的非递归实现后序遍历的非递归实现将中序遍历的非递归实现的思想进一步延伸，可以将中序遍历的非递归实现的思想进一步延伸，可以得到后序遍历的非递归实现。得到后序遍历的非递归实现。当以后序遍历一棵二叉树时，先将树根进栈，表示当以后序遍历一棵二叉树时，先将树根进栈，表示要遍历这棵树
53、。要遍历这棵树。根结点第一次出栈时，根结点不能访问，应该访问根结点第一次出栈时，根结点不能访问，应该访问左子树。于是，根结点重新入栈，并将左子树也入左子树。于是，根结点重新入栈，并将左子树也入栈。栈。根结点第二次出栈时，根结点还是不能访问，要先根结点第二次出栈时，根结点还是不能访问，要先访问右子树。于是，根结点再次入栈，右子树也入访问右子树。于是，根结点再次入栈，右子树也入栈。栈。当根结点第三次出栈时，表示右子树遍历结束，此当根结点第三次出栈时，表示右子树遍历结束，此时，根结点才能被访问。时，根结点才能被访问。 97后序遍历的过程后序遍历的过程BCDELAXW0A01LA011BLA111BL
54、A211BLA输出：输出：021ELABE121ELAL221ELA21LA02CA12CA98BCDELAXW022DCA0122WDCA02122XWDCA12122XWDCA22122XWDCA2122WDCA222DCA22CA2A输出：输出：BLEXWDCA99后序遍历的非递归实现后序遍历的非递归实现template void BinaryTree:postOrder() const linkStack s;StNode current(root); cout 后序遍历后序遍历: ;s.push(current); 100while (!s.isEmpty() current = s
55、.pop(); if ( +current.TimesPop = 3 ) cout data; continue; s.push( current ); if ( current.TimesPop = 1 ) if ( current.node-left != NULL ) s.push(StNode( current.node-left) ); else if ( current.node -right != NULL ) s.push(StNode( current.node-right ) ); 101第五章第五章 树树树的概念树的概念二叉树二叉树表达式树表达式树哈夫曼树与哈夫曼编码哈夫
56、曼树与哈夫曼编码树和森林树和森林102表达式树表达式树算术表达式可以表示为一棵二叉树，如算术表达式可以表示为一棵二叉树，如: : (4-2)*(10+(4+6)/2)+2 (4-2)*(10+(4+6)/2)+2对这棵树后序遍历可对这棵树后序遍历可 得到结果得到结果设计一个类，设计一个类， 利用表达式树计算由利用表达式树计算由 四则运算组成的表达式四则运算组成的表达式+*+/210+64-422103树的构建过程3*4+5*7*9+8 构建左节点构建左节点33*4+5*7*9+8 构建根节点构建根节点*3*4+5*7*9+8 构建右节点构建右节点43*4+5*7*9+8 构建根节点构建根节点+
57、，原树作为左子树，原树作为左子树+3*45*7*9+8 构建右节点构建右节点5+3*45104*7*9+8 下移到右节点，构建根节点下移到右节点，构建根节点*，原来的右节点作为它的左节点，原来的右节点作为它的左节点+3*45+3*45*7*9+8 构建右节点构建右节点7+3*45*7*9+8 创建根创建根*，原树作为左子树，原树作为左子树+3*45*7*105+8 上移到根。创建根上移到根。创建根+，原树作为左子树，原树作为左子树8 8作为左节点作为左节点9+8 9作为右子树作为右子树8+3*45*7*9+3*45*7*9+3*45*7*9106构建过程总结构建过程总结顺序扫描中缀表达式顺序扫
58、描中缀表达式当扫描到的是运算数：先检查当前的表达式当扫描到的是运算数：先检查当前的表达式树是否存在。如果不存在，则表示扫描到的树是否存在。如果不存在，则表示扫描到的是第一个运算数，将它作为树根。如果树存是第一个运算数，将它作为树根。如果树存在，则将此运算数作为前一运算符的右孩子。在，则将此运算数作为前一运算符的右孩子。如果扫描到的是如果扫描到的是+ +或或- -：将它作为根结点，原：将它作为根结点，原来的树作为它的左子树。来的树作为它的左子树。107构建过程总结构建过程总结 续续如果扫描到的是如果扫描到的是* *或或/ /：则与根结点比较。如：则与根结点比较。如果根结点也是果根结点也是* *或
59、或/ /，则根结点应该先执行，则根结点应该先执行，于是将当前运算符作为根结点，原来的树作于是将当前运算符作为根结点，原来的树作为左子树。如果根结点是为左子树。如果根结点是+ +或或- -，则当前运算，则当前运算符应该先运算，于是将它作为右子树的根，符应该先运算，于是将它作为右子树的根，原来的右子树作为它的左子树。原来的右子树作为它的左子树。在遇到运算数时，如何知道它前面的运算符在遇到运算数时，如何知道它前面的运算符是谁？这只需要判别根结点有没有右孩子。是谁？这只需要判别根结点有没有右孩子。如果没有右孩子，则运算数是根结点的右运如果没有右孩子，则运算数是根结点的右运算数，否则就是根结点右孩子的右
60、运算数。算数，否则就是根结点右孩子的右运算数。108构建过程（括号的处理）构建过程（括号的处理）(4+5)*(8+9)+10 遇到括号，将括号内的子表达式构建一棵子树遇到括号，将括号内的子表达式构建一棵子树 作为整个表达式的一个运算数作为整个表达式的一个运算数4+5*(8+9)+10 *作为根节点，括号内的子树作为左子树作为根节点，括号内的子树作为左子树4+5*(8+9)+10括号内的子表达式构建一棵子括号内的子表达式构建一棵子树作为整棵树的右子树树作为整棵树的右子树4+5*8+9+10 +作为根节点，原树作为左子作为根节点，原树作为左子树，树，10作为右子树作为右子树4+5*8+9+1010
61、9表达式树类的设计表达式树类的设计数据成员：指向树根节点的指针数据成员：指向树根节点的指针公有成员函数：公有成员函数：构造函数：调用构造函数：调用createcreate从表达式构建一棵树从表达式构建一棵树resultresult：计算表达式的结果，用后序遍历过程：计算表达式的结果，用后序遍历过程私有成员函数：私有成员函数：CreateCreate带有递归参数的带有递归参数的resultresult函数函数getTokengetToken：createcreate函数所用的子函数，用于从表达式中函数所用的子函数，用于从表达式中获取一个语法单位获取一个语法单位110结点的设计结点的设计在表达式树
62、中，每个叶子结点保存的是在表达式树中，每个叶子结点保存的是一个运算数，每个非叶结点保存的是一一个运算数，每个非叶结点保存的是一个运算符。个运算符。结点的数据部分应该包括两个部分：结结点的数据部分应该包括两个部分：结点的类型和值。点的类型和值。111calc类的定义类的定义 class calc enum Type DATA, ADD, SUB, MULTI, DIV, OPAREN, CPAREN, EOL ; struct node Type type; int data;node *lchild, *rchild; node(Type t, int d = 0, node *lc = NU
63、LL, node *rc = NULL) type = t; data = d; lchild = lc; rchild = rc;node *root;112public: calc( char *s ) root = create( s ); int result() if ( root = NULL ) return 0; return result( root ); private： node *create( char *&s ); Type getToken( char *&s, int &value ); int result( node *t ); 113私有私有create函
64、数的实现函数的实现 calc:node *calc:create(char *&s)calc:node *p, *root = NULL; Type returnType; int value; while (*s) returnType = getToken(s, value); switch (returnType) case DATA: case OPAREN: if (returnType = DATA) p = new node(DATA, value); else p = create(s); if (root = NULL) root = p; else if (root-rch
65、ild = NULL) root-rchild = p; else root-rchild-rchild = p; break;114 case CPAREN: case EOL: return root; case ADD: case SUB: if (root = NULL) root = new node(returnType,0, p); else root = new node(returnType,0, root); break; case MULTI: case DIV: if (root = NULL) root = new node(returnType,0, p); els
66、e if (root-type = MULTI | root-type = DIV) root = new node(returnType,0, root); else root-rchild = new node (returnType,0, root-rchild); return root;115getTokencalc:Type calc:getToken(char *&s, int &data) char type; while (*s = ) +s; if (*s = 0 & *s = 0 & *s type = DATA) return t-data; num1 = result
67、(t-lchild); num2 = result(t-rchild); switch(t-type) case ADD: t-data = num1 + num2; break;case SUB: t-data = num1 - num2; break;case MULTI: t-data = num1 * num2; break;case DIV: t-data = num1 / num2; return t-data; 118Calc类的应用类的应用int main()calc exp( 2*3+(1 * 2*3+6*6) * (2+3)/5 + 2/2 ); cout exp.resu
68、lt() endl; return 0; 119Calc类的特点类的特点使用时和基于栈实现的使用时和基于栈实现的calc类完全一样类完全一样缺点缺点没有考虑表达式不正确的情况没有考虑表达式不正确的情况没有考虑乘方运算没有考虑乘方运算120第五章第五章 树树树的概念树的概念二叉树二叉树表达式树表达式树哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码树和森林树和森林121字符的机内表示字符的机内表示在计算机中每个字符是用一个编码表示在计算机中每个字符是用一个编码表示大多数编码系统都采用等长编码，如大多数编码系统都采用等长编码，如ASCIIASCII编编码码例如在某段文本中用到了下列字符，括号中是例如在某段
69、文本中用到了下列字符，括号中是它们出现的频率：它们出现的频率：a(10), e(15), i(12), a(10), e(15), i(12), s(3), t(4), s(3), t(4), 空格空格(13), (13), 换行换行(1)(1)。如采用定。如采用定长编码，长编码，7 7个不同的字符至少要用个不同的字符至少要用3 3位编码。位编码。 122字符字符 编码 出出现频率率占用空占用空间（bit）a0001030e0011545i0101236s01139t100412空格空格 1011339换行行 11013总存储量：总存储量：3*（10+15+12+3+4+13+1）= 3*58
70、 = 174 bit 123这个编码可以对应成如下的完全二叉树，左枝为这个编码可以对应成如下的完全二叉树，左枝为0 0，右枝为右枝为1 1aSeit43121510113空格空格换行换行124aSeit43121510113空格空格换行换行很显然，将换行上移一层可以减少存储量很显然，将换行上移一层可以减少存储量不等长编码可以减少存储量！不等长编码可以减少存储量！125前缀编码前缀编码 字符只放在叶结点中字符只放在叶结点中 字符编码可以有不同的长度字符编码可以有不同的长度由于字符只放在叶结点中，所以每个字符由于字符只放在叶结点中，所以每个字符的编码都不可能是其他字符编码的前缀的编码都不可能是其他
71、字符编码的前缀前缀编码可被惟一解码前缀编码可被惟一解码126哈夫曼树哈夫曼树 哈夫曼树是一棵最小代价的二叉树，在这哈夫曼树是一棵最小代价的二叉树，在这棵树上，所有的字符都包含在叶结点上。棵树上，所有的字符都包含在叶结点上。要使得整棵树的代价最小，显然权值大的要使得整棵树的代价最小，显然权值大的叶子应当尽量靠近树根，权值小的叶子可叶子应当尽量靠近树根，权值小的叶子可以适当离树根远一些。以适当离树根远一些。127snltaeispA001E01I10S00000T0001Sp 11nl 00001总共用了总共用了146bit哈夫曼编码哈夫曼编码128哈夫曼算法哈夫曼算法1、给定一个具有给定一个具有
72、n n个权值个权值 w w1 1,w,w2 2, ,w wn n 的结点的集合的结点的集合 F = TF = T1 1,T,T2 2, ,T Tn n 2 2、 初始时，设集合初始时，设集合 A = FA = F。3 3、 执行执行 i = 1 i = 1 至至 n -1 n -1 的循环，在每次循环时执行以下操作的循环，在每次循环时执行以下操作从当前集合中选取权值最小、次最小的两个结点，以这两个结从当前集合中选取权值最小、次最小的两个结点，以这两个结点作为内部结点点作为内部结点 b bi i 的左右儿子，的左右儿子，b bi i 的权值为其左右儿子权值的权值为其左右儿子权值之和。之和。在集合
73、中去除这两个权值最小、次最小的结点，并将内部结点在集合中去除这两个权值最小、次最小的结点，并将内部结点b bI I 加入其中。这样，在集合加入其中。这样，在集合A A中，结点个数便减少了一个。中，结点个数便减少了一个。这样，在经过了这样，在经过了n-1 次循环之后，集合次循环之后，集合A中只剩下了一个结点，中只剩下了一个结点，这个结点就是根结点。这个结点就是根结点。 129a(10), e(15), i(12), s(3), t(4), 空格空格(13), 换行换行(1)。t4S3i12e15a1013空格空格1换行换行t4S3i12e15a1013空格空格1换行换行4t4S3i12e15a1
74、013空格空格1换行换行48130i12e15a1013空格空格18t4S31换行换行48i12e1513空格空格25a1018t4S31换行换行48131i1213空格空格25e1533a1018t4S31换行换行48i1213空格空格2558e1533a1018t4S31换行换行48132哈夫曼编码的生成哈夫曼编码的生成每个字符的编码是根节点到该字符的路径每个字符的编码是根节点到该字符的路径左枝为左枝为0 0，右枝为，右枝为1 1133哈夫曼树类的实现哈夫曼树类的实现为了便于找出一组符号的哈夫曼编码，我们可以定为了便于找出一组符号的哈夫曼编码，我们可以定义一个哈夫曼树类。义一个哈夫曼树类。
75、哈夫曼树类的对象可以接受一组符号以及对应的权哈夫曼树类的对象可以接受一组符号以及对应的权值，并告知每个符号对应的哈夫曼编码。因此，哈值，并告知每个符号对应的哈夫曼编码。因此，哈夫曼树类应该有两个公有的成员函数：夫曼树类应该有两个公有的成员函数：构造函数：接受一组待编码的符号以及它们的权值，构构造函数：接受一组待编码的符号以及它们的权值，构造一棵哈夫曼树。造一棵哈夫曼树。GetCodeGetCode函数根据保存的哈夫曼树为每个叶结点生成哈夫函数根据保存的哈夫曼树为每个叶结点生成哈夫曼编码。曼编码。134哈夫曼树的存储哈夫曼树的存储在哈夫曼树中，每个要编码的元素是一个叶结点，在哈夫曼树中，每个要编
76、码的元素是一个叶结点，其它结点都是度数为其它结点都是度数为2 2的节点的节点一旦给定了要编码的元素个数，由一旦给定了要编码的元素个数，由n n0 0n n2 21 1可知哈可知哈夫曼树的大小为夫曼树的大小为2n-12n-1哈夫曼树可以用一个大小为哈夫曼树可以用一个大小为2n2n的数组来存储。的数组来存储。0 0节节点不用，根存放在节点点不用，根存放在节点1 1。叶结点依次放在。叶结点依次放在n+1n+1到到2n2n的位置的位置每个数组元素保存的信息：结点的数据、权值和父每个数组元素保存的信息：结点的数据、权值和父结点和左右孩子的位置结点和左右孩子的位置135值值aeistsp nl权权58 3
77、3 25 18 8410 15 12 3413 1父父112454236536左左2495610右右3812 711 13012345678910 11 12 13i1213空格空格2558e1533a1018t4S31换行换行48136131211109876543210131171283右右1065942左左635632454211父父113431215104818253358权权nlsptsiea值值生成过程137编码的产生编码的产生值值aeistspnl权权58332518841015 1234131父父112454236536左左2495610右右381271113012345678
78、910111213生成生成a的代码：结点的代码：结点4的右孩子（的右孩子（1），结点），结点4是结点是结点2的左孩子（的左孩子（01），结点），结点2是结点是结点1的左孩子（的左孩子（001）对每个结点，从叶子往根推进，是左枝加对每个结点，从叶子往根推进，是左枝加0，是右枝加，是右枝加1138哈夫曼树类哈夫曼树类存储设计存储设计结点的表示：结点的数据、权值和父结点和左右孩子结点的表示：结点的数据、权值和父结点和左右孩子的位置的位置哈夫曼树的存储：一个结点数组以及一个整型数据成哈夫曼树的存储：一个结点数组以及一个整型数据成员，保存数组的大小。员，保存数组的大小。操作操作构建一棵哈夫曼树：构造函数
79、实现。构建一棵哈夫曼树：构造函数实现。给出节点数据数组，权值数组和数据个数给出节点数据数组，权值数组和数据个数获取树上节点的哈夫曼编码获取树上节点的哈夫曼编码返回一个数组，数组的元素由数据和编码两部分组成的返回一个数组，数组的元素由数据和编码两部分组成的139template class hfTreeprivate: struct Node Type data; /结点值结点值 int weight; /结点的权值结点的权值 int parent, left, right; ; Node *elem; int length;140public: struct hfCode Type data;
80、 string code; ; hfTree(const Type *x, const int *w, int size); void getCode(hfCode result ); hfTree() delete elem; 141构造函数构造函数 template hfTree:hfTree(const Type *v, const int *w, int size) const int MAX_INT = 32767; int min1, min2; /最小树、次最小树的权值最小树、次最小树的权值 int x, y; /最小树、次最小树的下标最小树、次最小树的下标 /置初值置初值 le
81、ngth = 2 * size; elem = new Nodelength; for (int i = size; i 0; -i) min1 = min2 = MAX_INT; x = y = 0; for (int j = i + 1; j length; +j) if (elemj.parent = 0) if (elemj.weight min1) min2 = min1; min1 = elemj.weight; x = y; y = j; else if (elemj.weight min2) min2 = elemj.weight; x = j; elemi.weight =
82、min1 + min2; elemi.left = x; elemi.right = y; elemi.parent = 0; elemx.parent = i; elemy.parent = i; 143getCode的伪代码的伪代码getCode(hfCode result) for (int i = size; i length; +i) resulti - size.data = elemi.data; resulti - size.code = ; p = elemi.parent; s = i;while (p不等于不等于0) if (p的左孩子是的左孩子是 = s) result
83、i - size.code 前添加前添加0; else resulti - size.code 前添前添1;移到上一层；移到上一层； 144getCode代码代码template void hfTree:getCode(hfCode result) int size = length / 2; int p,s; / s是追溯过程中正在处理的结点，是追溯过程中正在处理的结点，p是是s的父结点下的父结点下标标 for (int i = size; i length; +i) resulti - size.data = elemi.data; resulti - size.code = ; p =
84、elemi.parent; s = i;while (p) if (elemp.left = s) resulti - size.code = 0 + resulti - size.code; else resulti - size.code = 1 + resulti - size.code;s = p; p = elemp.parent; 145哈夫曼类的使用哈夫曼类的使用为下列符号集生成哈夫曼编码：为下列符号集生成哈夫曼编码：a(10), a(10), e(15), i(12), s(3), t(4), d(13), e(15), i(12), s(3), t(4), d(13), n(
85、1)n(1)146int main() char ch = aeistdn; int w = 10,15,12,3,4,13,1; hfTree tree(ch, w, 7); hfTree:hfCode result7; tree.getCode(result); for (int i=0; i 7; +i) cout resulti.data resulti.code endl; return 0; 147第五章第五章 树树树的概念树的概念二叉树二叉树表达式树表达式树哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码树和森林树和森林148树和森林树和森林树的存储实现树的存储实现 树的遍历树的遍历树、
86、森林和二叉树树、森林和二叉树149树的存储结构树的存储结构 标准形式：树中的每个结点除有数据字段之外，还有标准形式：树中的每个结点除有数据字段之外，还有 K 个指针字段；其中个指针字段；其中 K 为树的度。为树的度。datason1广义标准形式：在标准形式的基础上，再增加指向父亲结广义标准形式：在标准形式的基础上，再增加指向父亲结点的指针场。点的指针场。son2sonkparent150 E.g: 度数度数 K 3 的树的广义标准存储的树的广义标准存储ABCDEFGHIL 值值 s1 s2 s3 p0 A 1 2 3 -11 B 4 5 -1 02 C 6 -1 -1 03 D 7 8 -1
87、04 L -1 -1 -1 15 E -1 -1 -1 16 F -1 -1 -1 27 G 9 -1 -1 38 H -1 -1 -1 39 I -1 -1 -1 7 -1 表示空表示空缺点：空指针字段缺点：空指针字段 太多，多达太多，多达 ( K -1 ) n + 2 个。个。151孩子链表示法孩子链表示法将每个结点的所有孩子组织成一个链表。将每个结点的所有孩子组织成一个链表。树的节点由两部分组成：树的节点由两部分组成：存储数据元素值的数据部分存储数据元素值的数据部分指向孩子链的指针指向孩子链的指针如果树的所有结点存放在一个数组中，这个如果树的所有结点存放在一个数组中，这个数组称为表头数组
88、。这种存储方式称为静态数组称为表头数组。这种存储方式称为静态的孩子链表。的孩子链表。将树的所有结点组织成一个链表，称为动态将树的所有结点组织成一个链表，称为动态的孩子链表的孩子链表 152234 56 789 数据数据指指针1老王老王2王王13王王24王王35王王116王王127王王318王王329王王33老王老王王王1王王2王王3王王11王王12王王31王王32王王33153孩子兄弟链表示法孩子兄弟链表示法实质上是用二叉树表示一棵树。树中的每个结点实质上是用二叉树表示一棵树。树中的每个结点有数据字段、指向它的第一棵子树树根的指针字有数据字段、指向它的第一棵子树树根的指针字段、指向它的兄弟结点
89、的指针字段。段、指向它的兄弟结点的指针字段。 firstson data nextsibling 154ABCDEFGHIL A B C D E F G H L I 155双亲表示法双亲表示法 通过指向父结点的指针将树中所有的结点组织通过指向父结点的指针将树中所有的结点组织在一起在一起 在双亲表示法中，每个结点由两部分组成：在双亲表示法中，每个结点由两部分组成：存储数据元素的数据字段存储数据元素的数据字段存储父结点位置的父指针字段存储父结点位置的父指针字段 这种表示法对求指定结点的祖先的操作很方便，这种表示法对求指定结点的祖先的操作很方便，但对求指定结点的子孙则不方便。只适合某些但对求指定结点
90、的子孙则不方便。只适合某些应用，如不相交集的存储应用，如不相交集的存储156数据数据父父结点点1老王老王02王王113王王214王王315王王1126王王1227王王3148王王3249王王334老王老王王王1王王2王王3王王11王王12王王31王王32王王33157树和森林树和森林树的存储实现树的存储实现 树的遍历树的遍历树、森林和二叉树树、森林和二叉树158前序遍历前序遍历访问根结点；访问根结点；前序遍历根结点的第一棵子树、前序遍前序遍历根结点的第一棵子树、前序遍历它的第二棵子树、历它的第二棵子树、前序遍历它、前序遍历它的最后一棵子树。的最后一棵子树。 159后序遍历后序遍历后序遍历根结点
91、的第一棵子树、后序遍后序遍历根结点的第一棵子树、后序遍历它的第二棵子树、历它的第二棵子树、后序遍历它、后序遍历它的最后一棵子树。的最后一棵子树。访问根结点；访问根结点；160层次遍历层次遍历访问根结点；访问根结点；若第若第i i层已被访问，且第层已被访问，且第i+1i+1层的结点尚层的结点尚未被访问，则从左到右依次访问第未被访问，则从左到右依次访问第i+1i+1层层的结点。的结点。161BCDEFGHILA前序：前序：A、B、L、E、C、F、D、G、I、H后序：后序：L、E、B、F、C、I、G、H、D、A层次：层次：A、B、C、D、L、E、F、G、H、I162树和森林树和森林树的存储实现树的存
92、储实现 树的遍历树的遍历树、森林和二叉树树、森林和二叉树163树、森林和二叉树树、森林和二叉树二叉树是一种结构最简单、运算最简便的树二叉树是一种结构最简单、运算最简便的树形结构。但对很多问题来讲，其自然的描述形结构。但对很多问题来讲，其自然的描述形态是树或森林。形态是树或森林。树的孩子兄弟链表示法就是将一棵树表示成树的孩子兄弟链表示法就是将一棵树表示成二叉树的形态，这样就可以将二叉树中的许二叉树的形态，这样就可以将二叉树中的许多方法用在树的处理中。多方法用在树的处理中。 164ABCDFGEHIJABCDFGEHIJ165森林森林森林通常定义为树的集合或树的序列。森林通常定义为树的集合或树的序
93、列。森林的存储：存储一个森林要包括两方森林的存储：存储一个森林要包括两方面的内容面的内容存储森林中的每一棵树存储森林中的每一棵树表示这些树是属于同一个森林。表示这些树是属于同一个森林。 166森林的二叉树存储森林的二叉树存储将每棵树将每棵树TiTi转换成对应的二叉树转换成对应的二叉树BiBi；将将BiBi作为作为Bi-1Bi-1根结点的的右子树。根结点的的右子树。167ABCRFGHDEIJKLMN（a）森林）森林FABCRFGHDEIJKLMN（b）森林）森林F中的树对应的二叉树中的树对应的二叉树168ABCRFGHDEIJKLMN森林森林F中的树对应的二叉树中的树对应的二叉树169总结总结
94、 本章是数据结构的重点之一，也是本书许本章是数据结构的重点之一，也是本书许多后续章节的基础。多后续章节的基础。本章主要介绍了树形结构的基本概念，详本章主要介绍了树形结构的基本概念，详细讨论了一种重要的数据结构细讨论了一种重要的数据结构 二叉树二叉树的设计和实现。在此基础上介绍了二叉树的设计和实现。在此基础上介绍了二叉树的两种应用的两种应用 表达式树和哈夫曼树。表达式树和哈夫曼树。最后，本章还介绍了如何处理普通的树形最后，本章还介绍了如何处理普通的树形结构以及森林。普通的树形结构和森林的结构以及森林。普通的树形结构和森林的处理方法是将它们转换成二叉树来处理处理方法是将它们转换成二叉树来处理 17
95、0作业171第第6章章 优先级队列优先级队列 基本的优先级队列基本的优先级队列 二叉堆二叉堆D D堆堆归并优先级队列归并优先级队列STLSTL中的优先级队列中的优先级队列排队系统的模拟排队系统的模拟172基本的优先级队列基本的优先级队列结点之间的关系是由结点的优先级决定的，结点之间的关系是由结点的优先级决定的，而不是由入队的先后次序决定。优先级高而不是由入队的先后次序决定。优先级高的先出队，优先级低的后出队。这样的队的先出队，优先级低的后出队。这样的队列称为优先级队列。列称为优先级队列。优先级队列的操作与普通的队列相同优先级队列的操作与普通的队列相同173优先级队列的简单实现优先级队列的简单实
96、现利用现有的队列结构。有两种方法可以处理利用现有的队列结构。有两种方法可以处理优先级优先级入队时，按照优先级在队列中寻找合适的位置，入队时，按照优先级在队列中寻找合适的位置，将新入队的元素插入在此位置。出队操作的实现将新入队的元素插入在此位置。出队操作的实现保持不变。保持不变。入队操作的实现保持不变，将新入队的元素放在入队操作的实现保持不变，将新入队的元素放在队列尾。但出队时，在整个队列中查找优先级最队列尾。但出队时，在整个队列中查找优先级最高的元素，让它出队。高的元素，让它出队。174时间性能分析时间性能分析第一种方案的入队操作的时间复杂度是第一种方案的入队操作的时间复杂度是O O（N N）
97、，出队操作的时间复杂度是），出队操作的时间复杂度是O O（1 1）。）。第二种方案的入队操作的时间复杂度是第二种方案的入队操作的时间复杂度是O O（1 1），出队操作的时间复杂度是），出队操作的时间复杂度是O O（N N）。）。175第第6章章 优先级队列优先级队列 基本的优先级队列基本的优先级队列 二叉堆二叉堆D D堆堆归并优先级队列归并优先级队列STLSTL中的优先级队列中的优先级队列排队系统的模拟排队系统的模拟176二叉堆二叉堆堆是一棵完全二叉树，且满足下述关系之一堆是一棵完全二叉树，且满足下述关系之一 k ki i k k2i 2i 且且 k ki i k k2i+1 2i+1 (i=
98、1,2,(i=1,2, , , n/2n/2 ) )或者：或者： k k i i k k2i 2i 且且 k ki i k k2i+1 2i+1 (i=1,2,(i=1,2, , , n/2n/2 ) ) 其中，下标是树按层次遍历的次序其中，下标是树按层次遍历的次序满足前一条件的称为最小化堆。例如满足前一条件的称为最小化堆。例如: :序列序列 2,3,4,5,7,10,23,29,60 2,3,4,5,7,10,23,29,60 是最小化堆是最小化堆 满足后一条件的称为最大化堆。例如满足后一条件的称为最大化堆。例如: :序列序列 12,7,8,4,6,5,3,1 12,7,8,4,6,5,3,
99、1 是最大化堆是最大化堆 1774836712515423732102960最大化堆最大化堆最小化堆最小化堆178二叉堆的特性二叉堆的特性结构性：符合完全二叉树的结构结构性：符合完全二叉树的结构有序性：满足父节点小于子节点（最小有序性：满足父节点小于子节点（最小化堆）或父节点大于子节点（最大化堆）化堆）或父节点大于子节点（最大化堆）以下的讨论都以最小化堆为例以下的讨论都以最小化堆为例179二叉堆的存储二叉堆的存储可以采用顺序存储可以采用顺序存储二叉堆的有序性可以很容易地通过下标来反映二叉堆的有序性可以很容易地通过下标来反映542373210296023457102329600123456789
100、180基于二叉堆的优先级队列基于二叉堆的优先级队列 如果数值越小，优先级越高，则可以用一个最小化如果数值越小，优先级越高，则可以用一个最小化堆存储优先级队列堆存储优先级队列在最小化堆中，最小元素是根元素，而根结点永远在最小化堆中，最小元素是根元素，而根结点永远存放在数组的下标为存放在数组的下标为1 1的元素中。的元素中。获取队头元素的操作就是返回下标为获取队头元素的操作就是返回下标为1 1的数组元素值的数组元素值出队操作就是删除下标为出队操作就是删除下标为1 1的数组元素中的值的数组元素中的值入队操作就是在数组的末尾添加一个元素，但添加后要入队操作就是在数组的末尾添加一个元素，但添加后要调整元
101、素的位置，以保持堆的有序性调整元素的位置，以保持堆的有序性181优先级队列类优先级队列类数据成员：用一个动态数组数据成员：用一个动态数组成员函数：实现队列类的所有操作成员函数：实现队列类的所有操作182优先级队列类的定义优先级队列类的定义template class priorityQueueprivate: int currentSize; Type *array; int maxSize; void doubleSpace(); void buildHeap( ); void percolateDown( int hole ); 183public: priorityQueue( int
102、capacity = 100 ) array = new Typecapacity; maxSize = capacity; currentSize = 0; priorityQueue( const Type data, int size );priorityQueue() delete array; bool isEmpty( ) const return currentSize = 0; void enQueue( const Type & x ); Type deQueue(); Type getHead() return array1; ;184enQueue（x）enQueueen
103、Queue操作是在堆中插入一个新元素操作是在堆中插入一个新元素堆的插入是在具有最大序号的元素之后插入新堆的插入是在具有最大序号的元素之后插入新的元素或结点，否则将违反堆的结构性。的元素或结点，否则将违反堆的结构性。如果新元素放入后，没有违反堆的有序性，那如果新元素放入后，没有违反堆的有序性，那么操作结束。否则，让该节点向父节点移动，么操作结束。否则，让该节点向父节点移动，直到满足有序性或到达根节点。直到满足有序性或到达根节点。新节点的向上移动称为向上过滤新节点的向上移动称为向上过滤(percolate (percolate up)up)185在如下的堆中插入元素在如下的堆中插入元素1的过程：的
104、过程： 54237321029605423321029607186542332102960754233211029607187enQueue过程过程template void priorityQueue:enQueue( const Type & x ) if( currentSize = maxSize - 1 ) doubleSpace(); / 向上过滤向上过滤 int hole = +currentSize; for( ; hole 1 & x array hole / 2 ; hole /= 2 ) array hole = array hole / 2 ; array hole =
105、 x; 188enQueue的时间效率的时间效率最坏情况是对数的最坏情况是对数的平均情况，过滤会提前结束。有资料表平均情况，过滤会提前结束。有资料表明，平均是明，平均是2.62.6次比较，因此元素平均上次比较，因此元素平均上移移1.61.6层。层。189DeQueue 操作操作当最小元素被删除时，在根上出现了一个空结点。当最小元素被删除时，在根上出现了一个空结点。堆的大小比以前小堆的大小比以前小1 1，堆的结构性告诉我们，最后，堆的结构性告诉我们，最后一个结点应该删掉。一个结点应该删掉。 如果最后一项可以放在此空结点中，就把它放进如果最后一项可以放在此空结点中，就把它放进去。然而，这通常是不可
106、能的。去。然而，这通常是不可能的。我们必须玩与插入操作相同的游戏：把某些项放我们必须玩与插入操作相同的游戏：把某些项放入空结点，然后移动空结点。仅有的区别在于：入空结点，然后移动空结点。仅有的区别在于：对对DeQueue操作，空结点是往下移动。操作，空结点是往下移动。190向下过滤过程向下过滤过程找到空结点的一个较小的子结点，如果找到空结点的一个较小的子结点，如果该儿子的值小于我们要放入的项，则把该儿子的值小于我们要放入的项，则把该儿子放入空结点，把空结点往下推一该儿子放入空结点，把空结点往下推一层，重复这个动作，直到该项能被放入层，重复这个动作，直到该项能被放入正确的位置。正确的位置。 19
107、1542332110296075423321029605423321029605423732102960192deQueue() template Type priorityQueue:deQueue() Type minItem; minItem = array 1 ; array 1 = array currentSize- ; percolateDown( 1 ); return minItem; 193向下过滤向下过滤template void priorityQueue:percolateDown( int hole ) int child; Type tmp = array hol
108、e ; for( ; hole * 2 = currentSize; hole = child ) child = hole * 2; if( child != currentSize & array child + 1 array child ) child+; if( array child tmp ) array hole = array child ; else break; array hole = tmp; 194deQueue操作的性能操作的性能因为树有对数的深度，在最坏情况下，因为树有对数的深度，在最坏情况下，deQueuedeQueue是一个对数时间的操作。是一个对数时间的操
109、作。根据堆的有序性，堆中最后一个结点的值一根据堆的有序性，堆中最后一个结点的值一般都是比较大的。因此，向下过滤很少有提般都是比较大的。因此，向下过滤很少有提前一或二层结束的，所以前一或二层结束的，所以deQueuedeQueue操作平均操作平均也是对数时间。也是对数时间。 195建堆建堆可以看成可以看成N N次连续插入，其时间应该是在次连续插入，其时间应该是在O(NlogNO(NlogN) )时间内完成。时间内完成。 事实上，在构造过程中，我们并不关心每个元素加事实上，在构造过程中，我们并不关心每个元素加入后堆的状态，我们关心的是入后堆的状态，我们关心的是N N个元素全部加入后个元素全部加入后
110、的最后状态，最后的状态是要保证堆的有序性。至的最后状态，最后的状态是要保证堆的有序性。至于中间过程中的有序性是否成立并不重要。于中间过程中的有序性是否成立并不重要。有了这个前提后，我们能将构造堆的时间复杂度降有了这个前提后，我们能将构造堆的时间复杂度降到到O O（N N） 196建堆过程建堆过程利用堆的递归定义利用堆的递归定义如果函数如果函数buildHeapbuildHeap可以将一棵完全二叉树可以将一棵完全二叉树调整为一个堆调整为一个堆 ，那么，只要对左子堆和右，那么，只要对左子堆和右子堆递归调用子堆递归调用buildHeapbuildHeap。至此，我们能保。至此，我们能保证除了根结点外
111、，其余的地方都建立起了堆证除了根结点外，其余的地方都建立起了堆的有序性。然后对根结点调用的有序性。然后对根结点调用percolateDownpercolateDown，以创建堆的有序性。，以创建堆的有序性。197建堆过程的非递归实现建堆过程的非递归实现如果我们以逆向层次的次序对结点调用如果我们以逆向层次的次序对结点调用percolateDownpercolateDown，那么在，那么在percolateDownpercolateDown（i i）被处理时，所有结点被处理时，所有结点i i的子孙都已经调用过的子孙都已经调用过percolateDownpercolateDown。注意，不需要对叶结
112、点执行注意，不需要对叶结点执行percolateDownpercolateDown。因此，我们是从编号最大的非叶结点开始。因此，我们是从编号最大的非叶结点开始。198例如，给出的数据初值为例如，给出的数据初值为40，20，60，15，30，25，10，35，45，50，55，构造一个最小化堆，构造一个最小化堆 4035156010302025455055首先，将它看成是首先，将它看成是一棵完全二叉树，一棵完全二叉树，然后把它调整成一然后把它调整成一个堆个堆199403515601030202545505530和和15没没有违反堆有违反堆的有序性，的有序性，接着调整接着调整60403515106
113、0302025455055调整调整20 4035201060301525455055调整调整40 1035202560301540455055200建堆总结建堆总结自下往上调整每一个子堆自下往上调整每一个子堆在调整每个堆时，假设除根以外，所有在调整每个堆时，假设除根以外，所有节点满足堆的定义节点满足堆的定义根结点的调整和删除时一样，可以通过根结点的调整和删除时一样，可以通过调用调用percolateDown实现实现201建堆建堆 template void priorityQueue:buildHeap( ) for ( int i = currentSize / 2; i 0; i- ) p
114、ercolateDown( i ); 202带有初始数据的构造函数的实现带有初始数据的构造函数的实现 template priorityQueue:priorityQueue( const Type *items, int size ) : maxSize(size + 10 ), currentSize(size) array = new TypemaxSize; for( int i = 0; i size; i+ ) array i + 1 = items i ; buildHeap(); 203建堆的时间代价分析建堆的时间代价分析 建堆的时间是建堆的时间是O(N)O(N)的。的。高度为
115、高度为h h的节点（叶节点为的节点（叶节点为0 0），在），在percolateDownpercolateDown中交换的最大次数是中交换的最大次数是h h。建堆的时间是所有节点的调整时所需交换建堆的时间是所有节点的调整时所需交换次数之和，即所有节点的高度之和。次数之和，即所有节点的高度之和。204定理：对于一棵高度为定理：对于一棵高度为h h，包含了，包含了N = 2N = 2H+1H+1 - 1 - 1个个结点的满二叉树，结点的高度和为结点的满二叉树，结点的高度和为N H 1 N H 1 证明：高度为证明：高度为h h的结点有一个，高度为的结点有一个，高度为h-1h-1的结点的结点有有2
116、2个，高度为个，高度为h-2h-2的结点有的结点有2 22 2个，高度为个，高度为h-ih-i的节的节点有点有2 2i i个。因此，所有节点的高度和为：个。因此，所有节点的高度和为：205第第6章章 优先级队列优先级队列 基本的优先级队列基本的优先级队列 二叉堆二叉堆D D堆堆归并优先级队列归并优先级队列STLSTL中的优先级队列中的优先级队列排队系统的模拟排队系统的模拟206D-D-堆堆每个节点有每个节点有d d个儿子，这样生成的堆比较矮。个儿子，这样生成的堆比较矮。插入：插入：O(logO(logd dN N) )删除：需要在删除：需要在d d个元素中找出最小的，时间复个元素中找出最小的，
117、时间复杂度为：杂度为：O(dlogO(dlogd dN N) )优点：插入快优点：插入快缺点：删除慢缺点：删除慢用途：用途：插入比删除多的队列插入比删除多的队列队列太大，内存放不下，要放在外存的时候队列太大，内存放不下，要放在外存的时候207第第6章章 优先级队列优先级队列 基本的优先级队列基本的优先级队列 二叉堆二叉堆D D堆堆归并优先级队列归并优先级队列STLSTL中的优先级队列中的优先级队列排队系统的模拟排队系统的模拟208归并优先级队列归并优先级队列左堆左堆斜堆斜堆贝努里堆贝努里堆二叉堆能有效地支持优先级队列的入队和出队操作，二叉堆能有效地支持优先级队列的入队和出队操作，但不能有效地支
118、持两个优先级队列的归并。能有效但不能有效地支持两个优先级队列的归并。能有效地支持优先级队列归并的数据结构有左堆、斜堆和地支持优先级队列归并的数据结构有左堆、斜堆和贝努里堆等贝努里堆等 209左堆左堆满足堆的有序性，但平衡稍弱一些的堆满足堆的有序性，但平衡稍弱一些的堆定义：空路径长度定义：空路径长度( (nplnpl) ) Npl(xNpl(x) )为为x x到不满两个孩子的节点的最短到不满两个孩子的节点的最短路径。具有路径。具有0 0个或一个孩子的节点的个或一个孩子的节点的nplnpl为为0 0，npl(NULLnpl(NULL) = -1) = -1左堆：对每个节点左堆：对每个节点x x，左
119、孩子的，左孩子的nplnpl不小于右不小于右孩子的孩子的nplnpl显然，左堆是向左倾斜的堆。显然，左堆是向左倾斜的堆。2101010001110000左堆左堆非左堆非左堆211左堆的主要操作左堆的主要操作归并归并采用递归的方法采用递归的方法将根节点稍大的堆与另一个堆的右子树归并将根节点稍大的堆与另一个堆的右子树归并如产生的堆违反了左堆的定义，则交换左右如产生的堆违反了左堆的定义，则交换左右子树子树递归的终止条件：当某个堆为空时，另一个递归的终止条件：当某个堆为空时，另一个堆就是归并的结果堆就是归并的结果21238102114232617H167121824331837H27378171826
120、H2与与H1的右子堆归并的右子堆归并121824336213左堆的入队和出队操作左堆的入队和出队操作入队可以看成是归并的特例。将入队元素看入队可以看成是归并的特例。将入队元素看成是指有一个元素的左堆，归并两个左堆就成是指有一个元素的左堆，归并两个左堆就形成了最终的结果。形成了最终的结果。出队操作的实现也很简单。删除了根结点后，出队操作的实现也很简单。删除了根结点后，这个堆就分裂成两个堆。把这两个堆重新归这个堆就分裂成两个堆。把这两个堆重新归并起来就是原始的队列中执行出队运算后的并起来就是原始的队列中执行出队运算后的结果。结果。 214归并优先级队列归并优先级队列左堆左堆斜堆斜堆贝努里堆贝努里堆
121、二叉堆能有效地支持优先级队列的入队和出队操作，二叉堆能有效地支持优先级队列的入队和出队操作，但不能有效地支持两个优先级队列的归并。能有效但不能有效地支持两个优先级队列的归并。能有效地支持优先级队列归并的数据结构有左堆、斜堆和地支持优先级队列归并的数据结构有左堆、斜堆和贝努里堆等贝努里堆等 215斜堆斜堆斜堆是自调整的左堆。它满足堆的有序性，斜堆是自调整的左堆。它满足堆的有序性，但不满足堆的结构性。不需要维护但不满足堆的结构性。不需要维护nplnpl。因。因此，右路径可以任意长。此，右路径可以任意长。最坏的时间复杂性最坏的时间复杂性O(N)O(N)，但对，但对M M个连续的操个连续的操作，最坏的
122、运行时间是作，最坏的运行时间是O(MlogNO(MlogN) )。因此，。因此，每个操作由均摊的每个操作由均摊的O(logNO(logN) )的时间复杂度。的时间复杂度。它的操作比左堆简单。它的操作比左堆简单。216斜堆的归并斜堆的归并类似于左堆，只是在左堆中，归并后左类似于左堆，只是在左堆中，归并后左右子堆的交换是有条件的；而在斜堆中，右子堆的交换是有条件的；而在斜堆中，是无条件的，必须交换。仅有一种例外是无条件的，必须交换。仅有一种例外情况：右路径上所有节点中的最大者不情况：右路径上所有节点中的最大者不需要交换它的孩子。需要交换它的孩子。21738102114232617H16712182
123、4331837H27378171826H2与与H1的右子堆归并的右子堆归并121824336218斜堆的优点斜堆的优点不需要保存不需要保存nplnpl不需要维护不需要维护nplnpl不需要测试不需要测试nplnpl以决定是否要交换左右子以决定是否要交换左右子堆堆219归并优先级队列归并优先级队列左堆左堆斜堆斜堆贝努里堆贝努里堆二叉堆能有效地支持优先级队列的入队和出队操作，二叉堆能有效地支持优先级队列的入队和出队操作，但不能有效地支持两个优先级队列的归并。能有效但不能有效地支持两个优先级队列的归并。能有效地支持优先级队列归并的数据结构有左堆、斜堆和地支持优先级队列归并的数据结构有左堆、斜堆和贝努
124、里堆等贝努里堆等 220贝努里队列贝努里队列贝努里队列支持插入、删除和归并操作。贝努里队列支持插入、删除和归并操作。最坏情况下的时间复杂性是最坏情况下的时间复杂性是O(logNO(logN) )，但，但平均的插入时间是一个常量。平均的插入时间是一个常量。贝努里队列表示为一个贝努里树的集合。贝努里队列表示为一个贝努里树的集合。221贝努里树贝努里树贝努里树是一棵普通的树，不是二叉树。贝努里树是一棵普通的树，不是二叉树。高度为高度为0 0的贝努里树是单个节点，高度为的贝努里树是单个节点，高度为k k的贝的贝努里树努里树B Bk k是将一棵是将一棵B Bk-1k-1加到另一棵加到另一棵B Bk-1k
125、-1的根上形的根上形成的。成的。贝努里树满足堆的有序性贝努里树满足堆的有序性222B0B1B2B3223贝努里树贝努里树Bk的特性的特性B Bk k有有2 2k k个节点个节点第第d d层的节点数是贝努里系数层的节点数是贝努里系数224优先级队列的表示优先级队列的表示把优先级队列表示为贝努里树的集合。把优先级队列表示为贝努里树的集合。每个高度至多有一棵贝努里树。这样，每个高度至多有一棵贝努里树。这样，对于给定的元素个数，这个集合是唯一对于给定的元素个数，这个集合是唯一的，即元素个数的二进制表示。的，即元素个数的二进制表示。如如1313个元素，可表示为个元素，可表示为11011101。即该集合。
126、即该集合由由B B3 3、B B2 2和和B B0 0组成组成225六个元素的贝努里队列：六个元素的贝努里队列：16181221246514262351246513七个元素的贝努里队列：七个元素的贝努里队列：226贝努里队列的操作贝努里队列的操作归并归并入队入队出队出队227归并操作归并操作由低到高依次归并两个优先级队列中高度由低到高依次归并两个优先级队列中高度相同的树。如果由于前一次归并而出现三相同的树。如果由于前一次归并而出现三棵高度相同的树时，留下一棵，归并其余棵高度相同的树时，留下一棵，归并其余两棵。两棵。高度相同的树的归并：将根节点大的作为高度相同的树的归并：将根节点大的作为根节点小
127、的树的子树。根节点小的树的子树。归并的时间效益：归并的时间效益：N N个元素的队列有个元素的队列有logNlogN棵棵树，因此最坏情况为树，因此最坏情况为O(logNO(logN) )。228归并以下两个队列：归并以下两个队列：14262351246513161812212465H1H2归并归并B B0 0：由于只有：由于只有H2H2有有B B0 0，所以无需归并，所以无需归并归并归并B B1 1：形成以下的：形成以下的树树14261618现在有三棵现在有三棵B2B2，留下，留下一棵，归并其余两棵一棵，归并其余两棵229最后的队列：最后的队列：1323512465122124651426161
128、8230贝努里队列的操作贝努里队列的操作归并归并入队入队出队出队231插入插入插入是归并的特例插入是归并的特例为被插入节点形成一棵单节点的树组成的集合，为被插入节点形成一棵单节点的树组成的集合，归并两个集合归并两个集合时间效益：最坏情况为时间效益：最坏情况为O(logNO(logN) )，相当于二进制，相当于二进制加法中的加加法中的加1 1，但每次都有进位的情况。一般进，但每次都有进位的情况。一般进位进到中间的某一位会终止。即当原先集合中缺位进到中间的某一位会终止。即当原先集合中缺少少B Bi i时，则归并时，则归并i i次，由于每棵树的出现是等概次，由于每棵树的出现是等概率的，因此平均归并两
129、次就能结束。率的，因此平均归并两次就能结束。232贝努里队列的操作贝努里队列的操作归并归并入队入队出队出队233删除删除找出具有最小根值的树找出具有最小根值的树T T将将T T从原先的集合中删掉从原先的集合中删掉在在T T中删除根节点中删除根节点归并归并T T与原先的集合与原先的集合234在以下的队列中删除最小元素：在以下的队列中删除最小元素：13235124651221246514261618最小元素出现在最小元素出现在B3B3中，删除最小元素中，删除最小元素1212，形成下列森林：，形成下列森林：21246514261618235归并两个森林：归并两个森林：2351246513212465
130、14261618236贝努里队列的存储贝努里队列的存储每棵树看成是有序树，采用标准的树的每棵树看成是有序树，采用标准的树的存储方式存储方式孩子兄弟链的表示法孩子兄弟链的表示法整个森林表示成一个指向树根的指针的整个森林表示成一个指向树根的指针的线性表线性表23713235124651221246514261618如下的贝努里队列可表示成：如下的贝努里队列可表示成：13232451651221246514261618238贝努里队列的时间性能贝努里队列的时间性能归并：归并：N N个元素的队列至多有个元素的队列至多有logNlogN棵树，每两棵树棵树，每两棵树的归并只需要常量的时间。因此最坏情况的时
131、间的归并只需要常量的时间。因此最坏情况的时间复杂度为复杂度为O(logNO(logN) )。但可以证明平均情况的时间复。但可以证明平均情况的时间复杂度是常量的。杂度是常量的。 入队操作的平均时间复杂度是入队操作的平均时间复杂度是O O（1 1）的）的 出队操作：首先在队列中找出根结点值最小的树。出队操作：首先在队列中找出根结点值最小的树。这需要花费这需要花费O O（logNlogN）的时间。然后又要归并两个）的时间。然后又要归并两个优先级队列，又需要优先级队列，又需要O O（logNlogN）的时间。所以删除）的时间。所以删除操作的时间复杂度是操作的时间复杂度是O O（logNlogN）的）的
132、 239第第6章章 优先级队列优先级队列 基本的优先级队列基本的优先级队列 二叉堆二叉堆D D堆堆归并优先级队列归并优先级队列STLSTL中的优先级队列中的优先级队列排队系统的模拟排队系统的模拟240STLSTL中的优先级队列中的优先级队列头文件：头文件：queuequeue类模版：类模版：priority_queuepriority_queue实现方式：二叉堆实现方式：二叉堆主要成员：主要成员：Void push( const Object &x)Void push( const Object &x)Const Object &top() constConst Object &top() c
133、onstVoid pop()Void pop()BoolBool empty() empty()Void clear()Void clear()241使用实例使用实例#include #include using namespace std;int main() priority_queue q; q.push(10); q.push(1); q.push(5); q.push(8); q.push(0); q.push(4); q.push(9); q.push(7); q.push(3); q.push(6); q.push(2); while (!q.empty() cout q.top
134、() ; q.pop(); return 0;242第第6章章 优先级队列优先级队列 基本的优先级队列基本的优先级队列 二叉堆二叉堆D D堆堆归并优先级队列归并优先级队列STLSTL中的优先级队列中的优先级队列排队系统的模拟排队系统的模拟243单服务台的排队系统单服务台的排队系统在单服务台系统中，先到达的顾客先获得在单服务台系统中，先到达的顾客先获得服务，也肯定先离开。到达和离开的次序服务，也肯定先离开。到达和离开的次序是一致的。是一致的。事件处理的次序是：顾客事件处理的次序是：顾客1到达、顾客到达、顾客1离离开、顾客开、顾客2到达、顾客到达、顾客2离开、离开、顾客、顾客n到达、顾客到达、顾客
135、n离开离开只需要一个普通队列保存顾客到达信息只需要一个普通队列保存顾客到达信息244多服务台的排队系统多服务台的排队系统在多服务台系统中，先到达的顾客先获得服务，但在多服务台系统中，先到达的顾客先获得服务，但后获得服务的顾客可能先离开；后获得服务的顾客可能先离开；事件处理的次序可能是：顾客事件处理的次序可能是：顾客1到达、顾客到达、顾客2到达、到达、顾客顾客2离开、顾客离开、顾客3到达、顾客到达、顾客1离开、顾客离开、顾客3离开离开、顾客、顾客n到达、顾客到达、顾客n离开、离开、发生时间早的事件先处理，发生时间晚的事件后处发生时间早的事件先处理，发生时间晚的事件后处理。因而需要一个优先级队列存
136、放事件。事件的优理。因而需要一个优先级队列存放事件。事件的优先级就是发生的时间先级就是发生的时间245模拟过程模拟过程模拟开始时，产生所有的到达事件，存入优先级队模拟开始时，产生所有的到达事件，存入优先级队列。列。模拟器开始处理事件：模拟器开始处理事件：从队列中取出一个事件。这是第一个顾客的到达事件。从队列中取出一个事件。这是第一个顾客的到达事件。生成所需的服务时间。当前时间加上这个服务时间就是生成所需的服务时间。当前时间加上这个服务时间就是这个顾客的离开时间。生成一个在这个时候离开的事件，这个顾客的离开时间。生成一个在这个时候离开的事件，插入到事件队列。插入到事件队列。同样模拟器从队列中取出
137、的事件也可能是离开事件，这同样模拟器从队列中取出的事件也可能是离开事件，这时只要将这个离开事件从队列中删去，为他服务的服务时只要将这个离开事件从队列中删去，为他服务的服务台变成了空闲状态，可以继续为别的顾客服务。台变成了空闲状态，可以继续为别的顾客服务。 246产生产生CustomNumCustomNum个顾客的到达事件，个顾客的到达事件，按时间的大小存入事件队列；按时间的大小存入事件队列；置等待队列为空；置等待队列为空；置所有柜台为空闲；置所有柜台为空闲；设置等待时间为设置等待时间为0 0；多服务台的排队系统过程多服务台的排队系统过程247While （事件队列非空）（事件队列非空） 队头元
138、素出队；队头元素出队； 设置当前时间为该事件发生的时间；设置当前时间为该事件发生的时间； switch(事件类型）事件类型） case 到达：到达：if (柜台有空柜台有空) 柜台数减柜台数减1； 生成所需的服务时间生成所需的服务时间 ； 修改事件类型为修改事件类型为“离开离开” 设置事件发生时间为当前时间加上服务时间；设置事件发生时间为当前时间加上服务时间； 重新存入事件队列；重新存入事件队列； else 将该事件存入等待队列；将该事件存入等待队列； case 离开：离开：if （等待队列非空）（等待队列非空） 队头元素出队；队头元素出队； 统计该顾客的等待时间；统计该顾客的等待时间； 生成
139、所需的服务时间生成所需的服务时间 ；修改事件类型为；修改事件类型为“离开离开” 设置事件发生时间为当前时间加上服务时间；设置事件发生时间为当前时间加上服务时间； 存入事件队列；存入事件队列； else 空闲柜台数加空闲柜台数加1； 计算平均等待时间；计算平均等待时间； 返回；返回；248模拟类模拟类设计一个模拟类，告诉它顾客到达时间间隔设计一个模拟类，告诉它顾客到达时间间隔的分布、服务时间的分布、模拟的柜台数以的分布、服务时间的分布、模拟的柜台数以及想要模拟多少个顾客。能提供在本次服务及想要模拟多少个顾客。能提供在本次服务中顾客的平均等待时间是多少。中顾客的平均等待时间是多少。因此这个类应该有
140、两个公有函数：构造函数因此这个类应该有两个公有函数：构造函数接受用户输入的参数，另外一个就是执行模接受用户输入的参数，另外一个就是执行模拟并最终给出平均等待时间的函数拟并最终给出平均等待时间的函数avgWaitTimeavgWaitTime。这个类要保存的数据就是模拟。这个类要保存的数据就是模拟的参数。的参数。249模拟类的定义模拟类的定义 class simulatorint noOfServer; /服务台个数服务台个数int arrivalLow; /到达间隔时间的下界到达间隔时间的下界int arrivalHigh; /到达间隔时间的上界到达间隔时间的上界int serviceTime
141、Low; /服务间隔时间的下界服务间隔时间的下界int serviceTimeHigh; /服务间隔时间的上界服务间隔时间的上界int customNum; /模拟的顾客数模拟的顾客数struct eventT int time; /事件发生时间事件发生时间 int type; /事件类型。事件类型。0为到达，为到达，1为离开为离开 bool operator(const eventT &e) const return time e.time; ;public:simulator();int avgWaitTime(); 250构造函数的实现构造函数的实现 simulator:simulato
142、r() cout noOfServer; cout arrivalLow arrivalHigh; cout serviceTimeLow serviceTimeHigh;cout customNum; srand(time(NULL); 251avgWaitTime()int simulator:avgWaitTime() int serverBusy = 0; / 正在工作的服务台数正在工作的服务台数 int currentTime ; / 记录模拟过程中的时间记录模拟过程中的时间 int totalWaitTime = 0; /模拟过程中所有顾客的等待时间的总和模拟过程中所有顾客的等待时
143、间的总和 linkQueue waitQueue; /顾客等待队顾客等待队列列 priorityQueue eventQueue; /事件队事件队列列 eventT currentEvent; 252/生成初始的事件队列生成初始的事件队列 int i; currentEvent.time = 0; currentEvent.type = 0; for (i=0; icustomNum; +i) currentEvent.time += arrivalLow + (arrivalHigh -arrivalLow +1) * rand() / (RAND_MAX + 1); eventQueue.
144、enQueue(currentEvent); 253/模拟过程模拟过程 while (!eventQueue.isEmpty() currentEvent = eventQueue.deQueue(); currentTime = currentEvent.time; switch(currentEvent.type) case 0: /处理到达事件处理到达事件 break; case 1: /处理离开事件处理离开事件 /switch结束结束 /while结束结束 return totalWaitTime / customNum; 254处理到达事件处理到达事件if (serverBusy !
145、= noOfServer) +serverBusy; currentEvent.time += serviceTimeLow + (serviceTimeHigh - serviceTimeLow +1) * rand() / (RAND_MAX + 1); currentEvent.type = 1; eventQueue.enQueue(currentEvent); else waitQueue.enQueue(currentEvent);255处理离开事件处理离开事件if (!waitQueue.isEmpty() currentEvent = waitQueue.deQueue();
146、totalWaitTime += currentTime - currentEvent.time; currentEvent.time = currentTime + serviceTimeLow + (serviceTimeHigh - serviceTimeLow +1) * rand() / (RAND_MAX + 1); currentEvent.type = 1; eventQueue.enQueue(currentEvent); else -serverBusy;256simulator类的使用类的使用 int main() simulator sim; cout 平均等待时间：平
147、均等待时间： sim.avgWaitTime() endl; return 0;257某次执行结果某次执行结果 请输入柜台数：请输入柜台数：4请输入到达时间间隔的上下界（最小间隔请输入到达时间间隔的上下界（最小间隔时间时间 最大间隔时间）：最大间隔时间）：0 2请输入服务时间的上下界（服务时间下界请输入服务时间的上下界（服务时间下界 服务时间上界）：服务时间上界）：2 7请输入模拟的顾客数：请输入模拟的顾客数：1000平均等待时间：平均等待时间：61258总结总结 优先级队列是程序设计中常用的一个工具。优先级队列是程序设计中常用的一个工具。本章介绍了一种优先级队列的优秀的实现方本章介绍了一种优先级队列的优秀的实现方法法 二叉堆。二叉堆。还介绍了一些能够实现优先级队列归并的堆还介绍了一些能够实现优先级队列归并的堆的概念，的概念，最后。介绍了优先级队列的一个重要应用，最后。介绍了优先级队列的一个重要应用，即多服务台的排队系统的模拟。即多服务台的排队系统的模拟。259作业作业260
