搜索树/ trie时返回多个节点？

我构建了一个后缀trie，一个包含所有字符串后缀的树，其中每个节点只包含一个字符，每个路径末尾都有一个SuffixNode，后缀包含字符串中后缀的位置。搜索树/ trie时返回多个节点？

假设我的trie包含单词“Cat”，“Car”和“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>(); 
    } 
}

来源

2012-03-17 Matt

你可以请张贴一些代码/例子吗？这可能有助于理解这个问题......因为IMO只需遍历子树（在“CA”下面）...... – digEmAll 2012-03-17 11:40:19

这就是我想要做的，但是我发现它有点困难。我会发布我以前的搜索功能，其他代码会有用吗？ – Matt 2012-03-17 11:50:14

你也可以发布Node类吗？ – digEmAll 2012-03-17 12:21:13

我在考虑使用某种的集合添加后缀节点，然后返回集合。

这将是第一选择。

...，还是有更好的解决方案？

还有其他的解决方案，如

填充调用者
使用与yield return

但W/O型的任何特殊要求迭代器块提供的名单，填补了List<string>并将其作为IEnumerable<string>返回。

来源

2012-03-17 12:28:53

搜索树/ trie时返回多个节点？

回答

相关问题