搜索树/trie时返回多个节点
本文关键字:节点 返回 trie 搜索树 | 更新日期: 2023-09-27 18:28:02
我构建了一个后缀trie,一个包含字符串所有后缀的树,其中每个节点只包含一个字符,每个路径的末尾都有一个SuffixNode,它包含字符串中后缀的位置。
假设我的trie包含单词"Cat"、"Car"answers"Can",我想搜索"Ca",结果应该返回3个后缀节点,因为搜索字符串在3个不同的地方找到。我设法在树上搜索"Ca",但一旦达到这个点,我就不知道如何继续遍历"a"节点的子节点来找到所有后缀节点。
我正在考虑使用某种集合来添加后缀节点,然后返回集合。这种方法有意义吗?或者有更好的解决方案吗?
我已经解决了下面的搜索问题。它没有返回任何节点的原因与树的创建和节点之间的差异有关:
public void SearchTrie(Node parent, String s, List<SuffixNode> suffixes)
{
Node n = FindNode(parent, s);
FindSuffixes(n, suffixes);
}
private void FindSuffixes(Node parent,List<SuffixNode> suffixes)
{
if (parent is SuffixNode)
{
suffixes.Add((SuffixNode)parent);
}
else
{
foreach (KeyValuePair<char, Node> child in parent.children)
{
FindSuffixes(child.Value, suffixes);
}
}
}
private Node FindNode(Node parent, String s)
{
if ((s.Length == 1) && parent.children.ContainsKey(s[0]))
{
Node n = parent.children[s[0]];
return n;
}
while (s[0].ToString() != "")
{
if (parent.children.ContainsKey(s[0]))
{
if ((s.Length > 1))
{
return FindNode(parent.children[s[0]], s.Substring(1));
}
}
else
{
break;
}
}
return null;
}
节点:
class Node
{
public char label;
public Node parent;
public Dictionary<char,Node> children;
public Node(Node NewParent, char NewLabel)
{
this.parent = NewParent;
this.label = NewLabel;
children=new Dictionary<char,Node>();
}
}
我正在考虑使用某种集合来添加后缀节点,然后返回集合。
那将是第一选择。
还是有更好的解决方案?
还有其他解决方案,如
- 填写呼叫者提供的列表
- 将迭代器块与
yield return
一起使用
但是,如果没有任何特殊要求,请填写List<string>
并将其作为IEnumerable<string>
返回。