搜索樹/ 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時返回多個節點？

回答

相關問題