树在数据结构中的简单应用.doc

题目：树在数据结构中的简单应用树在数据结构中的简单应用Simple Application of Tree In Data-structure II 毕业论文(设计)摘 要树形结构是一类重要的非线性结构.本文研究了树形数据结构的基础知识，包括相关定义、操作以及树在数据结构中的简单应用问题.主要运用图示以及相关的算法来研究树以及树在数据结构中的若干应用问题，如在编码问题中的应用、在查找算法中的应用等.关键词:树;二叉树;数据结构;树的应用ABSTRACTThe construction of tree form is an important construction of not line. In this paper, we research the base knowledge of tree including some correlation definition, operation and the simple application of tree in data structure. We research tree and some application of tree in data structure by diagram and some correlative arithmetic, for example, in coding, in arithmetic and so on. Key words : Tree, Tree of two fork; Data construction; The trees application 毕业论文(设计)目 录摘要ABSTRACT0 引言11 树的概述1 1.1树的定义及相关术语1 1.2二叉树的定义及数学性质4 1.3二叉树的表示6 1.4树的操作92 树在最短路径问题中的应用11 2.1生成树和最小（代价）生成树113 树在编码中的应用14 3.1哈夫曼编码问题14 3.2哈夫曼树的定义14 3.3哈夫曼树的构造15 3.4哈夫曼树的应用164 树在查找算法中的应用17 4.1二叉排序树的概述17 4.2二叉排序树的查找18结束语 21参考文献22 毕业论文(设计)共22页第23页引言在计算机应用的各个领域中都会遇到各种各样的数据结构,而树在数据结构中又是一个相当重要的非线性结构,广泛应用于计算机领域中.在现实生活中存在很多可以用树形结构描述的实际问题，比如家谱等.下面先给出关于树的一些基本知识.1 树的概述树是一类重要的非线性结构,非常类似与自然界中的树.在计算机领域有广泛的应用.本章重点研究树的相关基础知识.1.1 树的定义及树的相关术语在本节中我们首先定义树以及树的一些相关术语.1.1.1 树的定义树是由一个集合以及在该集合上定义的一种关系构成的.集合中的元素称为树的结点，所定义的关系称为父子关系.父子关系在树的结点之间建立了一个层次结构.在这种层次结构中有一个结点具有特殊的地位,这个结点称为该树的根结点,或简称为树根.我们可以形式地给出树的递归定义如下:） 单个结点是一棵树,树根就是该结点本身. ） 设是树,它们的根结点分别为,用一个新结点作为的父亲,则得到一棵新树,结点就是新树的根.我们称为一组兄弟结点,它们都是结点的儿子结点.我们还称为结点的子树. 空集合也是树,称为空树.空树中没有结点.一棵典型的树如图1-1所示图1-1 树的层次结构由图1-1可以看出树的形状就像一棵现实中的树,只不过是倒过来的.1.1.2 树的相关术语结点的度1：一个结点的儿子结点的个数称为该结点的度.一棵树的度是指该树中结点的最大度数. 叶结点：树中度为零的结点称为叶结点或终端结点. 分枝结点：树中度不为零的结点称为分枝结点或非终端结点.内部结点1：除根结点外的分枝结点统称为内部结点.例如在图1-1中,结点,和的度分别为3,2,0.其中为根结点,为内部结点,为叶结点,树的度为3. 路径：如果存在树中的一个结点序列,使得结点是结点的父结点,则称该结点序列是树中从结点到结点的一条路径或道路.我们称这条路径的长度为,它是该路径所经过的边(即连接两个结点的线段)的数目.树中任一结点有一条到其自身的长度为零的路径.例如,在图1-1中,结点到结点有一条路径,它的长度为3. 祖先：如果在树中存在一条从结点到结点的路径,则称结点是结点的先,也称结点是结点的子孙或后裔.例如在图1-1中,结点的祖先有和自己,而它的子孙包括它自己和.注意,任一结点既是它自己的祖先也是它自己的子孙. 真祖先、真子孙：我们将树中一个结点的非自身祖先和子孙分别称为该结点的真祖先和真子孙.在一棵树中,树根是唯一没有真祖先的结点.叶结点是那些没有真子孙的结点.子树是树中某一结点及其所有真子孙组成的一棵树. 结点高度1：树中一个结点的高度是指从该结点到作为它的子孙的各叶结点的最长路径的长度.树的高度是指根结点的高度.例如图1-1中的结点,和的高度分别2,0和1,而树的高度与结点的高度相同为3. 结点的深度或层数：从树根到任一结点有唯一的一条路径,我们称这条路径的长度为结点的深度或层数.根结点的深度为0,其余结点的深度为其父结点的深度加1.深度相同的结点属于同一层.例如,在图1-1中,结点的深度为0；结点和的深度为1；结点的深度为2；结点和的深度为3.在树的第二层的结点有和,树的第0层只有一个根结点. 有序树、左儿子、右兄弟：树的定义在某些结点之间确定了父子关系,我们又将这种关系延拓为祖先子孙关系.但是树中的许多结点之间仍然没有这种关系.例如兄弟结点之间就没有祖先子孙关系.如果我们在树的每一组兄弟结点之间定义一个从左到右的次序,则得到一棵有序树；否则称为无序树.设结点的所有儿子按其从左到右的次序排列为,则我们称是的最左儿子,或简称左儿子,并称是的右邻兄弟,或简称右兄弟.图1-2中的两棵树作为无序树是相同的,但作为有序树是不同的,因为结点的两个儿子在两棵树中的左右次序是不同的.后面,我们只关心有序树,因为无序树总可能转化为有序树加以研究.图1-2 两棵不同的有序树我们还可以将兄弟结点之间的左右次序关系加以延拓：如果与是兄弟,并且在的左边,则认为的任一子孙都在的任一子孙的左边. 森林：森林是棵互不相交的树的集合.如果我们删去一棵树的树根,留下的子树就构成了一个森林.当我们删去的是一棵有序树的树根时,留下的子树也是有序的,这些树组成一个树表.在这种情况下,称这些树组成的森林为有序森林或果园. 1.2 二叉树的定义及数学性质在本节中我们将主要学习二叉树的定义及其数学性质.1.2.1 二叉树的定义二叉树是一类非常重要的树形结构,它可以递归地定义2如下：二叉树T是有限个结点的集合,它或者是空集,或者由一个根结点以及分别称为左子树和右子树的两棵互不相交的二叉树和组成.若用和分别表示和的结点数,则有.和有时分别称为的第一和第二子树.因此,二叉树的根可以有空的左子树或空的右子树,或者左、右子树均为空.二叉树有5种基本形态,如图1-3所示.图1-3 二叉树的5种基本形态(其中表示空)在二叉树中,每个结点至多有两个儿子,并且有左、右之分.因此任一结点的儿子不外4种情况：没有儿子；只有一个左儿子；只有一个右儿子；有一个左儿子并且有一个右儿子.二叉树与度数不超过2的树不同,与度数不超过2的有序树也不同.在有序树中,虽然一个结点的儿子之间是有左右次序的,但若该结点只有一个儿子时,就无须区分其左右次序.而在二叉树中,即使是一个儿子也有左右之分.例如图1-4中和是两棵不同的二叉树.虽然它们与图1-5中的普通树(作为无序树或有序树)很相似,但它们却不能等同于这棵普通的树.若将这3棵树均看作是有序树,则它们就是相同的了.图1-4 两棵不同的二叉树图1-5 一棵普通的树由此可见,尽管二叉树与树有许多相似之处,但二叉树不是树的特殊情形.1.2.2二叉树的数学性质二叉树具有以下的重要性质2：） 高度为的二叉树至少有个结点； ） 高度不超过的二叉树至多有个结点； ） 含有个结点的二叉树的高度至多为； ） 含有个结点的二叉树的高度至少为,因此其高度为. 具有个结点的不同形态的二叉树的数目在一些涉及二叉树的平均情况复杂性分析中是很有用的.设是含有个结点的不同二叉树的数目.由于二叉树是递归地定义的,所以我们很自然地得到关于的下面的递归方程3：即一棵具有个结点的二叉树可以看成是由一个根结点、一棵具有个结点的左子树和一棵具有个结点的右子树所组成.因此,当时, .于是,含有3个结点的不同的二叉树有5棵,如图1-6所示.图1-6 含有3个结点的不同二叉树1.3 二叉树的表示我们已经看到,虽然二叉树与树很相似,但它却不是树的特殊情形.在许多情况下,使用二叉树具有结构简单,操作方便的优点.另外我们也看到,在树的左儿子右兄弟表示法中,实际上已将一棵一般的树转化为一棵二叉树.在更一般的情形,我们还可以将果园或森林转化为一棵等价的二叉树.下面我们来讨论二叉树的表示方法.1.3.1 左儿子右兄弟表示法树的左儿子右兄弟表示法又称为二叉树表示法或二叉链表表示法.每个结点除了data域外,还含有两个域,分别指向该结点的最左儿子和右邻兄弟.这种表示法常用二叉链表实现,因此又称为二叉链表表示法.但是实际应用中常用游标(静态链表)来代替链表.指针及游标实现及算法见数据结构-用C语言描述一书.用树的左儿子右兄弟表示法可以直接实现树的大部分操作,只有在对树结点作Parent操作时需遍历树.如果要反复执行Parent操作,可在结点记录中再开辟一个指向父结点的指针域,也可以利用最右儿子单元中的Right_Sibling作为指向父结点的指针(否则这里总是空指针).当执行Parent()时,可以先通过Right_Sibling逐步找出结点的最右兄弟,再通过最右兄弟的Right_Sibling(父亲指针)找到父结点.这个结点就是结点v的父亲.在这样的表示法下,求一个结点的父亲所需要的时间正比于该结点右边的兄弟个数.不过,这时每个记录中需要多用一位(bit)空间,用以标明该记录中的right_sibling是指向右邻兄弟还是指向父亲.考虑到对于现在的计算机,内存已经不是很重要的限制因素了.我们下面就采取增加一个parent域的方案,以改进左儿子右兄弟表示法中Parent操作的效率.因此重新定义树的类型如下：若用指针实现,其类型定义为：Type4TPosition=NodeType;NodeType=recordLabel:LabelType;Parent,Leftmost_Child,Right_Sibling:TPosition; 增加一个Parent域end;TreeType=TPosition;varTree:TreeType; 若用游标实现,其类型定义为:TypeTPosition=integer;NodeType=recordLabel:LabelType;Parent,Leftmost_Child,Right_Sibling:TPosition; 增加一个Parent域end;CellspaceType=array 1.MaxNodeCount of NodeType;TreeType=TPosition;varCellspace:CellspaceType;Tree:TreeType; 1. 3. 2 果园或森林的二叉树表示从树的左儿子右兄弟表示法和二叉树的链式表示法可知,一般树和二叉树都可以用二叉链表作为其存储结构.因此,以二叉链表为媒介可以将一棵一般树转换为一棵二叉树.例如,图1-7(a)中的树可转化为图1-7(b)中的二叉树,它们具有相同的二叉链表表示.(a)(b)图1-7 将一棵树转化为二叉树由树的左儿子右兄弟表示法可知,与其对应的二叉树根结点的右子树必为空树.因此,如果我们将一个果园中的所有树转换为二叉树,并将第棵树当作第棵树的根结点的右子树,则可将一个果园转换为一棵二叉树.如图1-8(a)中的果园,经上述转换,变成为图1-8(c)中的二叉树.图1-8 果园的二叉树的表示对于一个森林,可先确定森林中各树的一个排列顺序,将其变成一个果园,然后再用相应的二叉树来表示.用树的前序和中序遍历可定义果园的前序和中序遍历如下：） 若果园非空,则对果园的前序遍历是依序对果园中第棵树进行前序遍历的结果. ） 若果园非空,则对果园的中序遍历是依序对果园中第棵树进行中序遍历的结果. 在前序和中序遍历的意义下,果园和与之相应的二叉树是等价的.1.4 树的操作了解了树的的相关基础知识之后,下面我们来研究有关树的操作.为了研究的方便,用图表的形式对树和二叉树做一对照.1.4.1 ADT树的操作ADT：指定数据存储类型以及支持数据的操作.主要功能是简单而明确的描述数据结构的操作.树的最重要的作用之一是用以实现各种各样的抽象数据类型.与表的情形相同,定义在树上的操作也是多种多样的.在这里我们只考虑作为抽象数据类型的树的几种典型操作.以下的表示空结点,在树的不同实现方法中有不同的定义.表 ADT树的基本运算 运算 含义Parent这是一个求父结点的函数,函数值为树中结点的父亲.当是根结点时,函数值为,表示结点没有父结点.Leftmost_Child这是一个求最左儿子结点的函数.函数值为树中结点的最左儿子.当是叶结点时,函数值为,表示结点没有儿子.Right_Sibling这是一个求右邻兄弟的函数,函数值为树中结点的右邻兄弟.当没有右邻兄弟时,函数值为.Create这是一族建树过程.对于每一个非负整数,该函数生成一棵新树,的根结点是标号为的新结点,并令有个儿子,这些儿子从左到右分别为树的根.当时,既是树根,又是树叶.Label这时一个求标号的函数,函数值就是结点的标号.Root这是一个求树根的函数,函数值为树的根结点.当是空树时,函数值为.MakeNull这是一个过程,它使成为一棵空树.1.4.2 ADT二叉树的操作(见表2)表 二叉树的常用操作 运算 含义Parent这是一个求父结点的函数,函数值为树中结点的父亲.当是根结点时,函数值为,表示结点没有父结点.Left_Child这是一个求左儿子结点的函数.函数值为树中结点的左儿子.当结点没有左儿子时,函数值为.Right_Child这是一个求右儿子结点的函数.函数值为树中结点的右儿子.当结点没有右儿子时,函数值为.Create这是一个建树过程.该函数生成一棵新的二叉树,的根结点的标号为x, 的左右儿子分别为Left和Right.Label这时一个求标号的函数,函数值就是结点的标号.Root这是一个求树根的函数,函数值为树的根结点.当是空树时,函数值为.MakeNull这是一个过程,它使成为一棵空树.2 树在最短路径问题中的应用交通网络中常提出这样的问题,两地之间是否有路相通?在有多条通路的情况下,哪一条最短?交通网络中可以用带权图表示,图中结点可以表示城镇,边表示城镇之间的通路,边上权值表示城镇间的距离,交通费用或中途所需时间等,以上问题就是带权图中的最短路径问题.树在这里有非常重要的应用.21 生成树和最小（代价）生成树生成树和最小生成树就是解决最短路径最小代价问题的主要手段.2.1.1最短路径问题 生成树和最小生成树有许多重要的应用.令图的顶点表示城市,边表示连接两个城市之间的通讯线路. 个城市之间最多可设立的线路有条,把个城市连接起来至要有条线路,则图的生成树表示了建立通讯网络的可行方案.如果给图中的边都赋予权,而这些权可表示两个城市之间通讯线路的长度或建造代价,那么,如何选择条线路,使得建立的通讯网络其线路的总长度最短或总最小呢?这就是最小生成树要解决的问题.【例】网络表示个城市之间的通信线路网（其中顶点表示城市,边表示两个城市之间的通信线路,边上的权值表示线路的长度或造价）.可通过求该网络的最小生成树达到求解通信线路最短或总代价最小的方案.2.1.2 生成树和最小生成树的相关概念和MST的性质:连通图的一个子图如果是一棵包含的所有顶点的树,则该子图称为的生成树.图的生成树不是唯一的,从不同的顶点出发进行遍历,可以得到不同的生成树.对于连通网络,边是带权的,因而的生成书的各边也是带权的.我们把生成树各边的权值总和称为生成树的权,并把权值最小的生成树称为的最小生成树（Minimum Spanning Tree）.2.1.3 构造最小生成树的常用方法普里姆（Prim）算法5 基本思想：设是连通网,顶点集,是欲构造的最小生成树.任选中一顶点（不妨为）.初始化,.重复下列操作：在所有中, 的边中,选择一条权值最小的边并入,同时将并入,直到为止,这时产生的中具有条边,则上述过程求得的是的一棵最小生成树.相关算法（用C语言描述）见数据结构-用C语言描述一书. 普里姆算法的时间复杂度为,与图中边数无关,该算法适合于稠密图. 图2-1 用Prim算法构造最小生成树的过程克鲁斯卡尔（Kruskal）算法5 基本思想：设是无向连通网的最小生成树,是其边集,则令最小生成树的初始状态为个顶点而无边的非连通图,即为空集,图中每个顶点自成一个连通分量.在中选择权值最小的边,若该边依附的顶点落在中不同的连通分量上,则将此边加入到中,否则舍去此边而选择下一条权值最小的边.依次类推,直至中所有顶点都在同一连通分量上为止（此时已选中条边）. 克鲁斯卡尔算法的时间复杂度为,时间主要取决于边数,较适合于稀疏图. (a) (b) (c) (d) (e)图2-2 用kruskal算法构造最小生成树的过程3 树在编码中的应用上一章我们研究了树在最短路径问题中的应用,下面我们将研究树在编码中的应用.3.1哈夫曼编码问题在电报通讯中,电文是以二进制的0,1序列传送的.在发送段,需要将电文中的字符转换成二进制的0,1序列(编码),在接受端则要将收到的0,1串转化为对应的字符序列(译码).最简单的编码方法是等长编码,例如,若电文是英文,则电文的字符串仅由26个英文字母组成,需要编码的字符集合，采用等长编码时,每个字符用5位二进制位串表示即可.在接收端,只要按5位分割进行译码就可得到对应的文字.众所周知,字符集中的字符被使用的频率是非均匀的,例如,英文中和的只用较只和要频繁得多.因此,若让使用频率高的字符的编码尽可能短,则可使传送的电文总长缩短.然而采用这种不等长编码可能使译码长生多意性的电文,例如,假设用00表示,用01表示,用0001表示,则当接收到信息串0001时,无法确定原电文是还是,产生该问题的原因是的编码与的编码的开始部分(前缀)相同.因此,若对某字符集进行不等长编码,则要求字符集中任何一字符的编码都不是其他字符的编码的前缀,这种编码叫做前缀(编)码.显然,等长编码是前缀码.什么样的前缀码才能使得电文总长最短呢?这就是哈夫曼树在编码中的应用(哈夫曼编码).32 哈夫曼树的定义要研究哈夫曼编码,首先得弄清楚哈夫曼树的相关概念.321 哈夫曼树的相关概念在一棵树中,从一个结点往下可以达到的孩子或子孙结点之间的通路,称为路径.通路中分支的数目称为路径长度.若规定根结点的层数为1,则从根结点到第层结点的路径长度为.结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权.结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积. 树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为.322 哈夫曼树的定义给定个权值作为个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree).33 哈夫曼树的构造假设有个权值,则构造出的哈夫曼树有个叶子结点. 个权值分别设为 ,则哈夫曼树的构造规则6为：） 将看成是有棵树的森林(每棵树仅有一个结点)；） 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和；） 从森林中删除选取的两棵树,并将新树加入森林；） 重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为我们所求得的哈夫曼树. 下面给出哈夫曼树的构造过程,假设给定的叶子结点的权分别为1,5,7,3,则构造哈夫曼树过程如图3-1所示. 从图3-1可知, 个权值构造哈夫曼树需次合并,每次合并,森林中的树数目减1,最后森林中只剩下一棵树,即为我们求得的哈夫曼树. （a）初始森林 （b）一次合并后的森林 （c）二次合并后的森林 （d）三次合并后的森林 图3-1 哈夫曼树的构造过程34 哈夫曼树的应用弄清了哈夫曼树的相关概念及哈夫曼树的构造过程,下面我们就来研究它的应用.341 哈夫曼编码通信中,可以采用0,1的不同排列来表示不同的字符,称为二进制编码.而哈夫曼树在数据编码中的应用,是数据的最小冗余编码问题,它是数据压缩学的基础.若每个字符出现的频率相同,则可以采用等长的二进制编码,若频率不同,则可以采用不等长的二进制编码,频率较大的采用位数较少的编码,频率较小的字符采用位数较多的编码,这样可以使字符的整体编码长度最小,这就是最小冗余编码的问题. 而哈夫曼编码7就是一种不等长的二进制编码,且哈夫曼树是一种最优二叉树,它的编码也是一种最优编码,在哈夫曼树中,规定往左编码为0,往右编码为1,则得到叶子结点编码为从根结点到叶子结点中所有路径中0和1的顺序排列.例如,给定权1,5,7,3,得到的哈夫曼树及编码见图3-2 (假定权值就代表该字符名字). (a) 哈夫曼树 (b) 哈夫曼树编码 图3-2 构造哈夫曼树及哈夫曼编码342 哈夫曼译码在通信中,若将字符用哈夫曼编码形式发送出去,对方接收到编码后,将编码还原成字符的过程,称为哈夫曼译码.4 树在查找算法中的应用当用线性表作为表的组织形式时,可以有三种查找法.其中以二分查找效率最高.但由于二分查找要求表中结点按关键字有序,且不能用链表作存储结构,因此,当表的插入或删除操作频繁时,为维护表的有序性,势必要移动表中很多结点.这种由移动结点引起的额外时间开销,就会抵消二分查找的优点.也就是说,二分查找只适用于静态查找表.若要对动态查找表进行高效率的查找,可采用下面介绍的几种特殊的二叉树或树作为表的组织形式.不妨将它们统称为树表.下面将分别讨论在这些树表上进行查找和修改操作的方法.41 二叉排序树概述(1) 二叉排序树的定义：二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree).其定义为：二叉排序树或者是空树,或者是满足如下性质的二叉树： 若它的左子树非空,则左子树上所有结点的值均小于根结点的值； 若它的右子树非空,则右子树上所有结点的值均大于根结点的值； 左、右子树本身又各是一棵二叉排序树. 上述性质简称二叉排序树性质(BST性质),故二叉排序树实际上是满足性质的二叉树.(2) 二叉排序树的特点为8：由性质可得： 二叉排序树中任一结点,其左(右)子树中任一结点 (若存在)的关键字必小(大)于的关键字. 二叉排序树中,各结点关键字是惟一的.注意：实际应用中,不能保证被查找的数据集中各元素的关键字互不相同,所以可将二叉排序树定义中性质里的小于改为小于等于,或将性质里的大于改为大于等于,甚至可同时修改这两个性质. 按中序遍历该树所得到的中序序列是一个递增有序序列.【例】下图所示的两棵树均是二叉排序树,它们的中序序列均为有序序列：2,3,4,5,7,8 （a）高度为3 （b） 高度为5图5-1 二叉排序树示例42 二叉排序树的查找要搞清楚二叉排序树的查找首先得了解二叉排序树的存储结构,生成过程,这样才能更好的研究其查找过程.421 二叉排序树的存储结构见相关资料数据结构422 二叉排序树的生成二叉排序树的生成,是从空的二叉排序树开始,每输入一个结点数据,就调用一次插入算法将它插入到当前已生成的二叉排序树中.生成二叉排序树的算法9如下： BSTree CreateBST(void) /输入一个结点序列,建立一棵二叉排序树,将根结点指针返回 BSTree T=NULL； /初始时T为空树 KeyType key； scanf(d,&key)； /读人一个关键字 while(key) /假设key=0是输人结束标志 InsertBST(&T,key)； /将key插入二叉排序树T scanf(d,&key)；/读人下一关键字 return T； /返回建立的二叉排序树的根指针 /BSTree 由输入实例,根据生成二叉排序树算法生成二叉排序树的过程输入序列决定了二叉排序树的形态.二叉排序树的中序序列是一个有序序列.所以对于一个任意的关键字序列构造一棵二叉排序树,其实质是对此关键字序列进行排序,使其变为有序序列.排序树的名称也由此而来.通常将这种排序称为树排序(Tree Sort),可以证明这种排序的平均执行时间亦为.对相同的输入实例,树排序的执行时间约为堆排序的2至3倍.因此在一般情况下,构造二叉排序树的目的并非为了排序,而是用它来加速查找,这是因为在一个有序的集合上查找通常比在无序集合上查找更快.因此,人们又常常将二叉排序树称为二叉查找树. 423 二叉排序树上的查找(1) 查找递归算法 在二叉排序树上进行查找,和二分查找类似,也是一个逐步缩小查找范围的过程.递归的查找算法10： BSTNode *SearchBST(BSTree T,KeyType key) /在二叉排序树T上查找关键字为key的结点,成功时返回该结点位置,否则返回 NUll if(T=NULL|key=T-key) /递归的终结条件 return T； /T为空,查找失败；否则成功,返回找到的结点位置 if(keykey) return SearchBST(T-lchild,key)； else return SearchBST(T-rchild,key)；/继续在右子树中查找 /SearchBST(2) 算法分析在二叉排序树上进行查找时,若查找成功,则是从根结点出发走了一条从根到待查结点的路径.若查找不成功,则是从根结点出发走了一条从根到某个叶子的路径. 二叉排序树查找成功的平均查找长度 在等概率假设下,下面图5-2(a)中二叉排序树查找成功的平均查找长度为：在等概率假设下,图5-2(b)中所示的树在查找成功时的平均查找长度为：（a） (b) 图5-2 由同一组关键字构成的两棵形态不同的二叉排序树注意：与二分查找类似,和关键字比较的次数不超过树的深度. 在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关 二分查找法查找长度为的有序表,其判定树是惟一的.含有个结点的二叉排序树却不惟一.对于含有同样一组结点的表,由于结点插入的先后次序不同,所构成的二叉排序树的形态和深度也可能不同.【例】图5-2(a)所示的树,是按如下插入次序构成的：45,24,55,12,37,53,60,28,40,70图5-2(b)所示的树,是按如下插入次序构成的：12,24,28,37,40,45,53,55,60,70在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关： 在最坏情况下,二