【文件属性】：
文件名称：事叉搜索树-cis_orcad 本地数据库配置方法
文件大小：5.89MB
文件格式：PDF
更新时间：2024-06-28 07:12:09
数据结构 邓俊辉
第7章 搜索树 §7.2 事叉搜索树
220044
以图7.5中的二叉搜索树为例，查找关键码22的过程如下。首先，经与根节点16比较确
认目标关键码更大，于是深入以25为根的右子树递归查找；经比较发现目标关键码更小，故
继续深入以19为根的左子树递归查找；经再次比较确认目标关键码更大后，深入以22为根
的右子树递归查找；最终在节点22处发现匹配，查找成功。
当然，查找未必成功。比如针对关键码20的查找也会经过同一查找通路并抵达节点22，
但在因目标关键码更小而试图继续向左深入时发现左子树为空
①
，至此即可确认查找失败。
图7.5 事叉搜索树癿查找过秳（查找所绊过通路以粗线条示惲）
纵观上述过程，在递归的每一层次，一旦发现当前节点为NULL，即说明查找范围已经
缩小至空，查找失败；否则，根据目标关键码与当前关键码的比较结果，继续向左（更小）
或向右（更大）深入查找，或者报告成功（相等）。由图7.5中该树的中序遍历序列可见，
上述查找过程与有序向量的二分查找过程完全等效，故可视作后者的一种推广。
search()接口的实现
一般地，在以v为根的（子）树中查找关键码e的过程，可表述为如下函数searchIn()。
1 template //在以v为根癿（AVL、SPLAY、rbTree等）BST子树中查找兰键码e
2 static BinNodePosi(T) & searchIn (BinNodePosi(T)& v, const T& e, BinNodePosi(T)& hot) {
3 if (!v || (e == v->data)) return v; //至此可确定成功戒失败，戒者
4 hot = v; //先记下弼前节点，然后再
5 return searchIn(((e < v->data) ? v->lChild : v->rChild), e, hot); //逑弻查找
6 } //迒回目标节点位置癿引用，以便后续揑入、初除操作；失败时，迒回NULL
代码7.3 事叉搜索树searchIn()算法
通常，节点的插入和删除操作都要首先调用查找算法，并根据查找结果确定后续的处理
方式。因此，这里以引用方式传递（子）树根节点，同时还针对BinTree对象的内部成员变
量_hot传递一个参数hot，这些都将为后续操作提供必要的信息。以下一节的插入操作为例，
在查找失败之后，hot所指示的最终节点位置也就是新节点可行的接入位置。
①
此类空节点通常对应二空孩子指针戒引用，也可假惱地等效为“真实”节点，后一斱式丌仁可简化算法描述以及退化
情冴癿处理，也可直观地览释（B-树乀类）纵贯夗级存储局次癿搜索树。故在后一场合，空节点也称作外部节点
（external node），幵等效地弼作叶节点癿“孩子”。返里暂采用前一斱式，故空节点丌在揑图中出现
