数据结构与算法分析新视角（第2版） 课件 周幸妮 第5-9章 树-经典算法

数据结构与算法分析

新视角

结点逻辑关系分层次的非线性结构树Chapter

5DataStructuresandAlgorithmAnalysis主要内容广义表的概念、存储结构、基本运算广义表树的定义和基本术语二叉树的概念、存储结构遍历二叉树哈夫曼树及其应用树学习目标了解数据的逻辑结构从线性结构到非线性结构的过渡了解包含子结构的线性结构理解链式存储结构在表达非线性数据结构中的作用掌握树的概念、存储方法、基本运算了解广义表的概念、结构特点及其存储表示方法实际问题中的树及抽象树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树的遍历树的应用广义表*CONTENTS5.15.25.35.45.55.65.75.8实际问题中的树及抽象树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树的遍历树的应用广义表*CONTENTS5.15.25.35.45.55.65.75.85.1实际问题中的树及抽象树引例1——日常生活中的树形结构8树引例2——计算机的目录结构9树引例3——树形结构的网站10表达式树11实际问题本质的抽象12一切具有层次关系的问题都可用树来描述实际问题中的树及抽象树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树的遍历树的应用广义表*CONTENTS5.15.25.35.45.55.65.75.8树的逻辑结构14abdcefhgijlmnk层次结构一多对应非线性线性结构便不足以方便地描述这样的复杂情形树5.2树的逻辑结构5.2.15.2.2树的定义和基本术语树的操作定义5.2树的逻辑结构5.2.15.2.2树的定义和基本术语树的操作定义树17定义AGDCBFE树形结构是一种重要的非线性结构，讨论的是层次和分支关系树是递归结构——在树的定义中又用到了树的概念树（tree）是包含n个结点的有限集合，其中：（1）有一个根结点，它只有直接后继，但没有直接前趋。（2）除根结点之外的其余数据元素被分为m个根的子树。当树的集合为空时，n=0，此时称为空树，空树中没有结点。树的示意图18树的图形表示方法19树的相关术语20AGDCBFE包含一个数据元素及若干指向子树的分支结点的子树的根称为该结点的孩子一个结点的直接上层结点称为该结点的双亲同一双亲的孩子结点B、C、D是A的孩子，E、F是B的孩子A是B、C、D的双亲，B是E、F的双亲B、C、D是兄弟关系树的结点孩子结点双亲结点兄弟结点树的相关术语21AGDCBFE结点层树的深度结点的度树的度叶子结点分枝结点有序树无序树森林Level1Level2Level3根结点的层定义为1；根的孩子为第二层结点，依此类推；树中最大的结点层度不为0的结点也叫终端结点，是度为0的结点树中最大的结点度结点子树的个数不考虑子树的顺序子树有序的树互不相交的树集合树的基本术语——示例22E,K,L,GH,I,M树的概念23我们熟悉的树形结构中，无序树、有序树有哪些？思考&讨论讨论：有序树无序树的区别在于子树是否有顺序要求，有顺序要求的如家谱、书的目录等；无序的可以是计算机中的文件夹目录等。5.2树的逻辑结构5.2.15.2.2树的定义和基本术语树的操作定义构造建立一棵树，初始化。树的基本操作查找可以是查找根结点、双亲结点、孩子结点、叶子结点、指定值的结点等。插入删除在指定位置插入/删除结点遍历沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题求深度计算树的高度。实际问题中的树及抽象树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树的遍历树的应用广义表*CONTENTS5.15.25.35.45.55.65.75.8树的存储结构27存得进取得出A存数值存联系B树形结构的存储原则。非线性结构比线性关系复杂，存储树形结构问题的关键与重点。树的存储结构2828树形结构存储结点间联系的原则是什么？一个双亲n个孩子对于设计好的存储结构，检验的标准则是只要在存储结构中能找到一个结点的这两种关系，那么这样的存储结构设计就是可行的。我们可以称之为“双亲孩子检验原则”。双亲孩子检验法思考&讨论5.3树的存储结构5.3.15.3.2树的连续存储方式树的链式存储方式5.3树的存储结构5.3.15.3.2树的连续存储方式树的链式存储方式树连续存储1——双亲孩子表示法31树连续存储2——双亲表示法32树连续存储3——孩子表示法335.3树的存储结构5.3.15.3.2树的连续存储方式树的链式存储方式树的链式存储方式35树的链式存储方式361.同构型结构的特点有哪些？关于树的结构讨论37思考&讨论2．什么样的树在用同构型结构时，空的指针域最少？讨论：同构型结构消除了异构型的缺陷，结构的统一化使管理变得容易，但若多数结点的度小于树的度，则部分指针域为空，造成存储空间的浪费。38什么样的树在用同构型结构时，空链域最少？设有n个结点，度为d的树，用同构型结点存储整个链表共有指针域数有用的指针域数n*d个n-1个空的指针域数n(d-1)+1个R=空的指针域数整个链表共有指针域数=n(d-1)+1ndR=n→∞Limn→∞Limn(d-1)+1nd=1d1-K越小越好结论：d=2时，空链域最少二叉树关于树的结构讨论根结点的地址不占指针域degree——度想去掉结点个数的因素思考&讨论树链式存储——孩子兄弟表示法39树链式存储——孩子链表表示法40树链式存储——孩子链表表示法41实际问题中的树及抽象树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树的遍历树的应用广义表*CONTENTS5.15.25.35.45.55.65.75.843若我们能找到普通树转换为二叉树、二叉树又能还原成原来的普通树的方法，就完美地解决了这个问题。把二叉树作为典型的结构加以研究讨论，相应的结果能用到普通的树上面吗？二叉树普通树思考&讨论树转换为二叉树44树转换为二叉树的过程中各结点的联系有怎样的变化？树转换为二叉树45思考&讨论讨论：加线的过程，是增加了结点和兄弟的直接关联；去线的操作，是去掉了除长子之外的联系，但是可以通过长子的兄弟关系，间接得到所有孩子的信息，这个和前面介绍的“树链式存储-孩子兄弟表示法”是一样的原理。森林转换为二叉树46二叉树还原为树47树还原为二叉树的过程中各结点的联系有怎样的变化？思考&讨论一个结点x的左孩子其子孙，从来历上看，都是这个左孩子的兄弟，如图5.24中的FG点，都是E的子孙，EFG都是B的孩子，故加线是恢复结点与孩子的关系；去线是去掉兄弟间的连线，这样就可以恢复成原来的树结构了。树与二叉树的存储关系48树链式存储——孩子兄弟表示法495.4二叉树的逻辑结构5.4.15.4.2二叉树的概念二叉树的基本性质5.4.3二叉树的操作定义5.4二叉树的逻辑结构5.4.15.4.2二叉树的概念二叉树的基本性质5.4.3二叉树的操作定义52说明：二叉树是每个结点最多有两个子树的有序树。二叉树的子树通常称为“左子树”（leftsubtree）和“右子树”（rightsubtree）。左、右子树的顺序不能互换。二叉树的概念AFGEDCB二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念

