预计阅读本页时间:-
二叉搜索树(binary search tree)是一种结合了折半搜索策略的链接结构。树中的每一个节点都包含一
个项目和两个指向其他节点(称为子节点,child node)的指针。图17.12示意了二叉搜索树中的节点是如何链接的。这种构思是每一个节点都有两个子节点,左节点和右节点。其顺序按照如下规则确定:在左节点中的项目是父节点中项目的前序项,而在右节点中的项目是父节点中项目的后序项。这种关系存在于每一个有子节点的节点中。而且,所有能循其祖先回溯到左节点的项目都是该左节点的父节点项目的前序项,所有以右节点为祖先的项目都是该右节点的父节点项目的后序项。图17.12中的树按这种方式存储单词。很有趣的是,与植物学相反,树的顶部是根。树是一个分层的组织,这意味着数据是以等级或者说层次来组织的。一般地,每个等级都有其上和其下的等级。如果二叉搜索树是满的,那么每一层的节点数都两倍于其上层的节点数。
广告:个人专属 VPN,独立 IP,无限流量,多机房切换,还可以屏蔽广告和恶意软件,每月最低仅 5 美元
图17.12 一个存储单词的二叉搜索树
二叉搜索树中的每一个节点本身是其后代节点的根,此节点与其后代节点构成一个子树(subtree)。例如,在图17.12中,包含单词fate、carpet和llama的节点组成了整个树的左子树,而单词voyage是style-plenum-voyage子树的右子树。
假设您想在这样的一个树中查找一个项目(仍称为目标项)。如果此项目在根节点项目的前面,只须查找树的左半部分;如果目标项在根节点项目后面,则只须查找树的右半部分。因而,一次比较就排除了半个树。假设您查找左半边,那意味着将目标项与左子节点的项目进行比较。如果目标项在左子节点项目的前面,只须查找其后代的左半部分,依此类推。就像折半搜索一样,每次比较都排除一半可能的匹配项。
让我们用这种方法来看一看单词puppy是否在图17.12中。比较puppy和melon(根节点项目),发现puppy如果在树中的话,一定在树的右半部。因此,到右半部比较puppy和style。这次,发现puppy在此节点项目的前面,就要向下到其左节点。在那里找到plenum,它在puppy前面。现在需要向下到其右支,但树已经空了,所以3次比较就显示出puppy不在树中。
这样,二叉搜索树在链表结构中结合了折半搜索的效率。编程的代价是构造一棵树比创建一个链表更复杂。下面我们来创建一个二叉树,并最后建立一个ADT工程。
17.7.1 二叉树ADT
像前面那样,我们从定义二叉树的常规内容开始。该定义假设树中不包含相同的项目。很多操作与列表操作相同。不同之处在于数据的层次性安排。表17.4是有关此ADT的非正式的总结。
表17.4 二叉树类型总结
类 型 名 称: | 二叉搜索树 |
---|---|
类型属性: | 二叉树或者是一个空的节点集合(空树),或者是一个指定某一节点为根的节点集合 每个节点有两个作为其后代的树,称为左子树和右子树 每一个树本身又是一个二叉树,也包含它是个空树的可能性 二叉搜索树是有序的二叉树,它的每个节点包含一个项目,它的所有左子树的项目排在根项目的前面, 而根项目排在所有右子树项目的前面 |
类型操作: | 把树初始化为空树 确定树是否为空 确定树是否已满 确定树中项目的个数 向树中添加一个项目 从树中删除一个项目 在树中搜索一个项目 访问树中每一个项目 清空树 |
17.7.2 二叉搜索树的接口
理论上讲,可以用多种方法实现二叉搜索树,甚至可以通过操作索引来用数组实现。但实现二叉搜索树最直接的方法是用指针链接动态分配的节点,因此我们从如下的定义开始:
每个节点包含一个项目,一个指向左子节点的指针和一个指向右子节点的指针。可以将Tree定义成指向Node的指针类型,因为只需知道根节点的位置即可访问整个树。不过,使用带有一个指示树大小的成员的结构可以使跟踪树的大小更为简单。
我们要开发的示例程序是维护Nerfville宠物俱乐部的花名册。每一个项目由宠物的名字和种类组成。据此,我们可以建立一个如程序清单17.10所示的接口。树的大小被限制为10个节点,以使我们更容易测试当树已满时程序是否正确运行。如果需要,您可以把MAXITEMS设置为更大的值。
程序清单17.10 tree.h接口头文件
17.7.3 二叉树的实现
下面的任务是实现tree.h中描绘的伟大的函数。InitializeTree()、EmptyTree()、FullTree()和Treeltems()函数比较简单,与列表和队列抽象数据类型中的同类函数差不多。我们重点讨论其余的函数。
一、添加项目
在向树中添加一个项目时,应该首先检查树中是否还有空位给新节点。然后,由于二叉搜索树被定义成不含有相同的项目,所以要检查树中是否已经有该项目。如果这个新项目通过了前两步检查,就可以创建一个新的节点,将项目复制到节点中,并设置此节点的左右指针为NULL。这表示该节点无子节点。然后要更新Tree结构的size成员,以记录添加了一个新项目。接下来,要找出该把此节点放在树中的什么位置。如果树为空,就要将根节点指针指向该新节点。否则,在树中查找到放置该新节点的位置。AddItem()函数按照这条思路实现,并将其中一些工作交给几个尚未定义的函数:SeekItem()、MakeNode()和AddNode()。
Seekltem()、MakeNode()和AddNode()函数并不是Tree类型公用接口的一部分。它们是隐藏在tree.c文件中的静态函数。它们处理实现的细节,例如节点、指针和结构这些不属于公用接口的部分。
MakeNode()函数比较简单。它处理动态内存分配和节点的初始化。函数的参数是一个指向新项目的指针,函数返回值是一个指向新节点的指针。回忆一下,malloc()在无法完成请求的分配时返回空指针,MakeNode()函数只在内存分配成功时初始化新节点。以下是MakeNode()的代码:
AddNode()函数在二叉搜索树包中是很难的函数(其难度仅次于另一个函数)。它要判断新节点去向何方,并添加之。具体地,它需要比较新项目和根项目来决定新项目要添加到左子树还是右子树。如果项目是一个数字,可以用“<”和“>”进行比较。如果项目是一个字符串,可以用strcmp()进行比较。但本例中的项目是包含两个字符串的结构,所以必须定义执行比较的函数。后面定义的ToLeft()函数当新项目应在左子树时返回True,而ToRight()函数当新项目应在右子树时返回True。这两个函数相当于“<”和“>”。假设新项目要到左子树去。左子树可能是空的。在这种情况下,AddNode()函数只用把左子指针指向新节点。但如果左子树非空呢?则此函数就应比较新项目和左子节点的项目,以决定新项目应到此子节点的左子树,还是右子树中去。
这一过程继续进行,直到函数到达一个空的子树,在那一点添加新节点。递归是一种实现这种搜索的方法。即,在子节点而非根节点应用AddNode()函数。当左子树或右子树为空,即当root->left或root->right为NULL时函数的递归调用序列结束。切记root为指向当前子树顶部的指针,所以每次递归调用使它指向一个新的下一级子树(请参见第9章中关于递归的讨论)。
ToLeft()和ToRight()函数有赖于Item类型的特性。Nerfville宠物俱乐部的成员以名字的字母顺序排序。如果两个宠物重名,将其按种类排序。如果它们又是相同种类的,则这两个项目是相同的,这在基本二叉搜索树中是不允许的。回忆一下标准C库函数strcmp()的用法:如果第一个参数表示的字符串在第二个字符串之前则返回负数,如果两者相等则返回零,如果第一个字符串在第二个字符串之后则返回正数。ToRight()函数与之有相似的代码。用这两个函数进行比较,而不是直接在AddNode()中处理,会比较容易地适应新的需求。当需要不同形式的比较时,不必重写整个AddNode()函数,只须重写ToLeft()和ToRight()即可。
二、查找项目
有3个接口函数需要用到搜索树中特定项目的功能:AddItem()、InTree()和Deleteltem()。在实现中由Seekltem()函数提供这一服务。Deleteltem()函数还有另一个要求:需要知道被删除项目的父节点,以便子节点被删除时父节点指向该子节点的指针可以得到更新。因此,将Seekltem()设计成返回包含两个指针的结构,其中一个指针指向包含该项目的节点(如果没找到项目就为NULL),另一个指向父节点(如果该节点为根节点,也即没有父节点,就为NULL)。这个结构类型定义如下:
Seekltem()函数可以通过递归的方法实现。但是,为了向您介绍更多的编程技术,我们用while循环来控制树中从上到下的搜索。像AddNode() 一样,Seekltem()使用ToLeft()和ToRight()在树中导航。开始时Seekltem()设置look.child指针指向树的根节点,然后沿着目标项目应在的路径重置look.child到后续的子树。同时,look.parent指向它的父节点。如果未找到匹配项目,look.child为NULL。如果匹配项目在根节点,look.parent为NULL,因为根节点无父节点。以下是Seekltem()的代码
:
注意,由于Seekltem()函数返回一个结构,所以它能和结构成员运算符一起使用。例如,AddItem()函数中使用了如下代码:
有了SeekItem()之后,编写InTree()公用接口函数是很简单的:
三、删除项目
删除一个项目是最困难的任务,因为要将剩下的子树重新连接起来,以形成一个合法的树。在尝试编程完成这个任务之前,我们最好考虑清楚需要做什么。
图17.13示意了一种最简单的情况。其中要删除的节点没有子节点,这种节点被称为叶节点(leaf)。在这种情况下我们要做的就是将父节点的相应指针置为NULL,并用free()函数释放被删节点占用的内存。
接下来要删除有一个子节点的节点就复杂些了。删除该节点使其子节点子树与树的其他部分分离开了。为修复这种情况,需要把子节点子树的地址存储在先前被删节点的地址在父节点中占据的位置中(如图17.14所示)。
图17.13 删除一个叶节点
图17.14 删除有一个子节点的节点
最后,要删除有两个子树的节点。其中一个子树,例如左子树,可依附在被删节点先前依附的位置。但剩下的子树要去哪里呢?紧记树的基本设计:每一个在左子树中的项目都是父节点项目的前序项,而每一个右子树中的项目都是父节点项目的后序项。这意味着所有右子树中的项目都是所有左子树中项目的后序项。而且,因为右子树曾经是以被删项目为根的子树的一部分,所以所有右子树中的项目都是被删节点的父节点的前项。想象一下如何在树中自上而下寻找右子树的头应在的位置。它应在父节点的前面,所以要沿父节点的左支向下找。但是,它又在左子树所有项目的后面,这样就要查看左子树的右支是否有新节点的空位。如果没有,就要沿着左子树的右支向下找直到找到一个空位。图17.15说明了这种方法。
图17.15 删除有两个子节点的节点
1.删除节点
现在可以开始设计需要的函数了。可以将工作分成两个任务:第一个任务是将一个特定的项目与待删节点联系起来,第二个任务是实际删除此节点。有一点需要注意的是,在所有的情况下都必须修改父节点的指针,这导致两个重要的结论:
● 程序要能表示待删节点的父节点。
● 要修改指针,代码必须将该指针的地址传递给执行删除任务的函数。
稍后我们会回到第一点上来讨论。同时,要修改的指针本身是Node*类型的,也即指向Node的指针类型。因为函数参数是指针的地址,所以参数是Node**类型的,即指向Node的指针的指针。假设您有可用的合适地址,可以将删除函数写成如下形式:
这个函数明确地处理三种情况:无左子节点的节点、无右子节点的节点和有两个子节点的节点。无子节点的节点可作为无左子节点的节点的特例。因为如果该节点无左子节点,程序就将右子节点的地址赋给父指针;但如果此时该节点也没有右子节点,则其指针就为NULL,这恰好是无子节点情况的值。
注意到代码用了一个临时指针来跟踪被删除节点的地址。因为当父指针(*ptr)被重置后,程序会丢失将要被删除节点的地址,但free()函数还需要此信息。所以程序将*ptr的初值存储在temp中,然后用temp来释放被删除节点占用的内存。
处理有两个子节点情况的代码首先在一个for循环中用temp指针向下查找左子树的右半边以找到一个空位。当找到一个空位的时候,将右子树依附在那儿。然后再用temp保存被删除节点的地址。接下来,将左子树依附到父节点上,然后释放temp指向的节点的内存。
注意,因为ptr是Node**类型的,所以*ptr是Node*类型的,即和temp的类型相同。
2.删除项目
剩下的问题就是将一个节点与一个特定的项目联系起来。这可以用Seekltem()函数来完成。回忆一下,它返回一个结构,此结构包含一个指向父节点的指针和一个指向包含项目的节点的指针。这样就可以通过使用父节点指针获得相应地址传递给DeleteNode()函数。DeleteItem()函数遵循了这一思路,如下所示:
首先把SeekItem()函数的返回值赋给look结构变量。如果look.child等于NULL,表明本次查找失败,DeleteItem()函数退出,并返回false。如果找到该Item,函数处理三种情况。首先,look.parent的值为NULL意味着该项目在根节点中。在这种情况下,不需要更新父节点,而是需要更新Tree结构中的根指针。因此,函数将该指针的地址传递给DeleteNode()函数。否则,程序判断待删节点是其父节点的左子节点还是右子节点,然后传递适当指针的地址。
注意公用接口函数DeleteItem()中处理的是面向最终用户的对象(项目和树),而隐藏的DeleteNode()函数则完成与指针有关的实质性任务。
四、遍历树
遍历树要比遍历链表复杂,因为每个节点有两个分支。这种分支特性使得分而制之的递归方法(第9章)成为处理此问题的自然选择。在每一个节点,函数要做下列工作:
● 处理节点中的项目。
● 处理左子树(递归调用)。
● 处理右子树(递归调用)。
可以将此过程分给两个函数完成:Traverse()和InOrder()。注意InOrder()函数先处理左子树,然后处理项目,最后处理右子树。这种遍历树的顺序是按字母排序的结果。如果您有时间,可以试试用不同的顺序,比如项目一左子树一右子树和左子树一右子树一项目看会发生什么。
五、清空树
清空树与遍历树基本上是一样的过程,即代码需要访问每个节点并用free()函数释放之。还需要重置Tree结构的成员以说明是空Tree。DeleteAll()函数负责处理Tree结构,并将释放内存的任务分配给DeleteAllNodes()。后者和InOrder()函数构造相同。它保存了指针值root–>right,以使它在根节点被释放后仍然可用。下面是这两个函数的代码:
六、完整的包
程序清单17.11给出完整的tree.c代码。tree.h和tree.c共同组成了树程序包。
程序清单17.11 tree.c实现文件
17.7.4 试用树
现在已经有了接口和函数实现,我们来使用它们。程序清单17.12中的程序使用菜单来选择向俱乐部成员花名册添加宠物、显示成员列表、报告成员数、核查成员及退出。函数main()很简要,它集中于实质性问题的概括。支持函数完成了大部分工作。
程序清单17.12 petclub.c程序
程序将所有字母转换为大写,所以SNUFFY、Snuffy和snuffy被看作相同的名字。下面是一个运行示例:
图17.16 不平衡的二叉搜索树
17.7.5 树的思想
二叉搜索树有些缺点。例如,二叉搜索树只在满员(或者称为平衡)时效率最高。假设您要存储随意输入的单词。树看上去就可能比较枝繁叶茂,如图17.12所示。现在假设您按字母顺序输入数据,则每一个新的节点将被添加到右边,树将如图17.16所示。图17.12中的树被称为平衡的(balanced),而图17.16中的树则是不平衡的(unbalanced)。搜索这样的树并不比顺序搜索链表来得更快。
避免串状树的方法之一是在创建树时多加注意。如果一棵树或者子树开始在一边或另一边变得不平衡,需要重新排列节点使之恢复平衡。与之类似,您可能需要在删除操作之后重新排列树。俄国数学家Adel‘son-Vel’skii和Landis发明了一种完成此操作的算法,用他们的方法创建的树称为AVL树。由于需要额外的重构工作,所以创建一个平衡的树花费更多的时间,但这样的树可以保证最高或近乎最高的搜索效率。
您可能需要一个允许包含相同项目的二叉搜索树。例如您要分析一些文本,跟踪每个单词在文本中出现的次数。一种方法是将Item定义成包含一个单词和一个数值的结构。第一次碰到一个单词的时候,将其添加到树中,将其数值置为1。下一次碰到同样的单词,程序找到包含此单词的节点,并递增其中的数值。修改基本二叉搜索树使其具有这一性质并不需要很多的工作。
另一种可能的变化,考虑Nerfville宠物俱乐部实例程序。该例子以名字和种类来排序,所以能在一个节点包含Sam和cat,另一个节点包含Sam和dog,第三个节点包含Sam和goat。但您不能有两只猫叫Sam。解决这个问题的一种方法是只以名字来排序。但只做这种变化是不够的,它将只允许一个Sam,不管是什么种类的;还需要将Item定义成一个结构列表来代替单一的结构。Sally第一次出现时,程序将创建一个新的节点,并创建一个新的列表,然后将Sally和它的种类添加到列表中。下一次Sally出现时,程序将定位到同一个节点,并把新的数据添加到列表中。