《数据结构与算法》PPT课堂课件-第7章-树.pdf

《《数据结构与算法》PPT课堂课件-第7章-树.pdf》由会员分享，可在线阅读，更多相关《《数据结构与算法》PPT课堂课件-第7章-树.pdf（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2021/6/1317.0.1树树的的原原型型 社社会会生生活活中中：家家族族的的族族谱谱，政政府府自自上上至至下下设设置置的的机机构构体体系系，学学校校的的管管理理体体系系，公公司司的的管管理理体体系系， 7.0.2树树的的应应用用 操操作作系系统统中中：文文件件系系统统的的组组织织， 编编译译系系统统中中：复复合合语语句句的的句句法法， (二二元元运运算算)表表达达式式的的表表示示中中：表表达达式式树树， 编编码码与与解解码码中中：Huffman树树， 数数据据对对象象的的表表示示中中：大大量量地地用用到到树树。第第七七章章 树树2021/6/132 7.1 树树的的定定义义定定义义：树树

2、是是n(n0)个个结结点点的的有有限限集集T，其其中中：有有且且仅仅有有一一个个特特定定的的结结点点，称称为为树树的的根根当当n1时时，其其余余结结点点可可分分为为m(m0)个个互互不不相相交交的的有有限限集集T1,T2,Tm，其其中中每每一一个个集集合合本本身身又又是是一一棵棵树树，称称为为根根的的子子树树特特点点：树树中中至至少少有有一一个个结结点点根根树树中中各各子子树树是是互互不不相相交交的的集集合合2021/6/133A只只有有根根结结点点的的树树ABCDEFGHIJKLM有有子子树树的的树树根根子子树树2021/6/134基基本本术术语语结结点点(node)表表示示树树中中的的元元

3、素素结结点点的的度度(degree)结结点点拥拥有有的的子子树树数数叶叶子子(leaf)度度为为0的的结结点点孩孩子子(child)结结点点子子树树的的根根称称为为该该结结点点的的孩孩子子双双亲亲(parents)孩孩子子结结点点的的上上层层结结点点兄兄弟弟(sibling)同同一一双双亲亲的的孩孩子子树树的的度度一一棵棵树树中中最最大大的的结结点点度度数数结结点点的的层层次次(level)从从根根结结点点算算起起，根根为为第第一一层层，它它的的孩孩子子为为第第二二层层深深度度(depth)树树中中结结点点的的最最大大层层次次数数森森林林(forest)m(m 0)棵棵互互不不相相交交的的树树

4、的的集集合合2021/6/135ABCDEFGHIJKLM结结点点A的的度度：3结结点点B的的度度：2结结点点M的的度度：0叶叶子子：K，L，F，G，M，I，J结结点点A的的孩孩子子：B，C，D结结点点B的的孩孩子子：E，F结结点点I的的双双亲亲：D结结点点L的的双双亲亲：E结结点点B，C，D为为兄兄弟弟结结点点K，L为为兄兄弟弟树树的的度度：3结结点点A的的层层次次：1结结点点M的的层层次次：4树树的的深深度度：4结结点点A是是结结点点F，G的的祖祖先先2021/6/1367.2 树树的的遍遍历历树树的的遍遍历历遍遍历历依依次次对对树树中中结结点点访访问问一一次次且且仅仅访访问问一一次次常常

5、用用方方法法先先序序遍遍历历：先先访访问问树树的的根根结结点点，然然后后从从左左到到右右依依次次先先序序遍遍历历根根的的每每棵棵子子树树中中序序遍遍历历：先先中中序序遍遍历历第第一一棵棵子子树树，然然后后访访问问根根，接接着着依依次次对对其其余余子子树树进进行行遍遍历历后后序序遍遍历历：先先依依次次后后序序遍遍历历每每棵棵子子树树，然然后后访访问问根根结结点点按按层层次次遍遍历历：先先访访问问第第一一层层上上的的结结点点，然然后后依依次次遍遍历历第第二二层层，第第n层层的的结结点点2021/6/137ABCDEFGHIJKLMNO先先序序遍遍历历：后后序序遍遍历历：层层次次遍遍历历：ABE F

6、 I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNO中中序序遍遍历历：E B I F G AC J HKN L OMD2021/6/138 7.3 树树的的存存储储结结构构7.3.1 父父结结点点数数组组表表示示法法实实现现：定定义义一一个个一一维维数数组组存存放放树树的的每每个个结结点点的的父父结结点点。特特点点：可可唯唯一一的的表表示示任任 何何一一棵棵树树 找找双双亲亲容容易易，找找 孩孩子子难难2021/6/1397.3.1 父父结结点点数数组组表表示示法法效效率率分分析析： 寻寻找找一一个个结结点点的的

