吉林大学数据结构课件 第四章 树

树的基本概念二叉树(BinaryTree)线索化二叉树(ThreadedBinaryTree)树与森林(Tree&Forest)压缩与哈夫曼树(HuffmanTree)树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。第3页例[Joe的后代]下图给出了Joe的后代，并按层次方式组织，其中Joe在最顶层。Joe的孩子（Ann，Mary和John）列在下一层，在父母和孩子间有一条边。在层次表示中，非常容易地找到Ann的兄弟姐妹，Joe的后代，Chris的祖先等。例[政府机构]下图是联邦政府各分支机构的层次图。在最顶层是整个联邦政府。层次结构的下一级，是其主要的隶属单位(例如不同的部)。每个部可进一步细分。这些分支在层次结构的下一级画出。例如，国防部分成陆军、海军、空军和海军陆战队。在每个机构及其分支机构间都有一条边。图中数据即为整体-部分关系的例子。例[软件工程]下面考察另一种层次数据——软件工程中的模块化技术。通过模块化，可以把大的复杂的任务分成一组小的不太复杂的任务。模块化的目标是把软件系统分成许多功能不相关的部分或模块以便于进行相对独立的开发。由于解决几个小问题比解决大问题更容易一些，因此模块化方法可以缩短整个软件的开发时间。另外，不同的程序员可以同时开发不同的模块。如果有必要，每个模块可以再细分，下图给出了某文字处理器的一种可行的模块分解图。文字处理器的模块层次结构定义4.1.1一个树（或树形）就是一个有限非空的结点集合T，其中：有一个特别标出的被称为该树（或树形）之根root(T)的结点；其余结点（根除外）被分成m0个不相交的集合T1，T2，…，Tm，且T1，T2，…，Tm又都是树（或树形）。树（或树形）T1，T2，…，Tm被称作root(T)的子树（或子树形）。有序树：树中结点的各个子树从左至右有序。无序树：树中结点的各个子树从左至右无序。定义4.1.2树是包含n(n≥1)个结点且满足如下条件的有限集合(非递归定义)：存在一个唯一的结点v0，它没有前驱结点，称为树的根（或根结点）；任何非根结点都有且仅有一个前驱结点，称为该结点的父结点；任何结点都可能有多个（n1）后继结点，称之为该结点的子结点；若某结点没有后继结点，则称之为叶结点。任一非根结点vk都有且仅有一条从v0到该结点的结点序列（或曰路径）v0v1…vk，其中vi是vi1（1ik）与线性结构的比较线性结构树结构第一个数据元素根结点(无前驱)(无前驱)最后一个数据元素多个叶子结点(无后继)(无后继)其它数据元素树中其它结点(一个前驱、一个后继)(一个前驱、多个后继)基本术语结点的度（或者次数）:一个结点的子结点的数目(分支的个数)树的度:树中所有结点的度的最大值叶子结点:度为零的结点分支结点:度大于零的结点结点的层次:⑴root(T)层数为零；⑵其余结点的层数为其前驱结点的层数加1.结点的度、树的度叶子结点、分支结点结点的层次:A的层数为0B、C、D的层数为1E、G、H、I的层数为2F的层数为3AECDBIHGF层次0层次1层次2层次3图6.1树基本术语边:树形中结点间的连线被称为边路径:若树形T中存在结点序列vmvm+1…vmk(1kT的最大层数)满足vi+1是vi的子结点（mimk1），则称此结点序列为vm到vmk的路径,该路径所经历的边数nm被称为路径长度树的高度(深度)：树中叶子结点所在的最大层次一棵树中若存在结点vm到vn的路径，则称vn为vm的子孙结点，vm为vn的祖先结点。边、路径、路径长度树的高度子孙结点、祖先结点。从A到F的路径为A-B-E-F，路径长度为3。树的高度为3AECDBIHGF层次0层次1层次2层次3图6.1树结点(node)结点的度(degree)分支(branch)结点叶(leaf)结点子女(child)结点双亲(parent)结点兄弟(sibling)结点祖先(ancestor)结点子孙(descendant)结点结点所处层次(level)树的高度(depth)树的度(degree)树的表示1.集合嵌套表示法2.凹入表示法3.广义表表示法4.树形表示法ACBDE1ABCDE2ABCDE4A(B,C(D,E))3二叉树(BinaryTree)二叉树的主要性质和定义●定义：二叉树是结点的有限集合，它必须满足下面的一个条件：（1）它是空集。（2）它由一个根结点,根结点的左右子树构成，且其左右子树满足二叉树定义。●二叉树的特征①二叉树每个结点的最多有2个子结点；②二叉树的子树有左右之分。二叉树的五种不同形态二叉树的性质引理4.2.1二叉树中层数为i的结点至多有2i个，i≧0。证明：用数学归纳法。当i=0时，仅有一个根结点，其层数为0，因此i=0时引理成立。假定当i=j(j≥0)时，引理成立，即第j层上至多有2j个结点。对于二叉树的任意结点，其子结点个数最大为2，故第j+1层上至多有2*2j=2j+1个结点，因此当i=j+1时，引理成立。由数学归纳法可知，对于所有的i≥0，均有“第i层上至多有2i个结点”。证毕。高度为k的二叉树中至多有??个结点引理4.2.2高度为k的二叉树中至多有2k+1－1(k≧0)个结点。根据引理引理4.2.1第0层上至多有20个结点，第1层上至多有21个结点,……，第k层上至多有2k个结点,因此，高度为k的二叉树中至多有20＋21＋……+2k=2k+1－1个结点。引理4.2.3设T是由n个结点构成的二叉树，其中,叶子结点个数为n0，度为2的结点个数为n2，则有：n0＝n2＋1证明：若设度为1的结点有n1个，总结点个数为n，总边数为e，则n=n0+n1+n2e=n–1(子结点与父结点的连接)e=2n2+n1(所有发出分支的结点)因此，有2n2+n1=n0+n1+n2-1n2=n0-1n0=n2+1满二叉树的定义：一棵高度为k的满二叉树，是具有2k+1－1个结点且高度为k的二叉树(最多节点数目)。由引理4.2.2知，高度为k（非空）二叉树至多有2k+11个结点。满二叉树的特点是：①叶结点都在第k层上；②每个分支结点都有两个子结点；③叶结点的个数等于非叶结点个数加1(根据引理4.2.3和②)可按层次顺序（即按从第0层到第k层，每层由左向右的次序）将一棵满二叉树的所有结点用自然数从1开始编号。564372981013111214151完全二叉树的定义：是一棵具有n个结点，高度为k的二叉树，且树中所有结点对应高度为k的满二叉树中编号由1至n的那些结点。56437298101引理6.4设若将一颗具有n个结点的完全二叉树按层次次序从1开始编号，则对编号为i(1≦i≦n)的结点有：①若i≠1，则编号为i的结点的父结点的编号为i/2。②若2i≦n，则编号为i的结点的左孩子的编号为2i,否则i无左孩子。③若2i＋1≦n，则i结点的右孩子结点编号为2i+1,否则i无右孩子。引理4.2.5n个结点的完全二叉树的高度是log2n.证明：设二叉树高度为k，由定义4.2.3知，完全二叉树的结点个数介于高度为k-1和高度为k的满二叉树的结点数之间，即有：2k-1n≤2k+1-1从而有2k≤n2k+1，即k≤log2nk+1，因为k为整数，故有k=log2n.证毕。请注意:当根结点的层数从1计时，树的高度为log2n」+1。4.2.2二叉树的存储结构1·顺序存储结构●完全二叉树的顺序存储:按层次次序给结点编号，使用一维数组A来存放。A[0]存储二叉树的根结点，A[i]结点的左孩子结点存放在[2i+1]处，而A[i]的右孩子结点存放在A[2i+2]处。顺序存储结构A[0]A[1]A[2]A[3]A[4]A[5]A[6]A[7]A[8]A[9]94176612523627049313123126694175706249●一般二叉树的顺序存储CBA2465731a[0]a[1]a[2]a[3]a[4]ABCa[5]a[6]可能会浪费很多存储空间，单支树就是一个极端情况。2·链式存储结构二叉树诸结点被随机存放在内存空间中，结点之间的关系用指针说明。二叉树的结点结构二叉树结点应包含三个域：数据域data、指针域left（称为左指针）和指针域right（称为右指针），其中左、右指针分别指向该结点的左、右子树的根结点.leftrightdata二叉树链式存储结构ADCBEFG∧∧∧∧∧∧∧∧ACBEFDG(1)搜索二叉树中符合数据域条件的结点算法Find(t,item.q)/*在二叉树T中搜索Data域之值为item的结点，指针t指向T之根，指针q指向欲搜索的结点*/Find1.[t?]IFtTHEN(q.RETURN.).IFData(t)itemTHEN(qt.RETURN.).Find2.[递归]Find(Left(t),item.p).IFpTHEN(qp.RETURN.).Find(Right(t),item.q).RETURN.▐(2)从二叉树中删除给定结点及其左右子树算法DST(t)/*root指向一棵二叉树T之根，本算法从T中删除给定结点t(是简称，其含义是：t是指向该结点的指针)及其左右子树；DST是DelSubTree之缩写*/DST1.[t?]IFtTHENRETURN.DST2.[troot?]IFtrootTHEN(Del(t).root.RETURN.)DST3.[找t的父结点q]pt.Father(root,p.q).DST4.[修改q的指针域]IFLeft(q)pTHENLeft(q).IFRight(q)pTHENRight(q).DST5.[删除p及其子树]Del(p).▐算法Del(p)/*删除结点p及其左右子树*/Del1.[p?]IFpTHENRETURN.Del2.[递归删除]Del(Left(p)).Del(Right(p)).AVAILp.▐(3)搜索父结点算法Father(t,p.q)/*指针t指向二叉树T之根，在T中搜索给定结点p之父结点；q指向p之父结点；本算法使用了递归*/Father1.[t?]IFtTHEN(q.RETURN.)Father2.[t为所求?]IFLeft(t)pORRight(t)pTHEN(qt.RETURN.)Father3.[递归]Father(Left(t),p.qL).IFqLTHEN(qqL.RETURN.)ELSE(Father(Right(t),p.qR).qqR.RETURN.)▐问题：如何提高执行效率？三叉链表表示法Leftdataparentright4.2.4二叉树的遍历●二叉树的遍历：按照一定次序访问树中所有结点，并且每个结点的值仅被访问一次的过程。先根（中根、后根）序遍历次序是树中结点的一个有序序列，称为二叉树的先根（中根、后根）序列。遍历方式先根序列：DLR中根序列：LDR后根序列：LRDLDR先根序遍历中根序遍历后根序遍历步骤一访问根遍历左子树遍历左子树步骤二遍历左子树访问根遍历右子树步骤三遍历右子树遍历右子树访问根中根遍历二叉树算法的框架是：若二叉树为空，则空操作；否则–中根遍历左子树(L)；–访问根结点(V)；–中根遍历右子树(R)。遍历结果a+b*c-d-e/f中根遍历(InorderTraversal，中序遍历)表达式语法树二叉树递归的中根遍历算法算法Inorder（t）IN1[递归遍历]IFt≠NULLTHEN（Inorder（left（t））.PRINT（data（t））.Inorder（right（t））.）▌先根遍历(PreorderTraversal，前/先序遍历)先根遍历二叉树算法的框架是若二叉树为空，则空操作；否则–访问根结点(V)；–先根遍历左子树(L)；–先根遍历右子树(R)。遍