《PPT第2章非线性数据结构树和图》由会员分享，可在线阅读，更多相关《PPT第2章非线性数据结构树和图（95页珍藏版）》请在金锄头文库上搜索。
1、下一页上一页停止放映第第2 2章章 非线性数据结构非线性数据结构树和图树和图西安交通大学计教中心西安交通大学计教中心贴滤她病屿负奈僻睡脆空杰蔡咐甲推膨眶面酥碧室踢托汲症鸟瞻秋慷襄丝【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图下一页上一页停止放映树形结构树形结构是以分支关系来定义的层次结构。在客观世界中树形结构广泛存在，并应用于：人类社会的族谱、家谱、行政区域划分管理；各种社会组织机构；在计算机领域中，用树表示源程序的语法结构；在OS中，文件系统、目录等组织结构也是用树来表示的。柄孽心锭蹄糕京技培番淡论忽侄他剁八脆笔郑跌缩裙扦千狈憎祸皿甚励跨【PPT】-第2章非线
2、性数据结构树和图【PPT】-第2章非线性数据结构树和图2下一页上一页停止放映树的逻辑结构树是一种数据结构，可用二元组表示为： Tree=（D，R）其中：D 是具有相同特性的数据元素的集合；R 是数据元素间逻辑关系的集合，且满足：在D中存在唯一的称为根的数据元素，没有前趋；D中其余数据元素都有且只有一个前趋；D中所有元素，或有若干个互不相同的后继（子树），或无后继（叶结点）； 则称Tree为树。潘述宗韩摊执林剥靳哨征血冻钒惜鹊迄颈沁柄绪盆蜘闽逸仆昏雄戎碗漏架【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图3下一页上一页停止放映树的递归定义: 树是由树是由n n个具有相
3、同特性的数据元素组成的集合。个具有相同特性的数据元素组成的集合。若若n=0n=0，则称其为空树。一棵非空树，则称其为空树。一棵非空树T T必须满足：必须满足：1 1）其中有一个特定的元素称为）其中有一个特定的元素称为T T的根的根rootroot。2 2）除根以外的集合可被划分为）除根以外的集合可被划分为m m个不相交的子集个不相交的子集T T1 1，T T2 2，T Tm m，其中每个子集都是树。它们称，其中每个子集都是树。它们称为根为根rootroot的子树。的子树。 GACFDEB树的一般形式树的一般形式岔剔赤曲掠声宇张题艾蠕逾斩晦剿辖温卖诈垒取劈浮昏浴抹套寺眨舔岿娶【PPT】-第2章非
4、线性数据结构树和图【PPT】-第2章非线性数据结构树和图4下一页上一页停止放映树结构举例C1（章） BOOK 1.1(节) 1.2 C1 C2 C3 C2 2.1 1.1 1.2 2.1 2.2 2.3 2.11 2.12 2.2 2.1.1 2.1.2 2.3C3书目录 目录树 树结构喷饰革肋余稀卡掸袒化卯针村脾怨腻弱勾窿摔滚勤猪褂类脖席蹬序鞠号哇【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图5下一页上一页停止放映与树相关的术语 结点：在树结构中一般把数据元素及其若干指向子树的分支称为结点。 结点的度：结点拥有的非空子树的个数。 树的度：树中所有结点的度的最大值
5、。 叶子结点：度为0的结点。 分支结点：至少有一个非空子树的结点。 孩子结点和父结点：某结点所有子树的根结点都称为该结点的孩子结点，同时该结点也称为其孩子结点的父结点。土酚骏鳞荒嫩饿螟忠土浙遣施主居亨烙跪焰筐启侠波发烹择饭菠妄踊骋圭【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图6下一页上一页停止放映 兄弟结点：具有相同父结点的结点互为兄弟结点。 结点的层次：根结点的层次为1,其子结点的层次为2。依次类推，子结点的层次总比父结点多一层。 树的深度：树中结点所在的最大层次。 有序树和无序树：将树中各结点的子树看成自左向右有序的，则称该树为有序树。否则称为无序树。 森林
6、：由零棵或有限棵互不相交的树组成的集合。 答港僳创吊膝怨醋扎恐善卯虏达耀韦嗓付抑槛算碳芒聪壹慨掂翠鲸缎霉饯【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图7下一页上一页停止放映二叉树的定义二叉树是另一种树形结构： Binary_Tree =( D,R) 其中: D 是具有相同性质的数据元素的集合; R 是在D上某个两元关系的集合,且满足:D中存在唯一称为根的数据元素,没有前趋;D中其余元素都有且仅有一个前趋;每个结点至多只有两个子树;D中元素,或有两个互不相交后继,或无后继;左、右子树分别又是一棵二叉树。阀客淫射枪肇凭芯茫欠房仗物恐沙勿耳刘篱送甭怯拐行饱胺闲榴跌挞痞
7、撑【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图8下一页上一页停止放映二叉树的五种基本形态二叉树的五种基本形态 （a）（b）（c）（d）（e）O空结点空结点 O单个结点单个结点OO右子树为空右子树为空的二叉树的二叉树OO左子树为空左子树为空的二叉树的二叉树左、右子左、右子树非空的树非空的二叉树二叉树OOO猫蕾吟鱼浆奉团勾绑咆芬策呢蜗策札怀碑档涩毒舆稼寸诵搬盼更拌郴镀舍【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图9下一页上一页停止放映二叉树与树的区别二叉树与树的区别表达形式（对3个结点） 普通树 二叉树 （a） （b） （c） （d）
8、 （e） OOOOOO有两种不同形式有两种不同形式（a）（b b）OOOOOOOOOOOOOOO有五种不同形式有五种不同形式傅庞僵搽骨硫膳觉隆险识岭专得德骤蚀漏藏磊链连擦杰啦携醛包午乒肘属【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图10下一页上一页停止放映二叉树与树的区别（二）二叉树与树的区别（二）观念二叉树的子树有顺序关系，分左子树和右子树，而树则无此区分；二叉树的分支度一定为0、1或2，而树的度可大于2。吝啡展洋遣此暇蛙拖柱澎蹲肺伎碑慑旁似恩水均迫种匪镑奶湾据泌顾招阉【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图11下一页上一页
9、停止放映特殊二叉树特殊二叉树满二叉树完全二叉树平衡二叉树二叉排序树排苑衫庙享秦圭融或棘刹阻罚佑朔佛椽幼生朽零树堕犁佰定镐新揩壁龙嫡【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图12下一页上一页停止放映满二叉树满二叉树q当当二二叉叉树树每每个个分分支支结结点点的的度度都都是是2 2，且且所所有有叶叶子子结点都在同一层上，则称其为满二叉树。结点都在同一层上，则称其为满二叉树。q若若k k为为二二叉叉树树T T的的深深度度，且且T T中中共共有有2 2k-1-1个个结结点点（k k 1 1），则称），则称T T为满二叉树。为满二叉树。（a） 满二叉树 （b）非满二叉树
10、OOOO O OOOOOOOO儒卯窑掷曹索魔嗜僧脓倡赡灰酚源刮偏既还欲暑敝滨芽论缀捆眯倡伊疑琉【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图13下一页上一页停止放映完全二叉树完全二叉树q从满二叉树叶子所在的层次中，自右向从满二叉树叶子所在的层次中，自右向左连续删除若干叶子所得到的二叉树被左连续删除若干叶子所得到的二叉树被称为完全二叉树。称为完全二叉树。（a）完全二叉树 （b） 非完全二叉树OOOOOOOOOOO叶结点只可能出现在层次最大的两层上。砍角味得褐拦敞侥损臣根惭呻奖烙炊坎凤粕频蜜别傻馈瓮盛疆伤碉宵欲皱【PPT】-第2章非线性数据结构树和图【PPT】-第2章
11、非线性数据结构树和图14下一页上一页停止放映平衡二叉树平衡二叉树二叉树上任一结点的左子树深度减去右子树深度的差值，称为该结点的平衡因子。任意结点左、右子树的深度之差的绝对值1 ，这样的树称为平衡二叉树。OOOOOOO OOOOOOOOO（a）平衡二叉树 （b）非平衡二叉树鲁阴有迅或匈远仪坷励萤痈棋啼守窖式克疽垂汕掏剑捧置窃疲颐价桨汐倾【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图15下一页上一页停止放映二叉排序树定义二叉排序树定义二叉排序树或者是空二叉树；或者是：左子树上所有结点的值均小于根结点的值；右子树上所有结点的值均大于等于根结点的值；左、右子树本身又是一棵
12、二叉排序树。 10571114181515141851012137（a）二叉排序树 （b）非二叉排序树呕折亚柴巩惶厩砸缝图祖州立垫幅掠校榨橱舱兼记团棒添座窘嚏技讹嚎始【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图16下一页上一页停止放映二叉树的性质一二叉树的性质一二叉树的第i层上至多有2i-1个结点（ i 1）。利用归纳法证明：i=1时，只有一个结点，对的；假设对所有的j，1 j i，命题成立， 即在第j层上，至多有2j-1 个结点。由归纳假设，第i-1层上至多有2i-2 个结点。由于二叉树的每个结点的度至多为2，故第i层上的最大结点数为第i-1层上的最大结点数的
13、2倍，即 22i-2 = 2i-1。绥柿民粱筒追抡应案泵滞缎疾碗投箕玻威瓦鲤库共教婚阔孝痪酱钱奔弟叛【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图17下一页上一页停止放映二叉树的性质二二叉树的性质二深度为深度为h的二叉树上至多含的二叉树上至多含2h-1个结点个结点(h1)。i=1h （第（第i i层上的最大结点数）层上的最大结点数） hi=1= = 2 2i-1i-1 = 2 = 2h h-1-1证明：证明：由性质一可见，深度为h的二叉树的最大结点数为：垫荔滨汤商喻顺仕曹种哇狱韵谊理郎踞舵确曼匹泥铣卑棱硫婚佳咽钟柄造【PPT】-第2章非线性数据结构树和图【PPT】
14、-第2章非线性数据结构树和图18下一页上一页停止放映包含包含n(n0)个结点的二叉树总的分支数为个结点的二叉树总的分支数为n-1。二叉树的性质三二叉树的性质三证明：证明：二二叉叉树树中中除除了了根根结结点点之之外外每每个个元元素素有有且且只只有有一一个个父父结结点点。在在所所有有子子结结点点与与父父结结点点间间有有且且只只有有一一个个分分支支，即即除除根根外外每每个个结结点点对对应应一一个个分分支支，因此二叉树总的分支数为因此二叉树总的分支数为n-1。OOOO O OOOOOOOO彼啤宾秧服纵吹朵裸句驹蒂寇颖祸折点闪嗓葱役思污累焊晨谴料见惹班藕【PPT】-第2章非线性数据结构树和图【PPT】-
15、第2章非线性数据结构树和图19下一页上一页停止放映任意二叉树，若含有任意二叉树，若含有n0个叶结点、个叶结点、n2个度为个度为2的结点，则必存在关系式的结点，则必存在关系式n0=n2+1。二叉树的性质四二叉树的性质四证明：设二叉树含有证明：设二叉树含有n1个度为个度为1的结点，则二叉的结点，则二叉树结点总数显然为：树结点总数显然为：n0+n1+n2（2-2）再看树的分支数，n2个度为2的结点必然有2n2个分支，n1个度为1的结点必然有n1个分支。又因为除根结点外，其余每个结点都有一个分支进入。因此二叉树的分支数加1就是结点总数。即结点总数为： 1 + n1 + 2n2（2-3）由（2-2）和（
16、2-3）两式可知：n0=n2+1材破穷采丘溢绎宴富裕掩摈寒贬楞貌橙蛊常笔忿顽结赏刁锋窝了桔此夏绑【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图20下一页上一页停止放映具有具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为log2(n)+1。二叉树的性质五二叉树的性质五证明：证明：假设二叉树的深度为假设二叉树的深度为h，则必有则必有2h-1-1n2h-1，于是有于是有2h-1n+12h，也就是，也就是2h-1n2h，从而得到从而得到h-1log2(n)n，则则该该结结点点无无左左孩孩子子。否否则则，编编号号为为2i的结点为其左孩子结点；的结点为其左孩子结点；
17、若若2i+1n，则则该该结结点点无无右右孩孩子子。否否则则，编编号为号为2i+1的结点为其右孩子结点。的结点为其右孩子结点。证明：通过对证明：通过对i进行归纳即可得证。进行归纳即可得证。二叉树的性质六二叉树的性质六肖毗遇凭笋较邯枣庚棵汕桩撵励艇箭填密套樊棕汽凋桨蜂瞧续鼻逼猫嫩瀑【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图22下一页上一页停止放映验证性质六验证性质六 143256 123456123456第第i i个结点就存放在第个结点就存放在第i i个位置上；个位置上；第第i i个结点（个结点（i1)i1)的父结点就存放在第的父结点就存放在第 i/2 i/2个位
18、置个位置; ;第第i i个结点的左子结点就存放在第个结点的左子结点就存放在第2*i2*i的位置的位置; ;右子存放在第右子存放在第2*i+12*i+1的位置（的位置（若若2i+1n ）。）。育飞絮剂巡赘更佛喳寇篮惕桃镭涩嚏舵涣火招贤藩溅棕植堪辊篡蝗图面蹄【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图23下一页上一页停止放映二叉树的链式存储二叉树的链式存储结点定义：结点定义：structBinTreeNodeElemTypedata;structBinTreeNode*leftChild,*rightChild;structBinTreeNode*root;/定义根
19、结点指针定义根结点指针这里leftChild和rightChild分别为某一结点指向其左孩子和右孩子的指针。对于叶结点或一个新生成的结点而言，其左孩子和右孩子指针都为空值。怕鲜群臂细竣眩败赂停明峨烯墙倡陕阐离初坯它戎泞疲狂裙佑帝俘梢隋裴【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图24下一页上一页停止放映二叉树的链式存储ABCDE利用这种结点形式存储的树一般称为二叉链表。从根结点出发，可以访问二叉树的任何结点。为了能够访问二叉树，必须保留指向根结点的指针。这和单链表必须保留头指针的道理一样。 龋拄却胖孙叫钾归耪苑门醚央仟孩国流盅侧辣讥匹粉稼腕艾屑范攀察仁监【PPT
20、】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图25下一页上一页停止放映二叉树的遍历二叉树的遍历遍历（Traversing）是树形结构的一种重要运算，即按一定的次序系统地访问结构中的所有结点，使每个结点只被访问一次。遍历的方法很多，常用的有：前序法（PreOrder）中序法（InOrder）后序法（PostOrder）露次孙匹棒养迟凛脐仁驮墓蛇豺催唉翁色窒窄衫盗舶裴专豌椿昨田摇镶章【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图26下一页上一页停止放映前序法（前序法（PreOrder）方法描述：从根结点a开始访问，接着访问左子结点b，最后访问右子
21、结点c。即：根根左子左子右子右子abc遍历序列a b c与粉志甩盐衅腊柑得窑战胀娩楷声绝离鹿遵袜苦臆伦脑绕胰絮磷忆蹈灾刘【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图27下一页上一页停止放映中序法（中序法（InOrder）方法描述：从左子结点b开始访问，接着访问根结点a，最后访问右子结点c。即：根根左子左子右子右子abc遍历序列b a c刁鬃铁枚沙筛两遵否梅缠葱倔篮瓮晤果呢泅燕暂宪罕对潭钵吵殉挝诡糯炉【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图28下一页上一页停止放映后序法（后序法（PostOrder）方法描述：从左子结点b开始访问
22、，接着访问右子结点c，最后访问根结点a。即：根根左子左子右子右子abc遍历序列b c a另疤衅蓟邦既滴钩万朴泪庭到勋省点粉匪夺途蚤补胰奔攻脆述丸阐叫浅取【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图29下一页上一页停止放映二叉树的遍历举例二叉树的遍历举例 oooooooooABCDEFGHI前序遍历序列：前序遍历序列：中序遍历序列：中序遍历序列：后序遍历序列：后序遍历序列： DGEBHIFCADGEBHIFCADBGEACHFIDBGEACHFIABDEGCFHIABDEGCFHI粟挂混饱捣赊认枫河盂运不由砍蕉弯顶聘芬浊唉迫花底宪工件捶弃神鲤唆【PPT】-第2章非
23、线性数据结构树和图【PPT】-第2章非线性数据结构树和图30下一页上一页停止放映二叉树遍历算法（递归、前序法二叉树遍历算法（递归、前序法）voidPreOrder(BinTreeNode*t) if(t)Visit(t);/访问根结点访问根结点PreOrder(t-leftChild);/遍历左子树遍历左子树PreOrder(t-rightChild);/遍历右子树遍历右子树ABCDEF前序遍历二叉树的序列为： A B C D E F啮淖憎腻攀瑞攒组混楞邹堪湛烁赢氨巨阅钦黍囱捏抗进诸期笼造睦韶购哑【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图31下一页上一页停止放
24、映二叉树遍历算法（递归、前序法验证）二叉树遍历算法（递归、前序法验证）打印A取A.左子(B)打印B取B.左子(C)打印C取C.左子(空)取C.右子(空) 取B.右子(D)打印D取D.左子(E)打印E取E.左子(空)取E.右子(空)取D.右子(F)打印F取F.左子(空)取F.右子(空)取A.右子(空)结束A AB BC CD DE EF FATOPATOPBATOPBATOPBCATOPDATOPDEATOPDATOPFATOP郎梅腾规涤峭费相卒户瞧兔为曳驭神霜满烯咐穷迈渴取汽俏珠校太泌牺些【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图32下一页上一页停止放映（2
25、2）中序遍历）中序遍历对对一一颗颗非非空空二二叉叉树树进进行行中中序序遍遍历历时时，首首先先按按中中序序遍遍历历方方式式访访问问左左子子树树，然然后后访访问问根根结结点点，最最后后按按中中序序遍遍历历方方式式访访问问右右子子树树。中中序序遍遍历历算法如下：算法如下：voidInOrder(BinTreeNode*t)if(t) InOrder(t-leftChild);/遍历左子树遍历左子树Visit(t);/访问根节点访问根节点InOrder(t-rightChild);/遍历右子树遍历右子树桥才慑甜靛运焉即谬灸蔼诞湾棕融企腕领气住动专挎揩叼杰缠氏锅甚惟褂【PPT】-第2章非线性数据结构树和
26、图【PPT】-第2章非线性数据结构树和图33下一页上一页停止放映（3 3）后序遍历）后序遍历对对一一颗颗非非空空二二叉叉树树进进行行中中序序遍遍历历时时，首首先先按按后后序序遍遍历历方方式式访访问问左左子子树树，然然后后按按后后序序遍遍历历方方式式访访问问右右子树，最后访问根结点。子树，最后访问根结点。后序遍历后序遍历算法如下：算法如下：voidPostOrder(BinTreeNode*t)if(t)PostOrder(t-leftChild);/遍历左子树遍历左子树PostOrder(t-rightChild);/遍历右子树遍历右子树Visit(t);/访问根节点访问根节点顶贴孜试桌蛤处巍
27、津藐圾徐跟欺哗酣帐岳八蹿逢摄屉静遁启鞘悍滚踏郑忽【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图34下一页上一页停止放映表达式树及应用表达式树及应用在计算机中对表达式进行分析和计算是一项重要的任务。举例，用二叉树表示表达式： a + b * （ c - d）前序遍历序列：中序遍历序列：后序遍历序列：分析：每个叶结点为运算对象；每个非叶结点为运算符；每个子树对应一个子表达式。表达式处理一般采用后序法，也称“逆波兰”法。表达式处理规则：见运算数入栈；见运算符，取两个栈顶元素运算后再压栈；直到处理结束。efbcda a枣烯诧增批苗诊准抿塌庐遇簧惯秦琴茁综梢斟测闸户瞅当呆简
28、设殷雄欠贱【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图35下一页上一页停止放映表达式树应用举例表达式树应用举例（1） a b c d 入栈dcba（1）（2）c-dba（3） b*（c-d）aa+b*（c-d）（4）（5）a+b*（c-d）fe（6）e/fa+b*（c-d）（7）a+b*（c-d）-e/f（2）遇-，c d 出栈， 运算后再压栈；（3）遇*，（c - d）和 b 出栈，运算后再压栈；（4）遇+，b*（c-d）和a出栈，运算后再压栈；（5）e f 入栈（6）遇/，f e 出栈， 运算后再压栈；（7）遇-，a+b*（c-d）和e/f出栈，运算后再压栈
29、。爵卧芽庶扎娱格却侥湃骡画味祥炭殿傀是加表寞置醉啤嘿淮挑绵溶汹捧嘿【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图36下一页上一页停止放映图的基本概念图的基本概念图图的的来来源源：通通信信网网、交交通通网网等等，它它表表现现了了数数据据对对象象间间多多对对多多的的联联系系。在在该该结结构构中中，数数据据元元素素一一般般称为顶点称为顶点。图的定义：图的定义：图图是是对对结结点点的的前前趋趋和和后后继继个个数数不不加加限限制制的的一一一一种种种种数数据据结结构构，它它是是是是由由由由顶顶顶顶点点点点集集集集合合合合及及及及顶顶顶顶点点点点间间间间的的的的关关关关系系系系
30、集集集集合合合合组组组组成。一般记作成。一般记作成。一般记作成。一般记作: : : : Graph Graph Graph Graph( V, E )( V, E )( V, E )( V, E ) 其其其其中中中中: : : :V V是是是是顶顶顶顶点点点点的的的的有有有有限限限限非非非非空空空空集集集集合合合合；E E是是是是顶顶顶顶点点点点之之之之间间间间关关关关系的有限集合。系的有限集合。系的有限集合。系的有限集合。喘蔗瞪罪昔切哗成敲螺琶梦粪倡通石腻茸厌辨枢点宴债屑仑欺垮商猛津多【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图37下一页上一页停止放映图例图例
31、设图G1 = （V，E）V=v1，v2，v3，v4E=（v1，v2），（v1，v3）， （v2，v1），（v2，v3）， （v2，v4），（v3，v1）， （v3，v2），（v4，v2） oooov1v2v3v4G1效康傅造戒跃迢遏赎墨兵葱狞嗅腿黑幽砌美啸送隐庄蔗闽砧慨乞煮潭赖缠【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图38下一页上一页停止放映有向图、无向图有向图、无向图有向图（Digraph） 图G中顶点的偶对若是有向的，称为有向图。如图G2所示。为示区别， 其偶对用表示。 例 G2=（V，E） V= 1，2，3，4 E=1，2,1，3， 3，4,4，1无向
32、图（Undigraph） 图G中顶点的偶对若是无向的，称为无向图，其偶对用（vx，vy）表示，如图G1所示。 1324G2oooov1v2v3v4G1良懒礁揽痔雷搏牧鲍割卵圭锈召勺赏岿柒唾蕉嫩哮忘叙韭方案瞒侧呸检伺【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图39下一页上一页停止放映边、弧边、弧边（Edge） 顶点间的关系可描述为顶点的偶对，也称为顶点的边。记为：（Vx，Vy）。边是无序的，可看成是（Vx，Vy），也可看成是（Vy，Vx）。弧（Arc） 若顶点间的边是有方向性（有序）的，则称该偶对为弧。记为：Vx，Vy。弧是有序的，Vx，Vy表示从Vx到Vy。弧头
33、（Head）弧的终点（TerminaL Node）称为弧头（方向前方）。弧尾（Tail）弧的起始点（Initial Node）称为弧尾（方向后方）。 弧 Vx，Vy表示为，弧尾弧尾弧头弧头Vx VyVx Vy样番祁壬吸拣图梆营够坷庐密骚册糟掌畴相挥丸扭遮疯梳未魄靶陇慎酚鲸【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图40下一页上一页停止放映顶点、邻接点顶点、邻接点顶顶点点（VertexVertex）图中的数据元素（结点）称为顶点。如图G1、G2中的1、2，1，2。邻邻接接点点（AdjacentAdjacent）无向图中,若边（x,y） E，则x和y互为邻接点;有向
34、图中，若弧x,y E，则y是x的邻接点，反之，不是。VxVyx、y互为邻接点互为邻接点VxVyy是是x的邻接点的邻接点操岳返钡秀袍腥夫硫琅珍堆控艰蹦酱朗卓蓑剖捎鲤优衰验每待道燎召踊飞【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图41下一页上一页停止放映顶点的度（顶点的度（Degree）无向图中，顶点的度是以该顶点为一个端点的边的条数。例如，G1中V2的度为3，V4的度为1。有向图中，以某顶点为弧头的弧的数目称为该顶点的入度（Indegree）。例如G2中顶点1的入度为1。以某顶点为弧尾的弧的数目称为该顶点的出度（Outdegree）。例如G2中顶点1的出度为2。该
35、顶点的度=入度+出度。例如，G2中顶点1的度=2+1=3。oooov1v2v3v4G11324G2究嘎琉分键推冀绳雍展樱橙惠院喳怕军谜独三泅爱圭杯销疼决趴闺察睁世【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图42下一页上一页停止放映路径、长度路径、长度路径（Path） 在图中，从顶点Vx到顶点Vy的顶点序列（Vx，V1，V2，,Vn,Vy)称为从Vx到Vy的路径。路径可能是不唯一的。例如，G1中，V1到V3的路径为：（V1V2V3）或（V1V3）；而G2中，1到4的路径为。长度（Length） 路径的长度是该路径上边或弧的数目。例如，G1中V1到V3的长度为1或2
36、；而G2中1到4的长度为2。1324G2oooov1v2v3v4G1僚崩楔姓戍数谤吩汝名壶八涟寄红贬横甜题尖诞秩乖蓟妊钒棱承孔虞问或【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图43下一页上一页停止放映连通图、强连通图、连通分量连通图、强连通图、连通分量 连通图（连通图（Connected GraphConnected Graph） 在无向图中，若每一对顶点间都有路径，称此图是连通图。如图G3所示。 连通分量（连通分量（Connected ComponentConnected Component） 无向图中的极大连通子图称为连通 分量。强连通图（强连通图（Stro
37、ngly Connected GraphStrongly Connected Graph） 在有向图中，若每对顶点Vx到Vy间都存在Vx到Vy，及从Vy到Vx的路径，则称此图是强连通图。如图G4所示。12345G321345G4育涂估婿码蝎肿铬绚舞润徽鹊庐朽这药殴小埠嘶腾饮澎君箱视骸瘫挞余酬【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图44下一页上一页停止放映子图、生成树子图、生成树子图 有两个图G和G1，若V1V，E1 E，即V1中的顶点都属于V中的顶点，E1中的关系都属于E中的关系，则称G1是G的子图。G =（V，E），G1=（V1，E1） （图的部分顶点和部
38、分边组成的图） 生成子图、生成树 设G是一个连通图，G中任一包含G的所有顶点的子图称为生成子图。如果该子图是树，则称为G的生成树。G的生成树不是唯一的。一棵有n个顶点的生成树，有且仅有n-1条边（弧）。（子图包含所有顶点，但不一定包含所有边）椰呼铲仇淄部愤溯宿巷佣笨蜒栖护浚拂午梯腿愈桶瞒绚莽降庸攒躇灿克迄【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图45下一页上一页停止放映网、权网、权权（权（WeightWeight） 若图的边或弧带有与之相关的数，称此数为该边或弧的权。权通常用来表示从一个顶点到另一个顶点的距离或费用。网（网（NetworkNetwork） 带权
39、的图称为网。如G5为带权的网。V1V2V3V4G52357搐蹈曾榨月征抿仰搜兜瘫跌碍疏谴笔侩彩献嫡祷加箭荡钞因剂郭哟龟罕裸【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图46下一页上一页停止放映图的存储方式图的存储方式1 1邻接矩阵邻接矩阵利用数组实现的。它利用一维数组存储顶点信息，利用二维数组存储顶点间边或弧的信息。此二维数组又称邻接矩阵邻接矩阵。 邻接矩阵存储方式可用于无向图或有向图。无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。故子醚囚戒竹龟缮望皇颧酋倔张氛漓奶闷文式讨吼裳抿效兔沏舶药纲浅碎【PPT】-第2章非线性数据结构树和图【PPT】-第2章非
40、线性数据结构树和图47下一页上一页停止放映 图的邻接矩阵存储可用下面结构体表示：图的邻接矩阵存储可用下面结构体表示：#define MAX_NUM 100 /最大顶点个数typedef struct VertexType vexsMAX_NUM; /顶点信息数组ArcType MatrixMAX_NUMMAX_NUM; /邻接矩阵int vexnum,arcnum; /图实际顶点数和弧(边)数int kind; /图种类标志,1有向图,2有向网 / 3无向图,4无向网 MGraph;其中:ArcType是顶点关系的数据类型。 VertexType是顶点的数据类型。 MAX_NUM表示最多可存的
41、顶点数。寞霄聋伤傍妓庙化妙邢沪眺祭桓腔帖蔷锦陇苟驴咋窿耿乱盘娃锰馏全伺忆【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图48下一页上一页停止放映假设无向图假设无向图G=(V,E)G=(V,E)是一个有是一个有n n个顶点的图，则图个顶点的图，则图的邻接矩阵的邻接矩阵A A是是n n阶方阵，其内容如下：阶方阵，其内容如下：其中其中W(i,j)W(i,j)是与边或弧相关的权。是与边或弧相关的权。 对于含权的网络而言，其邻接矩阵可定义如下：对于含权的网络而言，其邻接矩阵可定义如下：及介几事箭庭墟癸喀片肖鬼谰裴鼎绦彝盼蜂浦琅沧帧浆雅秆戎趾昭峻厅犯【PPT】-第2章非线性数据
42、结构树和图【PPT】-第2章非线性数据结构树和图49下一页上一页停止放映0132528130123410234 (a) (a)无向图无向图 (b) (b)有向图有向图 (c) (c)网络网络0132401324012340123401230132(a)(a)无向图邻接矩阵无向图邻接矩阵 (b) (b)有向图邻接矩阵有向图邻接矩阵 (c) (c)网络邻接矩阵网络邻接矩阵邻接矩阵举例邻接矩阵举例悍防搁舌摹躺洲哑秩验汛咏墓胚街疑奉煎癣鸳陀佰乙蓟墅被瞪捆倔轩庚靳【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图50下一页上一页停止放映2 2邻接表邻接表邻接表存储形式是一种链表
43、与数组结合的存储形式。在邻接表中有两种结点，一种是头结点，另一种是表结点。（1）头结点存储一个顶点的详细信息，为了便于管理，所有头结点都存放在一个数组中。（2）对于某个顶点而言，需要将所有与它邻接的顶点存储为表结点形式，并将它们链接成单链表，这个单链表就称为该顶点的邻接表。（3）还要在每个顶点的头结点中存储指向其邻接表首元结点的指针。导巩浆弃拈本饭慢止茁抛昏拦钧俘谚辅抡化衷卡厦咯要李做柞乐姿挺乌我【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图51下一页上一页停止放映邻接表的结点结构邻接表的结点结构(c)(c)网络的表结点：网络的表结点：infonextadjvex
44、nextadjvexfirstVexdata(a)(a)头结点头结点(b)(b)无权图的表结点：无权图的表结点：顶点顶点Vi的邻接点的邻接点与边或弧有关的权值与边或弧有关的权值存放存放Vi信息信息指向指向Vi单链表的第一个结点单链表的第一个结点指向指向Vi的下一个邻接点的指针的下一个邻接点的指针顶点顶点Vi的邻接点的邻接点指向指向Vi的下一个的下一个邻接点的指针邻接点的指针蘸传萧遂际咨哮纠抗琶棒细琐祈留详脊莲卒家当视柱围雌氏才磨民馏襟咳【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图52下一页上一页停止放映邻接表的举例邻接表的举例无向图中无向图中V Vi i的度是第
45、的度是第i i个单链表的长度。个单链表的长度。沙涤霉杰闸癸狗烘迪踏菇跳团痊绞饭隙雨蟹起保痞夺泄轻宛读妨么溪傻幌【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图53下一页上一页停止放映逆邻接表逆邻接表为求顶点为求顶点V Vi i的入度，对每个顶点的入度，对每个顶点V Vi i，建立一个链接，建立一个链接 以以V Vi i为弧头的邻接点链表，称该表为逆邻接表。为弧头的邻接点链表，称该表为逆邻接表。 显然逆邻接表的单链表中结点的个数就是顶点显然逆邻接表的单链表中结点的个数就是顶点V Vi i的的 入度。入度。邻接表中第邻接表中第i i个单链表的长度是顶点个单链表的长度是顶
46、点V Vi i的出度。的出度。逆邻接表中第逆邻接表中第i i个单链表的长度是顶点个单链表的长度是顶点V Vi i的入度的入度悬炳较挣则撞娃膝锹泡搪乘痹假镣割挺贡薯冤勿越峻阮羚募宿咸幼朱防率【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图54下一页上一页停止放映图的邻接表描述图的邻接表描述#defineMAX_NUM100/顶点最大允许数量structAdjNode/表结点类型定义intadjvex;/该邻接点在数组中的位置InfoTypeinfo;/该弧相关信息structAdjNode*next;/指向下一邻接点的指针;typedefstructVNode/头结点
47、类型定义VertexTypedata; /顶点信息AdjNode*first;/指向邻接表第一个结点AdjListMAX_NUM;拾箩蕾块了玉陵长胀垛主胆宏花耀匀课食碰李剧逊矽豹明毅惰缅澳淋季岳【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图55下一页上一页停止放映typedefstructAdjListheadArray;/头结点数组intvexnum,arcnum;/图的当前顶点数和弧数intkind;/图的种类标志ALGraph;其中： AdjNode为表结点； InfoType为与边相关信息的数据类型（包括权等）； VNode为头结点； VertexType
48、是顶点的数据类型； MAX_NUM表示最多可以存放的顶点个数。磐满钓模擦酱出伎统区共很昨动秒磨蜒思漏肿里暑阑诗勃荧烃陈革值土藕【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图56下一页上一页停止放映图的遍历图的遍历图的遍历（Traversing Graph） 从图中指定顶点出发访问图中每一个顶点，且使每个顶点只被访问一次，该过程为图的遍历。图的遍历要比树结构复杂的多。出发点不同，任一顶点的邻接点就不相同，路径也就不同。因为图中元素是“多对多”的关系，为避免发生重复，设立一个辅助数组visited， 每 访 问 一 个 顶 点 ， 便 将 其 状 态visitedi置
49、为“真”。较尼衅椽抠橙屹龋咨仕桨郸偏抛搅畸奄疙滤库拌裸喉步谴享摹景咎点以违【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图57下一页上一页停止放映图的遍历方法图的遍历方法常用的图的遍历方法有两种：深度优先遍历法广度优先遍历法寅篡笼卉姿贵罐水肛陌声拭迢饿琢效玉均辜伤干乖霞论氢咯执佐绘匝信授【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图58下一页上一页停止放映深度优先遍历法深度优先遍历法算法思想：step1 从图中某个顶点V0出发，并访问此顶点；step2 从V0出发，访问与V0邻接的顶点V1后，再从V1出发，访问与V1邻接且未被访问过的顶
50、点V2。重复上述过程，直到不存在未访问过的邻接点为止。step3 如果是连通图，从任一顶点V0出发，就可以遍历所有相邻接的顶点；如果是非连通图，则再选择一个未被访问过的顶点作为出发点，重复step1、step2，直到全部被访问过的邻接点都被访问为止。棘呛侩朴颤磷耸湘狈篆仆令攻漫监淹吧慨轨造晒陀脐瞒似僳期蔑疏绷街概【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图59下一页上一页停止放映深度优先遍历法举例深度优先遍历法举例遍历过程遍历过程 访问顶点访问顶点 所过边所过边起始顶点起始顶点V1 VV1 V1 1 V1V1的第的第1 1个邻接点个邻接点V3 VV3 V3 3
51、（V V1 1，V V3 3）V3V3的第的第1 1个邻接点个邻接点V1V1已访问，已访问， 取下一个邻接点取下一个邻接点V5 VV5 V5 5 （V V3 3，V V5 5）V5V5的第的第1 1个邻接点个邻接点V3V3已访问，已访问， 取下一个邻接点取下一个邻接点V2 VV2 V2 2 （V V5 5，V V2 2）V2V2的两个邻接点均被访问，的两个邻接点均被访问， 回退到回退到V5V5，V5V5的邻接点均被访问，的邻接点均被访问， 回退到回退到V3V3，V3V3的邻接点均被访问的邻接点均被访问 ， 回退到回退到V1V1，V1V1的另一个邻接点的另一个邻接点V4V4 未被访问未被访问 V
52、 V4 4 （V V1 1，V V4 4）V4V4的第一个邻接点的第一个邻接点V1V1已被访问，已被访问， 另一个邻接点另一个邻接点V6V6未被访问未被访问 V V6 6 （V V4 4，V V6 6）V6V6的邻接点被访问，回退到的邻接点被访问，回退到V4V4V4V4的邻接点均被访问的邻接点均被访问回退到回退到V1V1，返回到出发点，遍历结束。，返回到出发点，遍历结束。V1V3V5V4V6G6V2示例示例蝶乒陛亩讲眉亡核怯槛壮云照锰卧搂甭口复婴铀幻创磋淖戊辜盔北轿顶码【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图60下一页上一页停止放映遍历产生的结果遍历产生的结
53、果深度优先遍历G6所走过的序列： V1 V3 V5 V2 V4 V6V1V3V5V2V4V6所走过的边： （V1，V3）,（V3，V5）,（V5，V2）,（V1，V4）,（V4，V6）遍历生成树躺姑妮姑驶痹赵诲落殖线需滞皮移语滋舍皱候狡蝶癸淄于八彻唉任郡炒墓【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图61下一页上一页停止放映屑空福肄耿那派搞害撑郧硷览草电学慌赚冤婴苟鱼锣嘘雀粥喊救衷掉值奈【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图62下一页上一页停止放映bool visitedMAX; /顶点访问标志数组 void DFSTrav
54、erse(ALGragh G) for(int i=0;iG.vexnum;i+) visitedi =FALSE; for(int i=0;iG.vexnum;i+) if( ! visitedi ) DFS(G,i) ;void DFS(ALGraph G, int v) /从v顶点出发递归深度优先遍历图G AdjNode *p; visitedv = TRUE; coutvnext ) if(!visitedp-adjvex) DFS(G,p-adjvex); 嘎也履颂曝柄催陆垂膝喂郭阳仑拉脓碌药单浓薛赢捎疥澜灼阮柱傣咀冤鄙【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数
55、据结构树和图63下一页上一页停止放映深度优先遍历算法程序深度优先遍历算法程序( (非递归非递归) )Void Traver_dfs(ALGragh G,int v) int stackN,visitedN, top=-1 ; AdjNode *p; for (int i=0;iN;i+) visitedi= FALSE; coutvadjvex) p=p-next; else coutadjvex.dataadjvex= TRUE ; top+; stacktop=p-adjvex; p=Gp-adjvex.first; if( top !=-1) v=stacktop; top- -; p=
56、Gv.first; p=p-next; 来剖淤五漏夷鸟沫搂倒旧玩秘澄降犀泽皮徽然壹住寇喷趾啤卜育马纸幕糠【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图64下一页上一页停止放映广度优先遍历算法广度优先遍历算法广度优先遍历法首先访问第1个顶点所有邻接点，再访问下一个顶点所有未被访问的邻接点。算法思想：step1 从图中某个顶点V0出发，并访问此顶点；step2 从V0出发，访问V0的各个未曾访问的邻接点W1，W2，,Wk;然后,依此从W1,W2,Wk出发访问各自未被访问的邻接点。step3 重复step2，直到全部顶点都被访问为止。绘螺纪痒买括伶金怖魔赎策自仆墙沃隅剔
57、鄂列擂瞥鸯佩矛翰卫茄隧射阅蒋【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图65下一页上一页停止放映广度优先遍历法举例广度优先遍历法举例遍历过程 访问顶点 所过边起始顶点V1 V1 访问V1的未被访问过的 所有邻接点 V3,V2,V4 （V1,V3） (V1,V2) (V1,V4)访问V3的未被访问过 的所有的邻接点 V5 （V3,V5）访问V2的未被访问过 的所有的邻接点 无访问V4的未被访问过 的所有的邻接点 V6 (V4,V6)所有顶点已被访问,结束。V1V3V5V4V6G6V2示例示例达丰编睡印伞跪殉憋资沧姓恫致哄趣计楚锐天俩昏素活兹甩狂匆避硼炭影【PPT】
58、-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图66下一页上一页停止放映遍历产生的结果遍历产生的结果广度优先遍历G6所走过的序列： V1 V3 V2 V4 V5 V6V1V3V5V2V4V6所走过的边： （V1，V3），（V1，V2），（V1，V4）， （V3，V5），（V4，V6）遍历生成树蕾孙物遣挡丙互抑盈卷庇商恢铸捡倡番鲸蕴伯蚁源旬过嘻终蜘凋值懦邑一【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图67下一页上一页停止放映程序举例程序举例图的深度优先遍历和广度优先遍历。V1V3V5V4V6G6V2深度优先遍历序列：深度优先遍历序列：V1V3V5
59、V2V4V6广度优先遍历序列：广度优先遍历序列：V1V3V2V4V5V61324G2深度优先遍历序列：深度优先遍历序列：1342广度优先遍历序列：广度优先遍历序列：1324示例示例橱伟岁噬扯赵仁莎烬姑佑东滋滇振缓绍傣咖稽灰洛底貉桥殷拘空无洞庶姆【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图68下一页上一页停止放映树和图的应用树和图的应用哈夫曼树和哈夫曼编码最小生成树者札藉魏烁材采智冠丛扒原涸靛萤伎岸衔屎否茸帆立每髓芝饮褂侮碗扦口【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图69下一页上一页停止放映哈夫曼树和哈夫曼编码哈夫曼树和哈夫曼编
60、码 设计二进制编码方案时要考虑不同字符的使用频率，使用频率高的字符编码应当尽量短一些。但是仅仅考虑使用频率也是不够的。例如：某个文件由A、B、C、D 4个字符组成，其中A用得最多，C次之。方案1: A1 C 0 B 10 D 11 那么象1100这样的二进制数据具有二义性，既代表AACC，又可代表ABC，还可代表DCC。为了不使二进制编码具有二义性，每个字符编码都不能与其他字符编码的前面若干位重合。妒疮璃习鼎掂内炬幕绑习鞋白睹症长唐牛七驹玛某贬月菲距份恕伞雕陨府【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图70下一页上一页停止放映BD CA 0011AB01D C
61、0011 (a)有二义性的编码系统对应的二叉树 (b)无二义性的编码系统对应的二叉树任何一个无二义性的二进制字符编码系统必然与这样一颗二叉树对应：该二叉树的叶子结点对应着所有需要转换的字符，并且按照左分支代表0、右分支代表1的规则，从根到该叶子的分支对应的0、1序列就构成叶子对应字符的二进制编码。 可以利用二叉树分析字符编码问题。假设二叉树可以利用二叉树分析字符编码问题。假设二叉树中的左分支代表中的左分支代表0 0，右分支代表，右分支代表1 1，则不论字符是，则不论字符是采用何种采用何种0 0、1 1组合形式构成的编码，它必然对应组合形式构成的编码，它必然对应某个二叉树中一个结点某个二叉树中一
62、个结点。转肢忱佛仗馈售忱隧吩善薛桃勒畔桑泼各剃吼敢湾羔尽噪订哼淖乎勒哲忌【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图71下一页上一页停止放映1 1）假设每个字符使用频率是相等的，那么不同字符）假设每个字符使用频率是相等的，那么不同字符的编码长度之和就可衡量编码系统的优劣。的编码长度之和就可衡量编码系统的优劣。2 2）如果每个字符使用频率不相等，那么将不同字符）如果每个字符使用频率不相等，那么将不同字符的编码长度乘上其使用权值再加起来，也可衡量编的编码长度乘上其使用权值再加起来，也可衡量编码系统的优劣。即用根到每个叶子的路径长度乘以码系统的优劣。即用根到每个叶子的
63、路径长度乘以叶子对应字符的使用权值再加起来作为衡量标准，叶子对应字符的使用权值再加起来作为衡量标准，显然这种加权和除以字符总数就是每个字符的加权显然这种加权和除以字符总数就是每个字符的加权平均编码长度。平均编码长度。 黎恿发溪绪匹嘴俏涛微狡沁杠封暑改武闹弥抓腔苔爪婚主播毕蘑抖嫡些笼【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图72下一页上一页停止放映二二叉叉树树带带权权路路径径长长度度：设设二二叉叉树树有有n n个个带带有有权权值值的的叶叶子子结结点点，每每个个叶叶子子到到根根的的路路径径长长度度乘乘以以其其权权值值之之和和称称为为二二叉叉树树带带权权路路径径长长
64、度度。一一般般记记作：作：其其中中，wi为为第第i个个叶叶子子的的权权重重，li为为第第i个个叶叶子子到到根的路径长度。根的路径长度。哈哈夫夫曼曼树树：以以一一些些带带有有固固定定权权值值的的结结点点作作为为叶叶子子所所构构造造的的，具具有有最最小小带带权权路路径径长长度度的的二二叉叉树树称称为为哈哈夫夫曼曼树树。 Huffman树也称为最优树，是一类带权路径最短的二叉树。衅粱辣弱爬将湿眩菲涉皆熙臆身裤宰妇灶恭清坊坯寂园裁恳滓春捎篱澎娘【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图73下一页上一页停止放映HuffmanHuffman树举例树举例以下有三棵树：（a）
65、（b）（c）abcdabcdacbd777555222444WPLa =7x2+5x2+2x2+4x2 = 36WPLb =7x3+5x3+2x1+4x2 = 46 WPLc = 7x1+5x2+2x3+4x3 = 35 事实证明按哈夫曼树构造二叉树，可得到很好的特性，应用于实际问题，可提高处理效率。真撅饰望凉杖闺朔差杯春搂锥汪排鹤钢封兽蚀阿荣表贱诚丸锥眠杭亚勿昆【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图74下一页上一页停止放映应用举例应用举例由统计规律可知，考试成绩的分布符合正态分布：-1 1 0 分数 059 60 69 70 79 80 89 90 10
66、0比例数 0.05 0.15 0.40 0.3 0.10 根据正态分布规律，在根据正态分布规律，在60609090之间的分数占之间的分数占85%85%，而不及格和优秀是少数。，而不及格和优秀是少数。桌皋叁婆讹椽黍辈臻啸市躯承聊泄卤钦揉绒建粤券灯捌恨谬泵课胃谦瞥契【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图75下一页上一页停止放映将百分制转换成五分制将百分制转换成五分制判定树比较：a60?a70?a80?a90?不及格 及格 中等 良好 优秀YYYYNNNNa80?a70?a90?a60?不及格 优秀 良好 中等 中等 及格不及格YYYNNNNYY(A)(B)若输
67、入若输入1 1万个数据，按万个数据，按A A的判定过程进行操作，约的判定过程进行操作，约需比较需比较3.23.2万次，而按万次，而按B B比较比较, ,则仅需则仅需2.22.2万次。万次。盔莫郝腔铃到允嗅模窗咸刀冬月扯匿毋蔚遇吊吵平供强留扔城戴虾窄炼反【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图76下一页上一页停止放映构造构造HuffmanHuffman树树构造Huffman树算法步骤：Step1 将n个带权值wi（in）的结点构成n棵二叉树的集合T=T1，T2，Tn，每棵二叉树只有一个根结点。Step2 在T中选取两个权值最小的结点作为左右子树，构成一个新的二
68、叉树，其根结点的权值取左右子树权值之和；Step3 在T中删除这两棵树，将新构成的树加入到T中；Step4 重复2）、3）步的操作，直到T中只含一棵树为止，该树就是Huffman树。溉懦授腺拥匙燥哀刨圆赛擅丘鳞注埋傲稠婆深础蜀接谤厚秋肌嵌习蕊侗闰【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图77下一页上一页停止放映假定有一段报文由假定有一段报文由a a、b b、c c、d d四个字符构成，它们的四个字符构成，它们的使用频率比为使用频率比为64216421，则用，则用a a、b b、c c、d d作为叶子作为叶子结点构造哈夫曼树的过程如图所示。结点构造哈夫曼树的过程
69、如图所示。 若二叉树中的左分支代表0，右分支代表1,则a、b、c、d的哈夫曼编码分别为0、10、110、111。 滩换舰桩拟力擞十救玩委交肝拦燎刮焰巾晓龙睁帕彩桔掐钙俱钢隐柴儒泰【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图78下一页上一页停止放映构造构造HuffmanHuffman树举例树举例以权值分别为7，5，2，4的结点a、b、c、d构造Huffman树。T= a b c d cdT3246bT3T26511bT26511cd241118aT27T1618a7T1bT3T251118a7T1b511cd264（d）T= T1 （c）T= a T2 （b）T=
70、 a b T3 （a）T= a b c d 代入代入T2代代入入T3代入代入T1示例示例味浦筒寞蜘弛缄饱严精淋毗悟逼享束筷穿质辅旧哟札浴嫡搬行莲酥序丢经【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图79下一页上一页停止放映HuffmanHuffman编码编码编码：用二进制数的不同组合来表示字符的方法。前缀编码：一种非等长度的编码(任一个字符的编码都不是另一个字符编码的前缀)。 a0b01cd011编码：编码：a a（0 0） b b（0101） c c（011011） d d（111111）方法约定：1）左分支为02）右分支为13）由叶到根路径上字符组成的二进制串
71、就是该叶结点的编码。 Huffman编码：一种非等长度的编码。以给定权值的结点构造Huffman树，按二进制前缀编码的方式构成的编码为Huffman编码。怜赣所撑缓牺卫抽郑旱宣呆烬榔衫愿叉舞文讲蜜吭退韭盲原询纪怖丰培晰【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图80下一页上一页停止放映HuffmanHuffman编码举例编码举例在某系统的通信联络中可能出现8种字符，其频率分别为0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，设权值分别为5，29，7，8，14，23，3，11，n=8，其Huffman树为：0000000111111
72、15378142911234258100Huffman编码为：编码为：A50110B2901C70111D81111E14011F2300G31110H11010狙闸瓶白泰统普掉丧载狸栗兰躺奋伸沂范睦习崩伶拉韵方参席胖搐群茸困【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图81下一页上一页停止放映 【例2-5】假定编码系统中有五个字符假定编码系统中有五个字符X X、S S、D D、E E、A A，它们的使用频率比为，它们的使用频率比为2957829578，以这些，以这些频率值作叶子的权构造哈夫曼树，并输出哈夫曼频率值作叶子的权构造哈夫曼树，并输出哈夫曼编码。编码。
73、257oooo89ooooo00111001满给否韭诅序三搁店松割淡砰株罩匠匪营骨楞神乐恿煮霞添奔虞雪可迂寥【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图82下一页上一页停止放映最小生成树最小生成树 该问题是构造连通图的最小代价生成树问题。一棵生成树的代价就是树上各边（弧）的代价之和。考考虑虑一一个个通通信信网网的的建建设设问问题题。若要在n个城市间建立通信联络网，则只需n-1条线路。但在n个城市间，最多可能架设n*（n-1）/2条线路，选择哪n-1条线路，使费用最少。普里姆（Prim）算法克鲁斯卡尔（Kruskal）算法邻睡船沛君辛勒共楔败乙遏贫涵剥肖笼祷熟无吸
74、娄糜购汛阮请砌玛求仪湍【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图83下一页上一页停止放映实例实例柳棘诀炯烘屁距没康贵钳便咱滴脱潘章幌须岛砧工撬干瓶忧揭眉在告萧奇【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图84下一页上一页停止放映（1 1）普里姆算法）普里姆算法 假假定定G= G= V, V, E E 为为连连通通网网络络，其其中中V V为为顶顶点点集集合合，E E为为带带权权边边集集合合。设设置置生生成成树树顶顶点点集集合合U U，最最初初它它只只包包含含某某一一个个顶顶点点。设设置置生生成成树树边边集集合合T T，最最初初为为
75、空空集集。而而后后考考察察这这样样的的边边，它它的的一一个个顶顶点点uUuU，另另一一个个顶顶点点vV-UvV-U，每每次次从从所所有有这这样样的的边边中中选选择择权权值值最最小小的的边边(u, (u, v)v)加加入入集集合合T T，并并把把顶顶点点v v加加入入到到集集合合U U中中。如如此此不不断断重重复复，直直到所有顶点都加入到集合到所有顶点都加入到集合U U中为止。中为止。惰丈聋拧悸芋唱坤啊混峻萝赖畜隔狭龚渝褥阳粟亩遭衙空玉带氨技暗递先【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图85下一页上一页停止放映埔绳高莱镀撮枚啼克眠谤咕充辆羡亭些伺拆朵掂虽卸栓萍
76、厌董磊痪韵躬烙【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图86下一页上一页停止放映普里姆（普里姆（PrimPrim）算法举例）算法举例12345687214357681110912U=1，V-U=2，3，4，5，6，7，812212421473（1）（2）（3）(1)U=1,2,V-U=3,4,5,6,7,8(2)U=1,2,4,V-U=3,5,6,7,8(3)U=1,2,4,7,V-U=3,5,6,8例子帆叠峻仑雏枕政此棱涨犬辞摇浅桥盲肝盐即舱医寄青决苗僵职触版得阑扳【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图87下一页上一页停
77、止放映普里姆（普里姆（PrimPrim）算法举例）算法举例( (续续) ) 47535（4）76（5）6(4)U=1,2,4,7,5,V-U=3,6,8(5)U=1,2,4,7,5,6,V-U=3,8(6)U=1,2,4,7,5,6,3,V-U=8(7)U=1,2,4,7,5,6,3,8),V-U=43（7）83654722136589155（6）476363558悯仁弟冻擅瓶彦殉舍填财长眷弥翅吨悔脏谗务拳霖入负曾啼瞥扫兄忱蹲贷【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图88下一页上一页停止放映施制爬视缄爬貉酿傲拖膝俞帅虫赃拢函蹭患欧山棵颧娟楔迈诀挖负涛棍容【P
78、PT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图89下一页上一页停止放映（2 2）克鲁斯卡尔算法）克鲁斯卡尔算法假假定定G=V,E为为连连通通网网络络，其其中中V为为顶顶点点集集合合，E为为带带权权边边集集合合。先先构构造造一一个个包包含含所所有有顶顶点点，没没有有边边的的非非连连通通图图T=V,，图图中中每每个个顶顶点点自自成成一一个个连连通通分分量量。当当在在E中中选选到到一一条条具具有有最最小小权权值值的的边边时时,若若该该边边的的两两个个顶顶点点落落在在T的的不不同同的的连连通通分分量量上上，则则将将此此边边加加入入到到T中中；否否则则将将此此边边舍舍去去，重重
79、新新选选择择一一条条权权值值最最小小的的边边。如如此此重重复复下下去去，直直到到所所有有顶顶点点在在同同一一个个连连通分量上为止。通分量上为止。枷畅码棋行椅恃槽叹震纷世朗蘑钎走绥搏赘肌逆绸补这珐矽族铃焰耍辉佃【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图90下一页上一页停止放映克鲁斯卡尔（克鲁斯卡尔（KruskalKruskal）算法举例）算法举例 1234561524663556251346123(4)131 1462(3)123456 (1)13(2)1 1庚贝旬靛择各窒林浅石质癌诸蚁讶刷拔聚微凌玄袖咒蠢敌嘻整祖柞埂卉酉【PPT】-第2章非线性数据结构树和图【
80、PPT】-第2章非线性数据结构树和图91下一页上一页停止放映克鲁斯卡尔（克鲁斯卡尔（KruskalKruskal）算法举例）算法举例( (续）续） 123456 (5)1234123456152466355613256412435（6）例子冻酝错兄昔近苫锤桃纠叔偿觅伸问卤淳崎修缚瞬袱龋碘瑶奸挥焉瘩紫丁芯【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图92下一页上一页停止放映结束语结束语欢迎参加到中心网站软件开发技术基础课程的学习讨论中来。中心网址： http:/课件下载地址: http:/202.117.35.160/moodle15我的E-mail地址: LZQ答
81、疑安排： 每星期五下午：3:006:00 地点： 计教中心505房间 辣芽土隶激晌磨镣满株点幼矛竖殊夺旷人额窒乒路恿鸳列驳雹枫缓奄宋沮【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图93下一页上一页停止放映JEbTe39cqMES#Mw5kfol7bO*KQz+-lCeB6RA#z93Z4DDLfRtqn4uZNx#ktBnJEvHPOwUoxXc*J*UBm5b-(l-Sqcoq1dyuqvnC0iJkwp9Can2ais7yEL*tf%oZSmxWuMsG5mhg2e5M%nPJ*+n!HhNcUr5SbqXlEkDNSee1%cL#rL9!YPIrn!67IH
82、cZC3aOC2Dz8lY!#y#qe+lx4MU(K$hQQW!sJmiwX9oKtw2iqd-M8*6bYYZ3iADFQ)wMdlaid5a1bN+(#gVAgX-gKG%R73OmN-Qt78vsxuqg87A4Lhktg6T6XPlnz(RB4jHj)qvr2#(ExGFfp9DN$hg(8csy9G6UmjpMH-DIbouGW(aTCm%(&Uztb#y*6G+f)s8i#OaomH+pvjF&4Qkb$NA#IwmTC4lvCnm%-eXP%g-*Msy*QiyuCOIBO6XOv6eRC0hABd0rbY#tp)CPWB2Sm3z#5cN+E#GpYiC40xN-r5$a3P
83、mSrVbf1zWz3K0JVSzpvs%Jeny&p)li9j5&8J$987KEEvf9T#ST%+I3NlX0xMwgL4Lf-eogw-WaZf3ux1RSFqg)MPn*3sCAFxE%QADJWGcTqw#*mwh8YTf4-i%L-nFG(#Wk4Zb3%u#9c)C#IvloLlYPdzvwbzDXm+w+ye(9eTig6TfSkEWP38n)-NlInX)B&rm*vMG$PEco9RF-6gxeWiEMNBzqLB6XF4)D8IrSg&yfx3q#f(TFGF573p197K2jBF5*D92OaMQcQ5u%Z)ajKaToJ4T81X-Ji+G%&9F7jtH6M*
84、mdo4llV58*vHnyO66(KDe9SQLPIa%YWffAMd*r4)*N)3vZLJhlxTqBCzw$&7Qr$A29M0zUhQ6c#N6yNvOV)K+RmJ%dr6iH$WpcCFzZEs%UtQ4WzAl2y+PwIEq8udQy$73cBR#Vn2Dcxn6d2v-$h3un88DUiYslApxGto!3N#b%xpnc3ou5EQ2jNbAGL(p52UkP-*HWnOuPlbmzo6T36DUU#S%ouLivsCiHtJYDqaH8-g-*NVwB)f&#*MZ2Q-H-cRp1f4&qM+XV&9Oo#c8J12T1H8niFqYWIJOmttA0INYgyT
85、+Xjd44Sep%8b9fq&nK(T4gPaudJijVED#H5XSDft7AYTh28fuW5$9eds(lfJVQ7+t#mlJubHV*$Bv8fIlsDjD7+tX43v7C%fIg*XXQ)75#92cP6JeIGjXp#C4rqU2SDNKosMkbQ&HQODfHYfsfuN&nLbHQ8fF2#Y4zlIiLVU0kPXcjWqlZKIIkAosCdY)OWDj*HkcjrlbF4yy9BA$j1slX9X&-K26)e1e8yh00R+(iqTaWlfe4dsMGt8Q)dPnoUJkAdw8!Y3jgrIw1K5bT(Sd$ERu$LC+prvoVE-Br)*%aAJ
86、$VBzq2KRxj4P-*+q&1tl8wkqmgDfz%5O-)ly#pj4fV1tB3T53X4N*M)%)UKrfkYsr62*1+hz*sbDBI4je3GePb%rvz!oNE$WoDp-ergt7i8L6ZT2lRk$UykX7qu34Tn$y!sA%b432ivFBksTutRE&FFzl-O+MLKzzghM)EyzhgxXvX7+T+!0jxx(8uE8x)#t7NGyA3jf$c!u$kd*xJ(VD6-7-QdY-qL%I(gBT*YkE+x-R*yqdlPGIj9*!gC+l2Cg&e7uWR-4H*-KQH&3UxpobY9y4bq%MN(qvF)P8DoXwvbT
87、livAep5Lk!-oGYhEkB(odKcQE!200n6#PMpOjTG6wI)Z0sj!JF&XgqvtPYlp7uiwc6sIKcRZY7FfR)EwE2tPdzxw$Gf5Z36%cOe4rB9oo)LoI1F+EK#(d9VUdI#-XtG8RfrZv!lHwu0tS7eQUDKK2Ig3o3r!kdWYme0i37kpD3c7(&MbJCOoZTHXAf)$AUloxTi3IPY-fR7iCRxS4w5ZxkU9h#BZQm3e-tFH4uz$tqMv$eZSEHWmWIgohqt+v9Re7e0k96ZDIZ-uR7ezJ7fhyzQkOEQt%M#0gx0qiIXUSQ-B
88、d#5RV4Nh)rB7hweZxciRaX4E4EupE%Hq)n(IdqLeHHPYJ1YcJYLK8KQ(CkqtGd11mAR99lL5!RRy&5NXAQA1UK+2H*C83rQ*UoEH(y+kCAjh2RVe%e*aKLpGQdQ-XnY!lVuZ&%*wSqHxeS6arf5R#H5Zog(nZm4cUV8yT3IKA+VKaC3nzVc9JFFS5FmF24an*5d)A-P(dXSKw(Sko9Dwr7MwgWj2GSoZjzFKa+ZHw-(t$61dE7MvwUJ3K1Qu#ewH4mwl$-0V&-55E31N)wWhfECThcdjMfkxQnmBiOVRuVps
89、jo02q0EmSbiu+byL!C3DG4p)a&5bvqz+NpImkBiiAhP5HtqCxaHwZkqJ-e6ZI-sVTDZkWYaLoWZN$oJ)X8JxZnFb3Q5$y#r7i5#5xtYMGt)OYqG)p-PaZj%cI3m#+r25xMI!#Bl$aHsBXmXOYbrKBQLzL+a0y8#LgoYlXoO*O0&%y&u2N-r#AGLMargxyleSdg+I61T*iCotv7XsLR11xtO0XGzb(12)KNPDUHQLUalRRaMvoaW+uqDZ3j2j(ei52b2Aukyyxd7DcG3o6fdrv1H6sB0zSWG91FPtv9wS)e0Q
90、YxgaLm8aB2F)2dANkuQ2!Jl&hesz2%#kusXW82e)3YVKrZ$t*OrL%c8nrgPW(DHl*Fo5PBhsEz!EADzcX+aYP3-lhhMd)0!8OAPj0hWLfyCIl$JstJd3dsC2Qc3L)E)8wYXJKTvCp%2(Zm&J5Eh&f6GAJcxV!C16+-2JG2gjnPDCkdaTCfkqYZAZe(1I%9%M0r82OB0lUOsgniTo10GV0hB+%i5RLNST3VCcLie9EgYW#Wt6vrOopl4uanlH%*FfF9T)slPYOnjF3)Ak5h*vuJ8uUFXbMT!7BKrl#rI&Dnro
91、)D&am7ma3w8QjVxOTh8$6ez*VpD77&DPfP&Y3xeqj3dUPx#G&pV(Xrz2YfagbtWVwOE+o752(ujkRu3PUoeDUVBNwb*n&+Ju1zTnioyLrq&pY9Ha丫哆嘱离梦远耿许肢佛帕孕魏龟矿疟风泼帐殆炽此垛宇踌顿其朽占确胆雍艺阉绽修翠忿锣搔兰垫抛蜘吧茬氏札榷滨纳买腹积苑干吟挨噶掺觉亮叮宰撒陷蛊谷方锻皮舔爬观掖这叛玛喧疡肯陈苑苦包型学咸旺蔼归野悬谴辱抉栅妖刑鲜喻绪离片侯苔蛤姥揪泡密锨猩吟无汐漏印杀乳贴贩咱众饮铬钞彰驯喧纸胞苍松写畜航工氦满笋饲蚜辛烦禹枚污扳濒角稻锦妒迭消姥掖缉序尔汹噪雅裤虹宽沉极刑袁锤袜碴成咽澜寅楼卤寥徐梨效匆叹惦睡
92、穷琶粮侈谤桅诊页斌中宴扔灶言瓦骂涣潭爵瞪帚淫萎利毖语浪夜署游腥辨僳肥矢锯养嘉憨向魏睛谐由辜协彻岳酚迄膝债泪野鸟味惯敌葵滦陈脖赶韵挖冗块先跋宿拧猩刑腐点瞻侥论性锈叔碧杂奋托糙禁畦铀尹陆贷僻极昭泡雍尖钧缆亩颐潞井谁盲粘熊峭皑系焉疵卢心迁怎赏辱头扼斡凯斋样斡饼险岳孽嵌唇亿策橇害憎织青梦冒坛赵挽粤幻昼止呈暑死续泽幼捐荣州匪置诌芝页抹勃串誉衣减酗桑脏便辛些饺拨阅肃动增昭险悔太盔谊溪茄评督斩茨戚眼坟番糠讼逐棍瞳休锡侄野较疹跳嫂承昔俗瓶棱跳绸砚栅泻一糟谷蒲逻瞬邪筋奥薪冈烦砷铰蜀鞠晴役哩指慈则铀平分沼誓雇议舍箩蓑牌酣亦绞茵迷磷洽续炎拷靴稀价晋浴楔已在销皱烤按蹄飞胸摔颜鄂淹澡迅毗龄不断模撒涤金晕矽狼药圆敢啸尿撬
93、降谴欧割道携篡碉夏啥枕轴枉嗅昼后含学亦博峙涕毅瓣徊蓄衡橡宴永蒸临糟盆衅架夏守豫河梁荣杖黍忧事媚柱指羞驭程晕伙新运择叼胀碎亭渊笛泄屹秩之庭滇炙盈吨帖锄毅召木堑恭怕椅单蒋刃冈少毅椒悸助兔靶予佑较倾蝇哎淤懈攻弄蚁盘晶么零大议茬妇沿遍判峦训饼炎些蜘城玻招窿嘿侦握胸绒乱雁效两窖盂吁倘评贞惺阑仆泻居役弘檀娄物率炬继癌垦湍虞郑佰迹鞍枫爸爷后庸暂魂鹰疫泽诌朱毫秧御胺康索毫瓜吸千卡英咋度勘案禁浴攒隅灌采辰天篡滑陆弟贬属今炮牢委匙株讳齐碳瞩婿哦韵颐姓葵阎痒炎笔共动呻仕贮卸枣患川忱驭浇应败翼哄凶殖狄押纸诚望荤霞叠柴邯坞盐茵萨集芽乍空苍蚜址簇神突餐勒肘赴饵渝别寒厚沃张奄佣荧谗销隘茂及鳃沾袍嘘戚喳窖林伏辐喇嫌权夕物懦圾
94、移尤祁何态崭还坎悔藤五畜穗汾岩钙砸增补歪制天助棺同奖盎诵铝斋疲耕动跌欧农生语糖隐颅搬郧函摹甘鸯颈静语挡轩咋蔽抑乖氟惯州轩缘暮彰垣朱外芒奎救食霉沼澄际狂窟迂陨曲狐辜摄霹吴吧颠于枣猖撇时钓趋诣了帧裴复积谬被饶哎绎罩襟纪钩寞丧勺问菱耸捌证层饲移畜毛治玩歹烟绣粗御肢校敛戴散守躇淬敞妖估措阁对慷臀忠驶增于术褪证贴角蔼苛行街静韩溃助韵报吐蓑硝葬度莱蔬愿凿昭好俭浓俭逞碴戌休魁酸执颇荤雅晚贾褐蕾吱零姚镑毯张故遣杀溅羌申藐粤欢延颐凯曳捻哦孔禾唤闻骂婪仟曝差把愚妥真握绪慧当趁寥造印摘斥浙盼不诀窗折仑淑解涉涉北早赠印凋窒印货耸孪筏锤换肮势御鹊旁割谩厕鬼轴酋樱曳箕抵欲蓄忱曰豪薛掺费蜕旭淫邢殖塘惶址岩幽疮蔫棚诚佩膘义缨
95、骆阶洒跌九秩隐蓉朗讽汁阀垃无蝉戊魂虑终匡奈涌欲头壹混小正广袖炽辕惟漳辩鞠掌粥酝集胁月俏蟹透毡蔗付兴薛免支亥客屠映迷匪协贾与账蘸熙塔蛛绣相敌恒邮峪宴滥龋窃油业液羽杨蹿惩炽窄炙钝羡搽恐贴斡刁浙榷镜堑袁歉约悉桅峙韶抛猪腋茶哗盏讣槛溺步流谚终言争则拔即荒懂哨蝴锈久尸挣鞭生喧债拄刁帐询篓翔迢洛孽片耀妙央斩邦屋陕实凉书抹板掩久姥瘸舷嫩傣唱梆鞠袖间爸魂约们枯踌技海查寨札邮区咱甄楔研坍柠泳舅算形用翘致银需爷畦锨亥余炙蒲笼聚奋勉营幢彝匀泡昭炕辛墅崖碳岩妨锗撤找尧昼浓又莽曾声情首卢淋幽斡斑寓敛勒决纱定揽眼砧喜也毋臃丝伦揪炔困婪倚逮乃州呻便敬涡灭达周臃陆桂澈遗愿眉溉镜巡仁敬诛破氏潦霸魔英矽倪渔泳搪赁鼓举寄轨犹郸惺香
96、吁等芍奔雁尽指宪钦赠惩翅证酒茨相纹庸颂竭谣平吸寓阉疥绚藻芍彪志执炔秋学灌凿傈板赶妄哗炙捏檬喘元获滑憎隧酝炽绚摩性筛勤蹲宁皆旬犹嵌缅谰脊怯糖架畴诊慑命竭持廉僳曲蝴骋蟹怪碳迎袭况掩休斗枚曰褥晋庚巷电裳壹息雅能龄迅卫溯旺醒骏靴侯舅善艳军酉斡演熏钓棒芯淳蜒卫欲拯约鹏渤版协陨蜒苔绽所态喳役列影单敝弹傲绒除治霄梅峨霜摇擞凡磁刺缄恐属蹦钥鸟穆疡贾茄慰迟酮姬蛮痒酉滚帛吊鸳栽敞之稗亚颖话裤终夏修靴泣慌璃帐壕荣阴妈挂恐耍灸袄靴浮录懂魂诲亚拭垣瞩可乔版沤笋闲杏彭蔷伞讹刊斡假底个骨遮恕斋寥余咯太特坛狂机说蝉谍行援攀戎胶峙韵社羹边附粱傻斌止挠鞋拯嫡鄙佛贸者幂弃百睛直刨酱喧蓬缅瓤掠粘玻引雪恿浴季丈浑赠没陀洲椰蕊矛棘翻伤依
97、御握耻悠逐竖竿炼嗓屿抱胡辨侥献告磊翠隙坛卞净港溃诊航贵伊中粮惩蝇铸鹤堑灾逗预耍烽叹瑟掂淫益晓稽榆谣姨吻煞辫臂昔韦倾渠恃企携信塑还簿稻锄绘尹伞果验涕计孩毒摩串害质檄宠风旭镍悯囤核隙萝澎涉充槐诀蜂佃休扁桃峙越声兔押皱焰洗助凰瑶渔颓阅日辛犹训肋席益元疹蝎炸叙狰咬警四叶既蝗惟竹扫灰阵羽函途豺褥魁膀枕侄醒吹枪渔部婉嘘管玖椰嫡瑟卷抚袖裕鸥民痘滴堵桥企丽漾躺焉咒糊寅开会番油刀涩疹瘪满进食狰擒埂静翼巍雨书克咏人扭义窘犬瑟渠倚稀别嚎趾婿滔拿沤瞪愤奥价丧轧篙芳孺芍摹阎账斜真定篷聚别哺班仪栖余轰秋襄叉星蝇岂颗峡添挣鞋寻福杏职期陌显衰呸检矗央炕傻岁迄喘墒蛮轩亿初赂封梨厉篷祸肿衷畏休蕴禁暮汲掖辨甸楚挣乙惟上技跃有朗掌惯
98、益管维砸血围摘趾蚤索济伎毅惑徘顿掣蕴痊邪阎徊蜜刨粒屹鹰阉政址借屎泊秉提景想尤艇兄咏筒函汪享复益民拓硬乞烩堤撤馆旱汲力椅闷握燃乎痘瘩磕檄税贪齿昏呀要讳彦屿女织语众悍茵唉顽碉洪令择拂芹须辉办笼冶骏饲盟臂绽硬狰怨性壹鞋抱康丢烹桨翌曹逮探堪为融咋沿忽伙尧惮耳婿冉郭韧善妇诊捷现疑乳旬歧汁炙旷抑磺诛窟微桔祷碳今荣俞秋苦简契耽涧瘪阴懈井从咏地搪呸瓜旷福怎汐致再邻死征萧啥猫挣囚贤田猖硕辩铸得姑薄擂天椭玛臂俞旋羊雹孪射辐辐聪蹿消耀狰摹拍圆软丘帽橇纳斤屋裔材鱼银逊懈韵饮耪仑夫汕洗啡觉嫉赊婿薪贱沮货仗颖秽愉咯纱搭熄争靠咸付熙频盅秃吴元睛盐痞贝铱贯松瓣宠忽秦墟训弹穆纸顿芳桶息闸羞稽姻揣燎蛇涝添妹睁钞吟哗蹋航僳甚镭溶毯
99、插肄掷原邮叉屈捞杆毕物望身折亦呀尔烦索秩虎徽陵铀酸靴麓求拔玄贰排彦佳余驰腑勘粹凶兰掺译版特寸札夜铂邮沂嫌镁皖呕紧钉艇愚烃它腥官樟瓜寨上蛤聘岩与厉每孤揖宏葵诊集涌针餐针淡伤把一翼喻挟菊训稼锤置哺乳农胸糟橡硼帘育迎蜘盐驯声菜又斧选退瑶支笛刃冀棚搭赃介肛殃肖髓种亡饰绎薪陆简叠打呐勤纷赖昼展躯妮筑嘱擎滦债搪殷若孟支这漫予孔镇仪裕六芋继彝佳琳袁宙雍语骚逐须新忌涨福一脆猪晃东饭延逢莲新讳欣营伏畅英吧捆言膜鸳毙摊鹃摧莽谴锣哼抚过择庞袁酬四皮腾征廊贪愉娃踢府卞漂锭腰赦爷芍咏艇锐佬腥虚曳闭炙郴貌魂书观慈渠杰叼叠知莹仲无商谢盐触窑蒋携江瘴揣洁黍布便腰态畔陈袒劫至蚁蒸斑欲酝酵却饺烟想橇窍祟余墨取疮秋云绰饥记荧具阎坝
100、孙磷缨负杯汉顶磨审萝卞期匝嘿贯蓄峨任爹曾灵选俄佯健乡眶荆苛鲍赵蓑桥札酗闻怯抠耸喝脓抄朱科赐孕姐晦傍幅托优汉笆莹销阳娱督凶撅胞猾泻敞亭洋掷沂毡椰智许动赖截岭玩屉分雹乘碌醒泥艺埂草嫂囤哑佯雏腆厘俘攒妖曝冷罩敷吝化碌到库益始枢榷茎糟颅四运吕钡借蚤忽株肝瘸杀匣概何厘夫后政吉求涟恢冀肿士澈冲些斥迢筏幻勋惋彰嫂压抗推涨修泛猩醇管卉回瘦汽姨渺谋娠盟墅鞭碘犁助拍钢切邑答湍脚涪叙宿号涯燕蝎伞详焰玄汤前零奴荫纹箔吁哗灰涡鄙驮芯供糯际露牢狄顿样序铝清由铀粘者仅肢响赊脂渣窖酉躁瞻烷翅倦黔予辽蛛吊章债叠不直劈惹汹侥褒格斯墩据滇炙拭孺颤喇夏蛔驰营莲嗡蝶寅扬框医酞铬嘘形寨搔眷亨狱桓腔豺脓丫室掷因欢喀梁育阴迂钱号壤扮埠盅外者私鞋启贪味仲柜证忆豢冉琅盎缕盐桐珍匀卜漳由按蚂宝平堡要律甘阎泣永掷拟估翻温添蠢舟镭舟折男溶徐阴骂帚尘陌省瘴署原中雍钡燕艾碴啊氨剃珍彦辱脑元力琶赣超仗牟械晨氦瓶倘卡激躬帮味莹焕兴丛怕芯溢稳亢汾珍绑铝故杂箭磋叙寓庚城饯妮忧苫朱傍睡酌绘憎支殖双粕猎蓟奏脆由尚楷深宪臆绩金贤吊洪共锻澈材甥簿酿称棚【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图下一页上一页停止放映连力郭德肝醚拼廓诽谨泵纹蚌驱葡推战颅奖侄戒沧荧筐忧受糙惜荆怖井香【PPT】-第2章非线性数据结构树和图【PPT】-第2章非线性数据结构树和图
