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

问题描述 投票:0回答:1

我有一个存储字符串的二叉搜索树。字符串按字典顺序进行比较(使用 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.

string algorithm binary-search-tree
1个回答
0
投票

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

strcmp(input, key)
,而是检查它们共享的前缀有多少。对于每个前缀长度,您存储找到的
key
具有此前缀的第一个节点。然后,您可以使用这些节点作为起始节点,仅在子树中查找相应的前缀,而不必从根开始。

© www.soinside.com 2019 - 2024. All rights reserved.