探索一個二叉搜索樹

Question

我想一個二叉搜索樹是最簡單的例子，但我真的想知道如何探索三元搜索樹或一些嘗試各種。我對這些沒有任何經驗，但我理解添加和搜索它們的概念。

我的問題是，當我找到與我的輸入相匹配的節點（如自動完成），我如何有效地收集所有的子節點？

Answer 1

這取決於您的搜索樹的實施。如果獲得特定節點的所有子節點是您需要執行的常見操作，則應該使用能夠使該操作高效的實現。

例如，對於每個節點，您可以存儲包含指向每個節點的子節點的指針的子節點數組。

Answer 2

對於特里，你應該有節點結構

class Node 
{ 
    char data; 
    ArrayList<Node> children; 

    public Node getChild(char data) 
    { 
     for(Node child : this.children) 
      if(child.data == data) 
       return child; 
     return null; 
    } 
} 

每個節點將包含其子節點的性格和列表
所以，你的搜索將loook這樣的事情

public boolean search(String s) 
{ 
    Node current = root;   // root is the Node present in Trie 
    for(int i=0; i<s.length(); i++) 
    { 
     char c = s.charAt(i); 
     Node n = current.getChild(c); 
     if(n==null) 
      return false; // Match not present 
     current = n; 
    } 
    return true;  // Match found 
} 

上面的搜索方法只是檢查搜索到的字符串是否存在於您的trie中。你可以調整它收集所有的孩子根據您的要求（這是保留給你:)）

希望這可以幫助你，並給你一個想法如何收集它。 如果需要任何幫助來填充特里。讓我們知道！

備註在Trie節點中，您還可以維護boolean marker以指示單詞的結尾。您可以根據您的應用和使用情況使用或不使用它。