我有一个存储字符串的二叉搜索树。字符串按字典顺序进行比较(使用 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.
在遍历过程中,您不是执行普通的
strcmp(input, key)
,而是检查它们共享的前缀有多少。对于每个前缀长度,您存储找到的 key
具有此前缀的第一个节点。然后,您可以使用这些节点作为起始节点,仅在子树中查找相应的前缀,而不必从根开始。