7、父父结结点点只只需需要要O(1)O(1)时时间间。 对对于于涉涉及及查查询询儿儿子子结结点点和和兄兄弟弟结结点点信信息息的的运运算算，可可能能要要遍遍历历整整个个数数组组。 改改进进： 约约定定让让树树结结点点的的编编号号满满足足：儿儿子子结结点点的的编编号号大大于于父父结结点点的的编编号号，且且兄兄弟弟结结点点的的编编号号是是从从左左到到右右递递增增的的。 在在此此约约定定下下，结结点点k的的儿儿子子只只要要在在编编号号大大于于k的的结结点点中中找找；结结点点k的的左左兄兄弟弟只只要要在在编编号号小小于于k的的结结点点中中找找；结结点点k的的右右兄兄弟弟只只要要在在编编号号大大于于k的的结结

8、点点中中找找。 简简单单的的办办法法是是按按层层次次遍遍历历的的顺顺序序编编号号。2021/6/13107.3.2 双双亲亲表表示示法法实实现现：定定义义结结构构数数组组存存放放树树的的结结点点数数据据域域，每每个个结结点点含含两两个个域域：数数据据域域：存存放放结结点点本本身身信信息息双双亲亲域域：指指示示本本结结点点的的双双亲亲结结点点在在数数组组中中位位置置特特点点：找找双双亲亲容容易易，找找孩孩子子难难2021/6/1311abcdefhgiacdefghib012235551096012345789dataparent0号号单单元元不不用用或或存存结结点点个个数数如何找孩子结点202

9、1/6/13127.3.3 7.3.3 孩孩子子表表示示法法多多重重链链表表：每每个个结结点点有有多多个个指指针针域域，分分别别指指向向其其子子树树的的根根结结点点同同构构：结结点点的的指指针针个个数数相相等等，为为树树的的度度D结结点点不不同同构构：结结点点指指针针个个数数不不等等，为为该该结结点点的的度度ddata child1 child2 . childDdata degree child1 child2 . childd2021/6/13137.3.3 7.3.3 孩孩子子表表示示法法孩孩子子链链表表：每每个个结结点点的的孩孩子子结结点点用用单单链链表表存存储储，再再用用含含n个个元

10、元素素的的结结构构数数组组指指向向每每个个孩孩子子链链表表孩孩子子结结点点：typedef struct node int child; /该该结结点点在在表表头头数数组组中中下下标标 struct node *next; /指指向向下下一一孩孩子子结结点点 JD;表表头头结结点点：typedef struct tnode datatype data; /数数据据域域 struct node *fc; /指指向向第第一一个个孩孩子子结结点点 TD; TD tM; /t0不不用用2021/6/1314abcdefhgi6012345789acdefghibdatafc 2 3 4 5 9 7 8

11、 6如何找双亲结点2021/6/1315改改进进：带带双双亲亲的的孩孩子子链链表表 （将将双双亲亲表表示示法法和和孩孩子子表表示示法法结结合合）612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parentabcdefhgi2021/6/13167.3.4 左左儿儿子子右右兄兄弟弟表表示示法法（二二叉叉树树表表示示法法）实实现现：用用二二叉叉链链表表作作树树的的存存储储结结构构，链链表表中中每每个个结结点点的的两两个个指指针针域域分分别别指指向向其其第第一一个个孩孩子子结结点点和和下下一一个个兄兄弟弟结结点点特特点点操操作作容容易易破破坏坏了了树

12、树的的层层次次abcdefhgi a b c d e f g h i2021/6/13177.4 二二叉叉树树定定义义：二二叉叉树树是是n(n 0)个个结结点点的的有有限限集集，它它或或为为空空树树(n=0)，或或由由一一个个根根结结点点和和两两棵棵分分别别称称为为左左子子树树和和右右子子树树的的互互不不相相交交的的二二叉叉树树构构成成特特点点每每个个结结点点至至多多有有二二棵棵子子树树(即即不不存存在在度度大大于于2的的结结点点)二二叉叉树树的的子子树树有有左左、右右之之分分，且且其其次次序序不不能能任任意意颠颠倒倒五五种种基基本本形形态态A只有根结点的二叉树空二叉树AB右子树为空AB左子树

