查找存储在二叉搜索树中的单词的所有前缀

Question

我有一个存储字符串的二叉搜索树。字符串按字典顺序进行比较（使用 c 中的 strcmp）。

给定一些输入字符串，我想检索存储在 BST 中的该字符串的所有前缀的列表。例如，如果我的 BST 包含“a”、“ab”和“abc”，则在给定输入字符串“abcd”的情况下，此类搜索应返回这三个字符串的列表（详细信息：如果 BST 包含字符串本身，它被视为前缀）。

天真的方法是测试 BST 是否一一包含字符串的每个前缀（对于“hello”，搜索“h”，“he”，“hel”，...），但我想一种更有效的方法，可以避免多次遍历同一节点。

你会怎么做？我已经思考这个问题有一段时间了，但似乎永远无法弄清楚。

我注意到，如果在一个节点上找到一个前缀，那么该节点左侧的所有节点可能只包含较短的前缀，而右侧的所有节点只能包含较长的前缀。然而，我不太知道这有什么帮助。

我的 BST 实现很简单：

typedef struct Node_t
{
    Node* left, *right; // NULL if no node to either side
    const char* key; // Every node has an associated key
} Node;

typedef struct BST_t
{
    Node* root;
    size_t nNodes;
} BST;

对于插入/搜索，我调用

strcmp(string, node->key)

，如果结果 >0，我就转到右子节点，如果是 <0, I go to the left one. If the result is 0, it means I've found a node with a matching key.

Answer 1

在遍历过程中，您不是执行普通的

strcmp(input, key)

，而是检查它们共享的前缀有多少。对于每个前缀长度，您存储找到的

key

具有此前缀的第一个节点。然后，您可以使用这些节点作为起始节点，仅在子树中查找相应的前缀，而不必从根开始。