二叉树是n(n≥0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。二叉树二叉树的概念53二叉树与树的区别是什么？思考&讨论讨论：尽管二叉树与树有许多相似之处，树和二叉树的两个主要差别：（1）树中结点的最大度数没有限制，而二叉树结点的最大度数为2；（2）树的结点无左、右之分，而二叉树的结点有左、右之分，二叉树的基本形态54二叉树的特殊形态——满二叉树55如果深度为k的二叉树，有2k-1个结点则称为满二叉树二叉树的特殊形态——完全二叉树56可以说满二叉树是完全二叉树的特例情形、(b)完全二叉树(c)不是完全二叉树二叉树的特殊形态——完全二叉树57完全二叉树5.4二叉树的逻辑结构5.4.15.4.2二叉树的概念二叉树的基本性质5.4.3二叉树的操作定义二叉树的基本性质59深度为h的二叉树至多有2h–1个结点（h

≥1）对任何一棵二叉树，若它含有n0个叶子结点、n2个度为2的结点，则必存在关系式：n0=n2+1FGCBADE在二叉树的第i层上至多有2i-1个结点（i≥1）性质1性质2性质3完全二叉树的性质60具有n个结点的完全二叉树的深度为：[log2n]+1若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：若i=1，则该结点是二叉树的根，无双亲，否则，编号为

i/2

的结点为其双亲结点；若2i>n，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；若2i+1>n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。123456FCBADE方括号表示取整性质4性质5完全二叉树的性质【例5-1】二叉树各种结点数目的计算若一个完全二叉树有n=1450个结点，则度为1的结点、度为2的结点、叶子结点个数分别是多少？有多少左孩子，多少右孩子？该树的高度是多少？解：树的高度：∵是完全二叉树

∴1～10层全满，k=10最下层叶子结点的个数=n-（2k

-1）=1450-1023=427k-1层带叶子的结点数=[427+1/2]=214k-1层结点数=2k-1=512k-1层叶子数=512-214=298∴总叶子数n0=427+298=725度为2的结点n2=n0-1=724度为1的结点n1=n-1-2n2=1450-1-2*724=1有左孩子结点数=度为2的结点数+度为1的结点数=725有右孩子结点数=度为2的结点数=72461二叉树的特殊形态——完全二叉树62完全二叉树k层最下层k-1层k-1层带叶子的结点k-1层带的叶子数5.4二叉树的逻辑结构5.4.15.4.2二叉树的概念二叉树的基本性质5.4.3二叉树的操作定义二叉树的操作定义构造建立一棵树，初始化查找查找指定条件的结点插入

删除在指定位置插入/删除结点遍历

对树中每个结点均做一次且仅做一次访问求深度计算树的高度实际问题中的树及抽象树的逻辑结构树的存储结构二叉树的逻辑结构二叉树的存储结构及实现树的遍历树的应用广义表*CONTENTS5.15.25.35.45.55.65.75.8普通树二叉树二叉树的存储结构及实现已讨论过一般形式树的存储方案简化对照树的一般形式来讨论二叉树的存储方案5.5二叉树的存储结构及实现5.5.15.5.2二叉树的顺序存储结构二叉树的链式存储结构5.5.3建立动态二叉链表二叉树顺序存储——结点间关系分析68二叉树顺序存储——结点间关系分析69二叉树顺序存储——结点位置分析70二叉树顺序存储——结点位置分析71完全二叉树存储方案是否适用一般的二叉树存储？将二叉树的所有结点，按照完全二叉树的编号方法进行编号，按序存储到一片连续的存储单元中。结点的顺序将反映出结点之间逻辑关系。二叉树的顺序存储思考&讨论二叉树顺序存储——结点位置分析72退化的二叉树的存储5.5二叉树的存储结构及实现5.5.15.5.2二叉树的顺序存储结构二叉树的链式存储结构5.5.3建立动态二叉链表二叉树的链式存储结构74

二叉树的每个结点含有两个指针域来分别指向相应的分支，称其为二叉链表二叉链表二叉树的链式存储结构75二叉树的每个结点含有两个指针域来分别指向相应的分支。二叉树的链式存储二叉树的三叉链存储结构76树的三重链表表示77静态二叉链表78ADBCFE021435孩子结点在数组中的位置。用-1表示无左孩子或右孩子采用数组存储的静态二叉链表5.5二叉树的存储结构及实现5.5.15.5.2二叉树的顺序存储结构二叉树的链式存储结构5.5.3建立动态二叉链表层次输入法创建二叉链表方法一80层次输入法创建二叉链表方法一81

Q队列元素A出列，A的下标i=1

将A的左孩子结点地址（在下标为2*i处）填入A结点的左指针域

将A的右孩子结点地址（在下标为2*i+1处）填入A结点的右指针域层次输入法创建二叉链表方法一82

Q队列元素A出列，A的下标i=1

将A的左孩子结点地址（在下标为2*i处）填入A结点的左指针域

将A的右孩子结点地址（在下标为2*i+1处）填入A结点的右指针域83层次输入法创建二叉链表方法一伪代码描述设二叉树的深度为k，则队列Q的长度至少为2k-1+1(队列的0下标位不用)生成树的所有结点，结点地址按结点编号顺序填入队列数组Q[]中队头元素下标i=1当Q队列i<k-1层元素个数(2k-1)

Q队列元素i出列将i的左孩子结点地址(下标2*i）填入i的左指针域将i的右孩子结点地址(下标2*i+1的结点）填入i的右指针域返回根结点地址层次输入法创建二叉链表方法二84

输入结点信息，若输入的结点不是虚结点，则建立一个新结点。若新结点是第1个结点，则令其为根结点，否则将新结点作为孩子链接到它的双亲结点上。如此反复进行，直到输入结束标志“＃”为止层次输入法创建二叉链表方法二85

输入结点信息，若输入的结点不是虚结点，则建立一个新结点。若新结点是第1个结点，则令其为根结点，否则将新结点作为孩子链接到它的双亲结点上。如此反复进行，直到输入结束标志“＃”为止86层次输入法创建二叉链表方法二伪代码细化描述设二叉树的深度为k，则队列Q的长度设置按完全二叉树编号至树的最后一个结点当输入结点信息不是结束标志‘#’若输入的结点不是虚结点，则建立一个新结点并入队若新结点是第1个结点，则令其为根结点，否则将新结点作为孩子链接到它的双亲结点上。若新结点是双亲结点的右孩子，则双亲结点出队。返回根结点地址87层次输入法创建二叉链表方法二功能描述输入输出CreaTree无根地址函数名形参函数类型

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;数据结构设计函数框架设计层次输入法创建二叉链表方法二/*===============================================函数功能：层次输入法创建二叉链表函数输入：无函数输出：二叉链表根结点键盘输入：按完全二叉树结点编号规则顺序输入结点值，空结点为@====================================================*/885.6树的遍历5.6.15.6.2树的广度优先遍历树的深度优先遍历5.6.3树的遍历的应用引例1——机电设备通电自检模型90设备通电自检步骤应该如何进行检测步骤：左子树：网卡等正常→PCI正常→显卡等正常→非PCI正常→板卡正常右子树：硬盘等正常→外存正常→键盘等正常→其他正常→非板卡正常整棵树：板卡正常→非板卡正常→计算机正常在上述的检测过程中，“后序遍历”的意思是指树的根结点是最后被访问到的，无论是整棵树还是左右子树。“后序遍历”引例2——网购商品的管理91FoodMeatPorkBeefFruitYellowBananMangoRedCherry如何打印商品清单“先序遍历”根结点：Food左子树：Meat→Pork/Beef右子树：Fruit→（左子树）Yellow→Banan/MangoFruit→（右子树）Red→Cherry引例3——树中结点的快速查找策略92“中序遍历”如何得到有序序列？二分查找递归过程根为1的树：左子树（空）→根1→右子树（2）→结果为1、2根为3的树：左子树（1,2）→根3→右子树（4,5）→结果为1、2、3、4、5根为9的树：左子树（7,8）→根9→右子树（10,11）→结果为7、8、9、10、1193遍历的基本概念对结点的处理。如修改结点数据、输出结点数据。

按某种顺序访问数据结构中的结点，要求每个结点访问一次且仅访问一次。遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。如何访问二叉树的每个结点，而且每个结点仅被访问一次？CBADFE遍历访问94遍历的基本概念——基本遍历策略广度遍历(Breadth-FirstSearch)深度遍历(Depth_FirstSearch)5.6树的遍历5.6.15.6.2树的广度优先遍历树的深度优先遍历5.6.3树的遍历的应用基于顺序存储结构的树的广度优先遍历96广度遍历（层次遍历）方法：从上到下、从左到右访问各结点适用于顺序存储结构

基于链式存储结构的二叉树广度优先遍历97基于链式存储结构的二叉树广度优先遍历98(1)初始化一个队列，并把根结点入列队；

(2)队列元素出队，取得一个结点，访问该结点；

(3)若该结点的左孩子非空，则将该结点的左子树入队列；

(4)若该结点的右孩子非空，则将该结点的右子树入队列；(5)循环执行步骤2到4，直至队列为空。算法描述基于链式存储结构的二叉树广度优先遍历99二叉树结点结构描述typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*Q[MAXSIZE];//设数组Q做队列，队列元素类型为二叉链表结点类型功能输入输出层次遍历二叉树leverOrder二叉链表根结点地址无函数名形参函数类型函数框架设计数据结构设计基于链式存储结构的二叉树广度优先遍历/*=====================================函数功能：层次遍历二叉树，打印遍历序列函数输入：二叉链表根结点地址bitree*Ptr函数输出：无=======================================*/1005.6树的遍历5.6.15.6.2树的广度优先遍历树的深度优先遍历5.6.3树的遍历的应用树的深度优先遍历102深度优先遍历方法深度优先遍历递归算法深度优先遍历非递归算法树的深度优先遍历103深度优先遍历方法深度优先遍历递归算法深度优先遍历非递归算法深度优先遍历方法104先左后右：DLR，LDR，LRD先右后左：DRL，RDL，RLD105深度优先遍历方法先序遍历（DLR）中序遍历（LDR）后序遍历（LRD）深度遍历策略——先序遍历106若二叉树非空，则依次进行以下操作（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；深度遍历策略——中序遍历107若二叉树非空，则依次进行以下操作（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；深度遍历策略——后序遍历108若二叉树非空，则依次进行以下操作（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点；用投影法理解树的遍历109用投影法理解树的遍历110用投影法理解树的遍历111先序遍历的例子112先序遍历的例子113情形圈中表示DLR序列情形圈中表示DLR序列1树的根A6A的右子树继续细化2A的左子树继续细化7A右子树的根E3A左子树的根B8E的右子树继续细化4B的右子树继续细化9E的右子树的根F5B的右子树的根C10F的左子树GHK4'B的右子树CD8'E的右子树FGHK2'A的左子树BCD6'A的右子树EFGHK中序遍历的例子114中序遍历的例子115情形圈中表示LDR序列情形圈中表示LDR序列1A的左子树继续细化6A的右子树继续细化2A的左子树的根B7A的右子树的根E3B的右子树继续细化8E的右子树继续细化4C的左子树的根D9F的左子树HGK3'B的右子树DC8'E的右子树HGKF1’A的左子树BDC6'A的右子树EHGKF5树的根A

后序遍历的例子116后序遍历的例子情形圈中表示LDR序列情形圈中表示LDR序列1A的左子树继续细化5E的右子树继续细化2B的右子树继续细化6F的左子树HKG3C的左子树的根D5'E的右子树HKGF2'B的右子树DC4'A的右子树HKGFE1'A的左子树DCB7树的根A4A的右子树继续细化

117深度优先遍历递归算法118深度优先遍历方法深度优先遍历递归算法深度优先遍历非递归算法先序遍历的递归算法119功能描述输入输出输出DLR遍历序列PreOrder根地址无函数名形参函数类型伪代码描述输入：树的当前根结点t；设树的结点指针bitree*t递归的边界条件：t为空结点，返回；递归继续的条件：访问t结点；

前序遍历t的左子树；

前序遍历t的右子树；函数框架设计先序遍历的递归算法120typedefstructnode{ datatypedata; structnode*lchild,*rchild;}BinTreeNode;数据结构设计先序遍历的递归算法/*=================================函数功能：先序遍历树的递归算法函数输入：树的根结点函数输出：无屏幕输出：树的先序遍历序列====================================*/121DLR递归过程示意图122中序遍历的递归算法/*=============================函数功能：中序遍历树的递归算法函数输入：树的根结点函数输出：无屏幕输出：树的中序遍历序列===============================*/voidinorder(BinTreeNode*t){if(t){inorder(t->lchild);putchar(t->data);inorder(t->rchild);}}123后序遍历的递归算法/*=====================================

函数功能：后序遍历树的递归算法

函数输入：树的根结点

函数输出：无

屏幕输出：树的后序遍历序列======================================*/voidpostorder(BinTreeNode*t){if(t)

{

postorder(t->lchild);postorder(t->rchild);putchar(t->data);}}124遍历的分析125二叉树遍历路径图从根结点出发到终点的路径上，每个结点经过3次“左手扶墙”法第一次经过A1B1C1D1E1————先序遍历ABCDE第二次经过B2D2C2A2E2————中序遍历BDCAE第三次经过D3C3B3E3A3————后序遍历DCBEA用遍历的方法建立二叉链表【例5-3】用遍历的方法建立二叉链表解：算法基本思想，按先序遍历顺序，建立二叉链表的所有结点并完成相应结点的链接。树的先序序列为ABD@F@@@CE@@@126用遍历的方法建立二叉链表【例5-3】用遍历的方法建立二叉链表/*=========================================函数功能：用先序遍历的方法建立二叉链表函数输入：（二叉链表根结点）函数输出：二叉链表根结点键盘输入：树的先序遍历序列,子树为空时输入@============================================*/ 127树的深度优先遍历128深度优先遍历方法深度优先遍历递归算法深度优先遍历非递归算法深度优先遍历非递归算法129递归非递归利用一个栈来记录尚待遍历的结点，以备以后访问栈可以将递归的深度优先遍历改为非递归的算法。

递归的深度优先遍历130深度优先遍历非递归算法非递归先序遍历非递归中序遍历非递归后序遍历非递归先序遍历131算法设计（1）当前指针指向根结点；（2）打印当前结点，当前指针指向其左孩子并进栈，重复(2)，直到左孩子为NULL；（3）依次退栈，将当前指针指向右孩子；（4）若栈非空或当前指针非NULL，执行（2），否则结束。对二叉树各结点的访问顺序是沿其左链一路访问下来，在访问结点的同时将其入栈，直到左链为空。然后结点出栈，对于每个出栈结点，即表示该结点和其左子树已被访问结束，应该访问该结点的右子树。非递归前序遍历/*==================================函数功能：先序遍历树的非递归算法函数输入：树的根结点函数输出：无屏幕输出：树的先序遍历序列=========================================*/132非递归中序遍历133算法设计

遇到一个结点，就把它压入栈中，并去遍历它的左子树。遍历完左子树后，结点出栈并访问之，然后按照它的右链接指示的地址再去遍历该结点的右子树。

非递归后序遍历134

遇到一个结点，压栈遍历结点的左子树遍历结点的右子树出栈该结点并访问之给栈中的每个元素加上一个特征位特征为Left表示已进入该结点的左子树，将从左子树返回特征为Right表示已进入该结点的右子树，将从右子树返回

算法设计树的遍历程序的测试/*=========================================测试功能：树的各种遍历算法测试测试函数： 1.用先序遍历的方法建立二叉链表CreatBTree_DLR 2.非递归先序遍历序列PreOrder_NR 3.递归先序遍历序列PreOrder 4.递归中序遍历序列inorder 5.递归后序遍历序列postorder==========================================*/1355.6树的遍历5.6.15.6.2树的广度优先遍历树的深度优先遍历5.6.3树的遍历的应用137树的遍历的应用求二叉树深度统计叶子数目138树的遍历的应用求二叉树深度统计叶子数目树的遍历的应用139二叉树的深度是二叉树中结点层次的最大值。可通过先序遍历来计算二叉树中每个结点的层次,其中的最大值即为二叉树的深度。求二叉树深度求二叉树深度2——先序遍历法140DLR序列ABDEGHCF层数leve12334423最大高度h12334444求二叉树深度1——先序遍历法141按先序遍历的方式求二叉树深度输入：树的当前根结点；树的当前根结点所处的层数leve设树的结点指针bitree*p，树的高度h，树的层数leve递归的边界条件：P为空结点，返回h；递归继续的条件：leve增1，h取左右子树中leve的大者

p的左孩子非空，先序遍历p的左孩子；

p的右孩子非空，先序遍历p的右孩子；求二叉树深度1——先序遍历法/*===================================================函数功能：按先序遍历的方式求二叉树深度函数输入：根结点函数输出：树的深度屏幕输出：（叶子结点值、层数、树的当前高度）——方便调试用=====================================================*/142求二叉树深度2——后序遍历法143DLR序列DGHEBFCA左子树高lh11122114右子树高rh11123123求二叉树深度2——后序遍历法144按后序遍历的方式求二叉树深度输入：树的当前根结点；设树的结点指针bitree*p，左子树的高度lh，右子树的高度rh递归的边界条件：p为空结点，返回0；递归继续的条件：p的左孩子非空，后序遍历递归求lh；

p的右孩子非空，后序遍历递归求rh；

返回左右子树中高度值大者把左右子树的高度分别记录在lh、rh两个变量中，即使它们都是局部量，但在每一层二者都是可比较的求二叉树深度2——后序遍历法/*================================================函数功能：按后序遍历的方式求二叉树深度函数输入：根结点函数输出：树的深度屏幕输出：（叶子结点值、左右子树高度）——方便调试用================================================*/145146树的遍历的应用求二叉树深度统计叶子数目树的遍历的应用147

利用遍历的方式来访问树的各个结点，由于叶子结点的特殊性，因此可以统计出一棵树中叶子的数目。叶子结点判断条件：root->lchild==NULL&&root->rchild==NULL或者：!root->lchild&&!root->rchild统计叶子数目求叶子结点数1——先序遍历法【例5-4】统计二叉树中叶子结点的数目并打印出叶子结点的值。解：若结点root的左右指针均空，则为叶子。可选用任何一种遍历算法查找叶子，将其统计并打印出来。

【方法一】用先序遍历递归法求树的叶子结点的数目148求叶子结点数1——先序遍历法149/*============================================函数功能：用先序遍历递归法求树的叶子结点的数目函数输入：二叉树根结点函数输出：无（通过全局量传递叶子结点的数目）屏幕输出：叶子结点值=============================================*/求叶子结点数2——递归法150/*====================================函数功能：递归求树的叶子结点的数目函数输入：根结点地址函数输出：叶子结点数目=======================================*/intLeafNum(BinTreeNode*root){ if(root==NULL)return(0); elseif(root->lchild==NULL&&root->rchild==NULL) return(1); elsereturn(LeafNum(root->lchild)+LeafNum(root->rchild));}

求叶子结点函数的测试/*============================================测试功能：求叶子结点的数目的测试测试函数：1.递归求树的叶子结点的数目LeafNum2.用先序遍历递归法求树的叶子结点的数目LeafNum_DLR===============================================*/1515.7树的应用5.7.15.7.2表达式树线索二叉树5.7.3哈夫曼树及哈夫曼编码树的应用153树基本操作扩展/限定条件树的应用树的应用，可以说是在树的结构及基本操作基础上增加各种扩展或限定条件后，形成的特定使用方法。本节介绍一些经典的应用，重点介绍哈夫曼树。关于树的查找的相关内容将在查找一章介绍。5.7树的应用5.7.15.7.2表达式树线索二叉树5.7.3哈夫曼树及哈夫曼编码表达式树155在计算机内，使用后缀表达式易于求值。表达式树【例5-5】输入一个算术表达式，输出表达式的表达式树。（假设输入的表达式为合法表达式，判断该表达式是否合法部分略）表达式不合法有三种情况：①左右括号不匹配；②变量名不合法；③运算符两旁无参与运算的变量或数。156表达式树【例5-5】输入一个算术表达式，输出表达式的表达式树。157①设数组ex存放表达式串的各字符，lt、rt作为结点的左右指针，变量left、right用于存放每次取字符范围的左、右界。②设置左界初值为1；右界初值为串长度。③判断左右括号是否匹配，不匹配则认为输入有错误。④在表达式的左右界范围内寻找运算级别最低的运算符，同时判断运算符两旁有否参与运算的变量或数。若无，则输入表达式不合法；若有，作为当前子树的根结点，设置左子树指针及其左右界值，设置右子树指针及其左右界值。⑤若表达式在左右界范围内无运算符，则为叶子结点，判断变量名或数是否合法。⑥转④，直到表达式字符取完为止。5.7树的应用5.7.15.7.2表达式树线索二叉树5.7.3哈夫曼树及哈夫曼编码问题引入159递归方法借助栈的非递归方法二叉树遍历方法二者本质都要用栈问题引入160相比递归模式的二叉树运算，非递归模式具有更广泛的应用面。“少跳转、无堆栈、非递归”时间空间受限的系统如嵌入式系统或片上系统对算法的要求嵌入式系统完全嵌入受控器件内部的、为特定应用或专门用途而设计的专用计算机系统。片上系统：将一个完整的系统（产品）的各个功能集成在一个芯片上或一组芯片上。传统的与数据结构相关的算法，大多面向软件层面的需求，较少顾及硬件层面的考虑。随着硬件体系结构的扩展及其开发技术的发展，尤其是近年来可重构计算系统的迅速发展，“硬件的软化”、“软件的硬化”以及“芯片级程序设计技术”等成为当代程序与算法设计的—个重要方向，硬件系统设计已经不可避免地涉及到了数据结构的基本问题。二叉树结点前趋后继的查找问题161“前趋后继关系”基于树遍历的结果而言“双亲孩子关系”基于树结构定义而言遍历二叉树的结果是:求得结点的一个线性序列。二叉树结点关系二叉树结点前趋后继的查找问题162

采用树的线性存储方式解决结点的前趋或后继的查找，有什么问题？在二叉链表中查找结点的前趋后继方便吗？二叉链表线索化的实现163【方案一】增加前趋后继指针域可以增加二叉链表结点中的指针域来存放前趋和后继结点信息，其中Lthread表示前趋结点的地址，Rthread表示后继结点的地址。二叉链表线索化讨论164结点前趋左孩子右孩子后继A空BDBBA空CCCB空空DDC空EEEDF空FFE空空空前趋、后继线索与孩子指针的信息是否有重复的地方？增加两个指针域记录前趋后继先序遍历中，结点的孩子或者没有，或者与后继是一样的————可以考虑利用原结点的指针域来存储前趋、后继的线索。二叉链表线索化讨论165利用原结点的指针域的方案是否能区分孩子还是线索？无法区分用空链域记录前趋/后继的位置ADECBF【方案二】利用原结点的指针域二叉链表线索化讨论166改进的方案利用原结点的指针域的方案是否能保证所有前趋的线索都被记录？存在结点有左孩子而无法记录其前趋的状况，如结点E，其前趋D的地址没有指针域记录，但对于先序遍历而言，只要有结点的后继线索即可，因此，前趋线索有“中断”不影响先序遍历的操作。167线索二叉树二叉树添加了直接指向结点的前趋和后继的指针的二叉树称为线索二叉树。线索二叉树根据线索内容的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。线索二叉树168结点的标志Ltag与Rtag用来标示相应的指针域存储的是线索或孩子线索二叉树【例5-6】画出图中二叉树的中序二叉链表和中序线索二叉树。解：求出二叉树的中序遍历序列为BCADFE（1）按照二叉树的形状，画出二叉链表；（2）按照线索二叉树结点定义，画出线索域的指向；169线索二叉树170如何在线索二叉树的遍历序列中找结点的前趋和后继结点？BCADFE前趋标志110110前趋空B左子树最后结点CAD左子树最后结点F后继标志010011后继右子树最左结点CA右子树最左结点D右子树最左结点FE空右线索标志为1：右孩子为后继右线索标志为0：右子树最左结点为后继右子树最左结点：中序遍历右子树时访问的第一个结点左线索标志为1，左孩子为前趋左线索标志为0，左子树最右结点为前趋左子树最右结点：中序遍历左子树时访问的最后一个结点由线索二叉树得到遍历序列的方法171由中序遍历线索二叉树得到中序遍历序列的方法：访问根结点找根的前趋序列找根的后继序列由先序遍历线索二叉树得到先序遍历序列的方法：访问根结点找根的后继序列由后序遍历线索二叉树得到后序遍历序列的方法：访问根结点找根的前趋序列线索化方法172线索化的过程——在遍历过程中修改空指针在遍历过程中将二叉树线索化5.7树的应用5.7.15.7.2表达式树线索二叉树5.7.3哈夫曼树及哈夫曼编码通信中的编码问题174数字通信系统模型信息发布者信息接收者信源编码——将信源发出的消息符号转换为适合信道传输的符号。信源译码——按照编码的逆过程，将信息还原为原来的形式。二元信道(常用)等长二元编码设计175【例5-7】等长二元编码设计设一个信源符号集只有A、B、C、D四种字符，为区分不同的字符，设每个字符需要的二进制编码位数为n：∵4=2n∴n=2所谓数据编码就是数据与二进制字符串的转换等长编码问题讨论176在实际应用中，有些字母（如e,s,t）出现频率很高，有些字母出现频率很低。如果对所有字母重新编码，用比较少的bit表示出现次数高的字母，用比较多的bit表示出现次数低的字母，这样就应该可以用比较小的储存空间存相同的信息，使得总的报文码长缩短，提高通信效率。已知电文中出现的一组字符及出现频率，试为该组字符编码以使得电文总长最短。等长编码的效率如何？不等长二元编码设计177译码结果不唯一，原因是什么？【例5-8】不等长二元编码设计译码结果讨论178译码具有唯一性的必要条件——任一个字符的编码都不是另一个字符的编码的前缀译码树译码问题是一个字符串的查找问题，即串的多模式匹配问题字符结点不能出现分支结点上译码结果讨论179哈夫曼编码哈夫曼树180哈夫曼树与哈夫曼编码哈夫曼树的概念哈夫曼树构造算法哈夫曼树的算法实现哈夫曼编码哈夫曼树的译码哈夫曼树的应用181哈夫曼树与哈夫曼编码哈夫曼树的概念哈夫曼树构造算法哈夫曼树的算法实现哈夫曼编码哈夫曼树的译码哈夫曼树的应用哈夫曼树的概念182DCAB4752路径

结点的权

结点的带权路径长度树的带权路径长度

(WeightedPathLength)从一个结点到另一个结点之间的若干个分支具有一定含义的比例系数。如“词频”路径长度

路径上的分支数目称为路径长度结点的路径长度

从根到该结点的路径长度从根到该结点的路径长度与该结点权的乘积n——叶子结点的数目Wi——第i个叶结点的权值，i=1,2,...nLi——第i个叶结点的路径长度，i=1,2,...n哈夫曼树183DCAB4752CDAB4752

用n（n>0）个带权值的叶子来构造二叉树，限定二叉树中除了这n个叶子外只能出现度为2的结点，那么符合这样条件的二叉树往往可构造出许多棵，其中带权路径长度最小的二叉树就是哈夫曼树或最优二叉树。哈夫曼树哈夫曼树184185哈夫曼树与哈夫曼编码哈夫曼树的概念哈夫曼树构造算法哈夫曼树的算法实现哈夫曼编码哈夫曼树的译码哈夫曼树的应用哈夫曼树的构造186【例5-9】构造哈夫曼树构造以W=（6，5，3，4）为权的哈夫曼树，和构造以W=（7，2，4，5）为权的哈夫曼树。187哈夫曼树与哈夫曼编码哈夫曼树的概念哈夫曼树构造算法哈夫曼树的算法实现哈夫曼编码哈夫曼树的译码哈夫曼树的应用哈夫曼树的算法实现188typedefstruct //结点结构体{chardata; //结点值intweight; //权值intparent; //双亲结点intlchild; //左孩子结点intrchild; //右孩子结点}HTree_Node;数据结构设计Weightparentlchildrchild哈夫曼树表结构哈夫曼树的算法实现189函数框架设计功能描述输入输出构造Huffman树n个权值哈夫曼树函数名形参函数类型/*=======================================函数功能：创建哈夫曼树函数输入：（哈夫曼树）函数输出：（哈夫曼树）=========================================*/哈夫曼树的构造算法190191哈夫曼树与哈夫曼编码哈夫曼树的概念哈夫曼树构造算法哈夫曼树的算法实现哈夫曼编码哈夫曼树的译码哈夫曼树的应用哈夫曼编码192在已建立的哈夫曼树中，沿叶子结点的双亲路径回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路径上各分支所组成的0，1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。

若规定哈夫曼树中的左分支代表0，右分支代表1；则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码。哈夫曼编码方法哈夫曼编码193从叶子结点L开始，找其双亲F，根据F判断L是F的左孩子还是右孩子左孩子：编码为0（or1）右孩子：编码为1（or0）设L=F，重复上述过程，直到A为根结点(得到的编码是从低位到高位)哈夫曼编码194在已建立的哈夫曼树中，沿叶子结点的双亲路径回退到根结点，每回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路径上各分支所组成的0，1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码为所求编码的高位码。哈夫曼编码/*==========================================函数功能：哈夫曼符号集编码函数输入：哈夫曼树、（哈夫曼码编码表）函数输出：（哈夫曼编码表）=============================================*/195196哈夫曼树与哈夫曼编码哈夫曼树的概念哈夫曼树构造算法哈夫曼树的算法实现哈夫曼编码哈夫曼树的译码哈夫曼树的应用哈夫曼树的译码197

从哈夫曼树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束。哈夫曼译码方法哈夫曼树的译码198从根结点A开始，根据电文找其孩子B：编码为0，B为左孩子；编码为1，B为右孩子。设B=A重复以上过程，直到B为叶子结点。哈夫曼树的译码——程序199/*====================================函数功能：将哈夫曼码翻译为字符函数输入：哈夫曼树、哈夫曼编码函数输出：无======================================*/哈夫曼树的译码——测试程序/*=======================================函数功能：输出哈夫曼编码表函数输入：哈夫曼树、哈夫曼码编码表函数输出：（哈夫曼码编码表）屏幕输出：哈夫曼树、哈夫曼码编码表=========================================*/200哈夫曼树的译码——测试程序/*============================================

函数功能：对给定字符串进行编码

函数输入：哈夫曼树、哈夫曼码编码表

函数输出：无

键盘输入：要编码的字符串

屏幕输出：输入字符串的哈夫曼编码串===============================================*/201202哈夫曼树与哈夫曼编码哈夫曼树的概念哈夫曼树构造算法哈夫曼树的算法实现哈夫曼编码哈夫曼树的译码哈夫曼树的应用哈夫曼树应用举例——最佳判定算法203【例5-10】哈夫曼树的应用——最佳判定算法编制一个程序，将百分制转换成优秀、良好、中等、及格、不及格5个等级输出。哈夫曼树应用举例——最佳判定算法204这样的转换效率高不高？有80%的数据需要进行三次或三次以上的比较才能得出结果思考&讨论哈夫曼树应用举例——最佳判定算法205这样的改进，算法效率真的提高了么？每个结点的比较次数增加了哈夫曼树应用举例——最佳判定算法206605.8广义表5.8.15.8.2广义表的定义广义表的存储5.8.3广义表的基本运算你去过哪里旅游？208形式1：国家(直辖市，省(城市1，城市2，...城市n))形式2：洲名(国家(城市1，城市2，...城市n))包含子结构的线性结构，线性表的推广——广义表中国(

北京,上海,

江苏(南京,苏州),

浙江(杭州，宁波)，

陕西(西安，咸阳，宝鸡))欧洲(

荷兰(阿姆斯特丹，埃因霍温)，

比利时(布鲁塞尔)，

法国(巴黎)，

英国(伦敦))线性表及相关形式2095.8广义表5.8.15.8.2广义表的定义广义表的存储5.8.3广义表的基本运算广义表定义211说明：

广义表名——LS

表头——广义表LS非空时，称第一个元素为LS的表头。

表尾——广义表LS中除表头外其余元素组成的广义表。

长度——广义表LS中的直接元素的个数。

深度——广义表LS中括号的最大嵌套层数。原子的深度为0，空表的深度为1。

单元素——ai可以是单个的数据元素，单元素也称为原子，是指结构上不可再分的一个数或一个结构。

子表——ai可以是一个广义表。

广义表是n（n≥0）个数据元素的有限序列，记作：LS=(a1，a2，……，an)广义表广义表特性1）广义表是一个多层次的结构。因为广义表的元素可以是一个子表，而子表的元素还可以是子表。2）一个广义表可以为其他广义表共享，这种共享广义表称为再入表；3）广义表可以是一个递归的表。一个广义表可以是自已的子表。这种广义表称为递归表。递归表的深度是无穷值,长度是有限值；4）广义表与树形结构相对应，这个广义表就是纯表。广义表是对线性表和树的推广。各种表的关系如下：线性表∈纯表（树）∈再入表∈递归表

212广义表表示法1213不带名字的广义表表示广义表表示法2214带名字的广义表表示广义表表示示例215广义表常用表示等价写法带名字的表示法表长原子子表说明E=()E()0无无E为空表L=(a，b)L(a，b)2a，b无L也是线性表A=(x，L)A=(x，(a，b))A(x，L(a，b))2xLB=(A，y)B=((x，(a，b))，y)B(A(x，L(a，b))，y)2yAC=(A，B)C=((x,(a,b)),((x,(a,b)),y))C(A(x，l(a，b))，B(A(x，L(a，b))，y))2无A,BD=(a，D)D=(a，(a，(a，(…))))D(a，D(a，D(…)))2aDD为递归表广义表的图形表示216广义表与其他数据结构的关系217（1）与线性表的关系当限定广义表的每一项只能是基本元素而非子表时，广义表就退化为线性表：(a1,a2,…,an)；（2）与二维数组的关系当将数组的每行（或每列）看作为子表时，数组即为一个广义表：((a11,a12,…,a1n),(a21,a22,…,a2n),…(an1,an2,…,ann))（3）与树的关系树也可以用广义表来表示。广义表的运算定义218创建广义表输出广义表求广义表的长度和深度从广义表中查找或删除元素5.8广义表5.8.15.8.2广义表的定义广义表的存储5.8.3广义表的基本运算广义表链式存储结构设计220广义表头尾表示法1——表头表尾分析法221广义表头尾表示法2——子表分析法222广义表表示法——兄弟孩子表示法223一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的，在广义表链式存储中，通常把此种存储方式称为“孩子兄弟表示法”224广义表头尾表示法结点设计表头指针hPtr：子表首结点的地址后继指针tPtr：存放同层后继结点链接地址标志tag——区分表结点和元素结点的标志；元素值data——存放原子的值。头尾表示法结点类型描述typedefenum{ATOM,LIST}ElemTag;

//ATOM==0:原子,LIST==1:子表TypedefstructGLNode{ElemTagtag;//标志域union

{AtomTypedata;struct{structGLNode*hPtr,*tPtr;}ptr;};}Glist;225226【例5-11】用表头表尾分解法给出广义表E=(a,(b,c,d))的链表存储形式图表头表尾分解法子表分解法227【例5-12】子表分解法给出广义表L=(a,(x,y),((z)))的链表存储形式图。广义表的孩子兄弟表示法228typedefenum{ATOM,LIST}ElemTag; //ATOM=0：单元素；LIST=1：子表typedefstructGLENode{ElemTagtag; //标志域，用于区分原子结点和表结点union{ //原子结点和表结点的联合部分AtomTypedata; //原子结点的值域structGLENode*firstchildPtr; //表结点的表头指针};structGLENode*siblingPtr; //指向下一个结点}GList //广义表类型广义表的孩子兄弟表示法229【例5-13】用孩子兄弟表示法表示下列各广义表的存储空表： A=()线性表： L=(a,b,c,d)纯表： D=(a,(b,c))纯表： D=(A,B,C)=((),(e),(a,(b,c)))再入表： G(d,L(a,b),T(c,L(a,b)))递归表： E=(a,E)230本章小结231树存储结构基本概念基本操作连续存储链式存储构造、查找插入、删除遍历、求深度等树的定义、表示形式相关术语：结点、孩子、祖先、子孙、层数、高度、结点的度、有序树、无序树逻辑特征分层非线性结构特例情形：二叉树本章小结232二叉树相关概念运算—遍历二叉树的定义特例：满二叉树、完全二叉树基本性质：结点、深度、层数等之间的关系广度优先深度优先遍历应用求深度统计叶子数目先序遍历中序遍历后序遍历运算—应用表达式树线索二叉树哈夫曼树与哈夫曼编码本章小结233树中有子树按层级排列前后辈分等级森严不能乱，二叉树形态最简，专门把它的特性仔细研：顺序表存结点联系隐藏在下标位里面；二叉链表很形象，分支结构联系记录在左右孩子域中间。

借队列建链表，线性结构把非线性关系存里边，树结点逐个出队，添加指针域，二叉链表即展现。

树的结构为递归，操作处理有方案两类：按层横向处理基于顺序表的结构上看，自根沿路径纵向处理基于链表按递归办，先中后序三遍历将左右孩子与根递归地把每个结点都只跑一遍。

本章小结234

树的应用介绍哈夫曼编码是重点。哈夫曼树带权路径长度为最小，设计异前缀编码方法巧妙堪经典。哈夫曼树构造方法，找结点权值最小次小加起来为根逐步完善，左分支为0，右分支为1做好标记，根到叶沿途的各01连起来即是叶上字符的编码串。发送的信息传输前要将报文按字符编码写成01的序列串，通过有线或无线传递到接收的一端，天书般的报文1001串组成其意难辨，

要译码到哈夫曼树上，从根开始沿着路径逐个儿分辨，遇0左拐遇1右转，千回百转直到叶子上破译的字符展现。（注：哈夫曼编码中，左分支为0，则右分支为1；或者左分支为1，右分支为0；两种方案都可以）

本章小结235

树中有树是递归的树，表中有表为广义的表；广义表含义广泛，把线性非线性各种关系统统包含，头尾法兄弟孩子法描述纷繁的结点联系真不简单。元素有原子与子表两类，类型大不同，存储起来可是有点麻烦，用标记巧区分，结点结构设计统一在union中间。

结点逻辑关系任意的非线性结构图Chapter

6DataStructuresandAlgorithmAnalysis主要内容图的逻辑结构定义图的存储结构图的遍历图的应用学习目标 熟练掌握图的逻辑结构特点 掌握图的存储结构 掌握图的遍历 熟悉图的相关应用实际问题中的图及抽象图的逻辑结构图的存储结构及实现图的基本操作图的遍历图中的树问题图中的最短路径问题活动顶点与活动边的问题CONTENTS6.16.26.36.46.56.66.76.8实际问题中的图及抽象图的逻辑结构图的存储结构及实现图的基本操作图的遍历图中的树问题图中的最短路径问题活动顶点与活动边的问题CONTENTS6.16.26.36.46.56.66.76.86.1实际问题中的图及抽象几何图与拓扑图242所有多边形和圆周在拓扑意义下是一样的圆和方形、三角形的形状、大小不同，在拓扑变换下，它们都是等价图形。几何图与拓扑图243图引例1——地图染色问题24431232334四色猜想

四色定理1852年英国人发现现象1976年美国人计算机证明每幅地图都最多可以用四种颜色着色图引例1——地图染色问题245图引例1——地图染色问题246信息与信息间的联系如何抽象后存储到计算机中陕西河南安徽湖北四川山西贵州湖南广东广西福建浙江江西江苏山东图引例2——搜索引擎与网站的结构247搜索引擎的工作原理是按照一定的搜索策略搜索网络并搜集信息，在对信息进行组织和处理后存储在自己的数据库中，以便为用户提供快速检索服务。完成网络信息搜索任务的软件俗称“网络蜘蛛”或“网络爬虫”，网络蜘蛛是通过网站的站内链接来遍历网站内容的。网站内链接结构图引例2——搜索引擎与网站的结构248（a）网站链接（b）网站间的链接抽象图引例2——搜索引擎与网站的结构249拓扑意义上的图用点表示对象，有直接联系的对象用线连接起来。图形中连线的长短曲直和结点的位置无关紧要，每一条线两端都有结点。

从实际问题中抽象出来的数据结构的“图”有什么特点？图引例3——最短航线问题250航线图城市：顶点={a,b,c,d,e}航线：顶点间连线={ab,ad,bc,be,de}问题描述：求出从d到c的最短航线。图引例4——电路图的表示方法251无向图和有向图把电路中每一条支路画成抽象的线段形成的一个结点和支路的集合，见图6.10，其中没有考虑电流方向的图为无向图，有向图的方向一般为该支路电流的参考方向图的讨论【思考与讨论】从实际问题中抽象出来的数据结构的“图”有什么特点？讨论：数据结构中的图是拓扑意义上的图，其特点为：

用点表示对象，有直接联系的对象用线连接起来。

图形中连线的长短曲直和结点的位置无关紧要，每一条线两端都有结点。252实际问题中的图及抽象图的逻辑结构图的存储结构及实现图的基本操作图的遍历图中的树问题图中的最短路径问题活动顶点与活动边的问题CONTENT