13、为空ABC左、右子树均非空2021/6/13187.4.1 二二叉叉树树性性质质 性性质质1：证证明明：用用归归纳纳法法证证明明之之 i=1时时，只只有有一一个个根根结结点点， 是是对对的的 假假设设对对所所有有j(1 j1，则则其其双双亲亲是是 i/2 (2) 如如果果2in，则则结结点点i无无左左孩孩子子；如如果果2i n，则则其其左左 孩孩子子是是2i (3) 如如果果2i+1n，则则结结点点i无无右右孩孩子子；如如果果2i+1 n， 则则其其右右孩孩子子是是2i+1问问题题：有有一一棵棵完完全全二二叉叉树树，其其结结点点个个数数为为578， 求求此此二二叉叉树树中中叶叶子子结结点点的的

14、个个数数？2021/6/13237.5 二二叉叉树树的的实实现现7.5.1 顺顺序序存存储储结结构构实实现现：按按满满二二叉叉树树的的结结点点层层次次编编号号，依依次次存存放放二二叉叉树树中中的的数数据据元元素素特特点点：结结点点间间关关系系蕴蕴含含在在其其存存储储位位置置中中浪浪费费空空间间，适适于于存存满满二二叉叉树树和和完完全全二二叉叉树树abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 112021/6/13247.5.2 二二叉叉树树的的结结点点度度表表示示法法( (另另一一种种无无边边表表示示) )基基本本想想法法： 若若将将所所有

15、有的的结结点点按按后后序序列列表表从从1 1开开始始编编号号，并并在在每每个个结结点点中中附附加加一一个个0 0到到3 3之之间间的的整整数数，以以表表示示该该结结点点的的分分叉叉特特征征。该该整整数数为为0 0时时，表表示示相相应应的的结结点点无无儿儿子子；为为1 1时时，表表示示相相应应结结点点只只有有左左儿儿子子；为为2 2时时，表表示示相相应应结结点点只只有有右右儿儿子子；为为3 3时时，表表示示相相应应结结点点既既有有左左儿儿子子又又有有右右儿儿子子。2021/6/13257.5.3 用用指指针针实实现现二二叉叉树树7.5.3.1 二二叉叉链链表表ABCDEFG AB C D E F

16、 Gtypedef struct btnode *btlink;typedef struct btnode TreeItem element; btlink left, right;Btnode; left element right n+1个个问问题题：在在n个个结结点点的的二二叉叉链链表表中中，有有 几几 个个空空指指针针域域？2021/6/13267.5.3.2 三三叉叉链链表表 left element parent rightABCDEFG A B C D E F Gtypedef struct btnode *btlink;typedef struct btnode TreeIte

17、m element; btlink left, right,parent;Btnode;2021/6/13277.6 树树与与二二叉叉树树转转换换ACBED树ABCDE二叉树 A B C D E A B C D E A B C D E 对对应应存存储储存存储储解解释释解解释释2021/6/13287.7 将将树树转转换换成成二二叉叉树树加加线线：在在兄兄弟弟之之间间加加一一连连线线抹抹线线：对对每每个个结结点点，除除了了其其左左孩孩子子外外，去去除除其其与与其其余余孩孩子子之之间间的的关关系系旋旋转转：以以树树的的根根结结点点为为轴轴心心，将将整整树树顺顺时时针针转转45ABCDEFGHIAB

18、CDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI问问题题：为为什什么么树树转转换换成成的的二二叉叉树树根根的的右右子子树树一一定定为为空空？2021/6/13297.8 将将二二叉叉树树转转换换成成树树加加线线：若若p结结点点是是双双亲亲结结点点的的左左孩孩子子，则则将将p的的右右孩孩子子，右右孩孩子子的的右右孩孩子子，沿沿分分支支找找到到的的所所有有右右孩孩子子，都都与与p的的双双亲亲用用线线连连起起来来抹抹线线：抹抹掉掉原原二二叉叉树树中中双双亲亲与与右右孩孩子子之之间间的的连连线线调调整整：将将结结点点按按层层次次排排列列，形形成成树树结结构构ABCDEFGHIABC

19、DEFGHIABCDEFGHIABCDEFGHIABCDEFGHI2021/6/13307.9 森森林林转转换换成成二二叉叉树树将将各各棵棵树树分分别别转转换换成成二二叉叉树树将将每每棵棵树树的的根根结结点点用用线线相相连连以以第第一一棵棵树树根根结结点点为为二二叉叉树树的的根根，再再以以根根结结点点为为轴轴心心，顺顺时时针针旋旋转转，构构成成二二叉叉树树型型结结构构ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ2021/6/13317.10 二二叉叉树树转转换换成成森森林林抹抹线线：将将二二叉叉树树中中根根结结点点与与其其右右孩孩子子连连线线，及及沿沿右右分

20、分支支搜搜索索到到的的所所有有右右孩孩子子间间连连线线全全部部抹抹掉掉，使使之之变变成成孤孤立立的的二二叉叉树树还还原原：将将孤孤立立的的二二叉叉树树还还原原成成树树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ2021/6/13327.11 二二叉叉树树的的遍遍历历方方法法先先序序遍遍历历：先先访访问问根根结结点点,然然后后分分别别先先序序遍遍历历左左子子树树、右右子子树树中中序序遍遍历历：先先中中序序遍遍历历左左子子树树，然然后后访访问问根根结结点点，最最后后中中序序遍遍历历右右子子树树后后序序遍遍历历：先先后后序序遍遍历历左左、右右子子树树，然然后后访访

21、问问根根结结点点按按层层次次遍遍历历：从从上上到到下下、从从左左到到右右访访问问各各结结点点DLRLDR、LRD、DLRRDL、RLD、DRL2021/6/1333ADBCD L RAD L RD L RBDCD L R先序遍历序列：A B D C先序遍历:2021/6/1334ADBCL D RBL D RL D RADCL D R中序遍历序列：B D A C中序遍历:2021/6/1335ADBC L R DL R DL R DADCL R D后序遍历序列： D B C A后序遍历:B2021/6/1336-+/a*b-efcd先先序序遍遍历历：中中序序遍遍历历：后后序序遍遍历历：层层次次

22、遍遍历历：- + a * b - c d / e f-+a*b-cd/ef- +a *b - c d/e f-+a*b-c d/e f2021/6/13377.12 二二叉叉树树的的应应用用哈哈夫夫曼曼树树(Huffman) 带带权权路路径径长长度度最最短短的的树树定定义义路路径径：从从树树中中一一个个结结点点到到另另一一个个结结点点之之间间的的分分支支构构成成这这两两个个结结点点间间的的路路径径路路径径长长度度：路路径径上上的的分分支支数数树树的的路路径径长长度度：从从树树根根到到每每一一个个结结点点的的路路径径长长度度之之和和树树的的带带权权路路径径长长度度：树树中中所所有有带带权权结结点

23、点的的路路径径长长度度之之和和Huffman树树设设有有n个个权权值值w1,w2,wn，构构造造一一棵棵有有n个个叶叶子子结结点点的的二二叉叉树树，每每个个叶叶子子的的权权值值为为wi,则则wpl最最小小的的二二叉叉树树2021/6/1338例例 有有4个个结结点点，权权值值分分别别为为7，5，2，4，构构造造有有4个个叶叶子子结结点点的的二二叉叉树树abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=352021/6/1339构构造造Huffman树树的的方方法法Huf

24、fman算算法法构构造造Huffman树树步步骤骤根根据据给给定定的的n个个权权值值w1,w2,wn，构构造造n棵棵只只有有根根结结点点的的二二叉叉树树，令令起起权权值值为为wj在在森森林林中中选选取取两两棵棵根根结结点点权权值值最最小小的的树树作作左左右右子子树树，构构造造一一棵棵新新的的二二叉叉树树，置置新新二二叉叉树树根根结结点点权权值值为为其其左左右右子子树树根根结结点点权权值值之之和和在在森森林林中中删删除除这这两两棵棵树树，同同时时将将新新得得到到的的二二叉叉树树加加入入森森林林中中重重复复上上述述两两步步，直直到到只只含含一一棵棵树树为为止止，这这棵棵树树即即哈哈夫夫曼曼树树20

25、21/6/1340例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d4611182021/6/1341例例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3 111429 7823 1135887151429233581111358191429238715113581929 231487152929148715291135819234211358192342291487152958113581923422914871529581002021/6/1342Huffman树树应应用用最最佳佳判判定定树树等级分数段比例ABCDE059606970

26、79 8089 901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70EADECa80a70a60alchild=NULL f-rchild=NULLp只只有有左左子子树树或或右右子子树树p只只有有左左子子树树，用用p的的左左孩孩子子代代替替p (1)(2)p只只有有右右子子树树，用用p的的右右孩孩子子代代替替p (3)(4)p左左、右右子子树树均均非非空空沿沿p左左子子树树的的根根C的的右右子子树树分分支支找找到到S，S的的右右子子树树为为空空，将将S的的左左子子树树成成为为S的的双双

27、亲亲Q的的右右子子树树，用用S取取代代p (5)若若C无无右右子子树树，用用C取取代代p (6)2021/6/1348SQPLP中序遍历：Q S PL PSQPL中序遍历：Q S PL(2)SPPLQ中序遍历：PL P S QSPLQ中序遍历：PL S Q(1)2021/6/1349中序遍历：P PR S QSPRQ中序遍历：PR S Q(3)SPPRQ中序遍历：Q S P PRSQPR中序遍历：Q S PR(4)SQPRP2021/6/1350FPCPRCLQQLSSL中序遍历：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍历：CL C QL Q SL S PR F(5)FPCPRCL中序遍历：CL C P PR FFCPRCL中序遍历：CL C PR F(6)2021/6/1351删删除除算算法法例805012060110150557053删删除除508060120110150557053删删除除60805512011015053701042581354删删除除1084255134删删除除58425413