DS05_树a_陈越主编_数据结构

1第4章树§4.1引子哲学宗教文学医药卫生农业科学工业技术哲学理论世界哲学欧洲哲学宗教宗教分析研究宗教理论与概况佛教宗教与社会政治宗教与科学破除迷信综合电工技术计算机建筑科学水利工程………一般性技术计算机软件电子模拟计算机微型计算机计算机的应用图书……软件工程程序语言编译程序操作系统………2第4章树§4.1.2查找查找（Searching）的定义【定义】所谓静态查找，是指集合中的记录是固定的，不涉及对记录的插入和删除操作，而仅仅是按关键字查找记录。所谓动态查找，是指集合中的记录是动态变化的，即记录可能要发生插入和删除操作。查找的效率主要用“平均查找长度”（AverageSearchLength，ASL）来衡量。查找可分静态和动态两种情况考虑；手段分为利用比较和利用映射两种思路。根据某个给定的关键字K，从集合R中找出关键字与K相同的记录，这个过程称为“查找”。3typedefstruct{ElementType*Element;/*数组的起始地址*/intLength;/*数组长度*/}StaticTable;typedefstructNode*PtrToNode;typedefPtrToNodeList;typedefPtrToNodePosition;structNode{ElementTypeElement;/*结点的值域*/PtrToNodeNext;/*下一个结点的指针域*/};第4章树线性表的数组存储结构的定义：线性表的链表存储结构的定义：§4.1.2查找静态查找：通常是从一个线性表中查找数据元素012345678910StaticTable104方法1：顺序查找第4章树顺序查找算法的时间复杂度为O(n)。§4.1.2查找intSequentialSearch(StaticTable*Tbl,ElementTypeK){/*在表Tbl中查找关键字为K的数据元素，数据元素：Tbl[1]~Tbl[n]*/inti;Tbl-Element[0]=K;/*建立哨兵*/for(i=Tbl-Length;Tbl-Element[i]!=K;i--);returni;/*查找成功返回数据元素所在单元下标；查找不成功返回0*/}下标为0的存储空间是临时工作空间是否需要i=0？012345678910Tbl10K5方法2：二分查找第4章树当线性表中数据元素是按大小排列存放时，可以改进顺序查找算法，以得到更高效率的新算法——二分法(折半查找)。§4.1.2查找假设n个数据元素的关键字满足有序（从小到大或从大到小）并且是连续存放的（数组），那么可以进行二分查找。二分查找是每次在要查找的数据集合中取出中间元素关键字Kmid与要查找的关键字K进行比较，根据比较结果确定是否要进一步查找。当Kmid=K，查找成功；否则，将在Kmid的左半部分（当KmidK）或者右半部分（当KmidK）继续下一步查找。以此类推，每步的查找范围都将是上一次的一半。6[例4.1]假设有13个数据元素，它们的关键字为51，202，16，321，45，98，100，501，226，39，368，5，444。若按关键字由小到大顺序存放这13个数，二分查找关健字为444的数据元素过程如下：第4章树§4.1.2查找51639455198100202226321368444501123456789101112131、left=1,right=13;mid=(1+13)/2=7:100444;2、left=mid+1=8,right=13;mid=(8+13)/2=10:321444;3、left=mid+1=11,right=13;mid=(11+13)/2=12:444=444查找结束。7[例4.2]仍然以上面13个数据元素构成的有序线性表为例，二分查找关健字为43的数据元素如下：第4章树§4.1.2查找51639455198100202226321368444501123456789101112131、left=1,right=13;mid=(1+13)/2=7:10043;2、left=1,right=mid-1=6;mid=(1+6)/2=3:3943;3、left=mid+1=4,right=6;mid=(4+6)/2=5:5143;4、left=4,right=mid-1=4;mid=(4+4)/2=4:4543;5、left=4,right=mid-1=3;leftright?查找失败，结束。8二分查找算法第4章树intBinarySearch(StaticTable*Tbl,ElementTypeK){/*在表Tbl中查找关键字为K的数据元素*/intleft,right,mid,NoFound=-1;left=1;/*初始左边界*/right=Tbl-Length;/*初始右边界*/while(left=right){mid=(left+right)/2;/*计算中间元素坐标*/if(KTbl-Element[mid])right=mid-1;/*调整右边界*/elseif(KTbl-Element[mid])left=mid+1;/*调整左边界*/elsereturnmid;/*查找成功，返回数据元素的下标*/}returnNotFound;/*查找不成功，返回-1*/}二分查找算法的时间复杂度为O(logN)§4.1.2查找9631479510211811个元素的判定树第4章树§4.1.2查找判定树上每个结点需要的查找次数刚好为该结点所在的层数;查找成功时查找次数不会超过判定树的深度n个结点的判定树的深度为[log2n]+1折半查找的算法复杂度为O(log2n)11个元素的二分查找判定树ASL=(4*4+4*3+2*2+1)/11=310第4章树§4.2树的定义、表示和术语树（Tree）是n（n≥0）个结点构成的有限集合。当n=0时，称为空树；对于任一棵非空树（n0），它具备以下性质：1.树中有一个称为“根（Root）”的特殊结点，用r表示；2.其余结点可分为m(m0)个互不相交的有限集T1，T2，...，Tm，其中每个集合本身又是一棵树，这些树称为原来树的“子树（SubTree）”。每个子树的根结点都与r有一条相连接的边，r是这些子树根结点的“父结点(Parent)”。子树是不相交的；除了根结点外，每个结点有且仅有一个父结点；一棵N个结点的树有N-1条边。树的定义递归的定义形式11第4章树§4.2树的定义、表示和术语(a)树TABCDFGHIJKLMECHBFGLDIJKME(b)子树TA1(c)子树TA2(d)子树TA3(e)子树TA4树与非树ABCDEFGHABCDEFGHABCDEFGH12树的一些基本术语1.结点的度（Degree）：一个结点的度是其子树的个数。2.树的度：树的所有结点中最大的度数。3.叶结点（Leaf）：是度为0的结点；叶结点也可称为端结点。4.父结点（Parent）：有子树的结点是其子树的根结点的父结点。5.子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点。6.兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点。第4章树§4.2树的定义、表示和术语ABCDFGHIJKLM7.分支：树中两个相邻结点的连边称为一个分支。8.路径和路径长度：从结点n1到nk的路径被定义为一个结点序列n1,n2,…,nk，对于1ik,ni是ni+1的父结点。一条路径的长度为这条路径所包含的边（分支）的个数。9.祖先结点(Ancestor)：沿树根到某一结点路径上的所有结点都是这个结点的祖先结点。10.子孙结点(Descendant)：某一结点的子树中的所有结点是这个结点的子孙。11.结点的层次（Level）：规定根结点在1层，其它任一结点的层数是其父结点的层数加1。12.树的高度（Height）：树中所有结点中的最大层次是这棵树的高度（也有把根定义成高度为1的）。13第4章树§4.3二叉树【定义】一棵二叉树T是一个有穷的结点集合。这个集合可以为空，若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。可见左子树和右子树还是二叉树。二叉树具体五种基本形态（1）空二叉树；（2）只有根结点的二叉树；（3）只有根结点和左子树TL的二叉树；（4）只有根结点和右子树TR的二叉树；（5）具有根结点、左子树TL和右子树TR的二叉树。ФTLTRTLTR(a)(b)(c)(d)(e)二叉树的定义递归的定义形式二叉树与树不同，除了每个结点至多有两棵子树外，子树有左右顺序之分。例如，下面两个树按一般树的定义它们是同一个树；而对于二叉树来讲，它们是不同的两个树。14特殊二叉树第4章树§4.3二叉树二叉树的深度小于结点数N，可以证明平均深度是)NO(“完美二叉树(PerfectBinaryTree)”。（也称为满二叉树）。BACD13765410982ABCDEHIJFG一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为“完全二叉树(CompleteBinaryTree)”。1211KL151413MNO“斜二叉树(SkewedBinaryTree)”（也称为退化二叉树）；13765410982ABCDEHKJFG15第4章树§4.3二叉树二叉树的几个重要的性质一个二叉树第i层的最大结点数为：2i-1，i1。对任何非空的二叉树T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系n0=n2+1。深度为k的二叉树有最大结点总数为：2k-1，k1。ABCDEKJFHn0=4，n1=2n2=3n0=n2+1证明:设n1是度为1结点数,n是总的结点数.那么n=210nnn设B是全部分枝数.则n~B?n=B+1.因为所有分枝都来自度为1或2的结点,所以B~n1&n2?B=n1+2n2.123n0=n2+1n个结点的完全二叉树的深度为k为：16二叉树的存储结构1.顺序存储结构第4章树§4.3二叉树完全二叉树最适合这种存储结构。n个结点的完全二叉树的结点父子关系，简单地由序列号决定：(b)完全二叉树(a)相应的顺序存储结构1、非根结点（序号i1）的父结点的序号是i/2;2、结点（序号为i）的左孩子结点的序号是2i，（若2i=n，否则没有左孩子）;3、结点（序号为i）的右孩子结点的序号是2i+1，（若2i+1=n，否则没有右孩子）。数据ABOCSMQWK编号12345678917ABOMC137654982ABOM13111012C数据ABO∧∧M∧∧∧∧∧∧C编号12345678910111213(a)一般二叉树(b)对应(a)的完全二叉树第4章树§4.3二叉树造成空间严重浪费！一般二叉树采用这种结构将造成空间浪费182.二叉树的链式存储第4章树§4.3二叉树typedefstructTreeNode*BinTree;typedefBinTreePosition;structTreeNode{ElementTypeData;BinTreeLeft;BinTreeRight;}；LeftDataRightdataLeftRightHEDFGIACBFCBDGIHEA19【定义】“二叉树(BinaryTrees)”抽象数据类型定义。,类型名称：二叉树（BinTree）数据对象集：一个有穷的结点集合。这个集合可以为空，若不为空，则它是由根结点和其左、右二叉子树组成。操作集：对于所有BT,BT1,BT2BinTree,ItemElementType，重要的操作有：1、BooleanIsEmpty(BinTreeBT)：若BT为空返回TRUE;否则返回FALSE；2、voidTr