三叉搜索树中的近邻搜索：求带示例的实现说明

三叉搜索树（Ternary Search Tree）的近邻搜索用于找出与目标字符串编辑距离不超过指定值d的所有字符串。以下是对提供的近邻搜索函数的详细解析及示例说明：

函数核心逻辑解析 #

先看完整函数代码：

void nearsearch(Tptr p, char *s, int d) 
{   if (!p || d < 0) return; 
    if (d > 0 || *s < p->splitchar) 
        nearsearch(p->lokid, s, d); 
    if (p->splitchar == 0) { 
       if ((int) strlen(s) <= d) 
          srcharr[srchtop++] = (char *) p->eqkid; 
    } else
       nearsearch(p->eqkid, *s ? s+1:s, 
          (*s == p->splitchar) ? d:d-1); 
    if (d > 0 || *s > p->splitchar) 
        nearsearch(p->hikid, s, d); 
}

参数说明 #

• p：当前遍历的三叉树节点指针
• s：目标搜索字符串
• d：允许的最大编辑距离（字符不匹配、缺失、插入的次数上限）
• srcharr：存储搜索结果的数组，srchtop是结果数组的当前索引

执行步骤拆解 #

1. 终止条件：若当前节点为空，或剩余允许的编辑距离d<0，直接返回，停止遍历。
2. 遍历左子树：当仍允许错误（d>0），或目标字符串当前字符小于节点分割符splitchar时，递归遍历左分支（lokid），d保持不变——左分支存储分割字符小于当前节点值的子树，只要还有错误次数可用，就需要检查左分支是否存在符合条件的字符串。
3. 处理当前节点与中间分支：
   • 若节点splitchar为0，说明是叶子节点，eqkid指向完整存储字符串。此时检查目标剩余字符串长度是否≤d：如果目标字符串已遍历完（剩余长度为0），或剩余长度未超过允许的错误次数，就将该字符串加入结果数组。
   • 若不是叶子节点，递归遍历中间分支（eqkid）：
     • 若目标字符串还有未处理字符，指针移到下一个字符（s+1）；若目标已遍历完，保持s不变。
     • 调整编辑距离：目标当前字符与节点splitchar匹配时，d不变；不匹配时，消耗一次错误次数，d减1。
4. 遍历右子树：当仍允许错误（d>0），或目标字符串当前字符大于节点splitchar时，递归遍历右分支（hikid），d保持不变，逻辑与左子树一致。

示例演示 #

假设三叉树中存储了apple、apply、apricot、banana，搜索目标字符串appl（允许编辑距离d=1）：

1. 从根节点（分割符a）开始，目标字符a匹配，递归中间分支，s变为ppl，d保持1。
2. 下一个节点分割符p，目标字符p匹配，递归中间分支，s变为pl，d保持1。
3. 再下一个节点分割符p，目标字符p匹配，递归中间分支，s变为l，d保持1。
4. 当前节点分割符l，目标字符l匹配，递归中间分支，s变为空，d保持1：
   • 中间分支指向apple的叶子节点，此时strlen(s)=0 ≤1，符合条件，apple被加入结果。
5. 回到分割符l的节点，因d=1>0，遍历右分支（分割符y的节点）：
   • 递归中间分支时，目标已遍历完，字符不匹配y，d减为0。
   • 中间分支指向apply的叶子节点，strlen(s)=0 ≤0，符合条件，apply被加入结果。

最终结果数组包含apple和apply，二者与appl的编辑距离均为1，符合要求。

内容的提问来源于stack exchange，提问作者Willy Adams