data-structures - 探索二叉搜索树

Question

我认为二叉搜索树是最简单的例子，但我真的想知道如何探索三叉搜索树或各种尝试。我对这些没有任何经验，但我了解添加和搜索它们的概念。

我的问题是，当我找到一个与我的输入匹配的节点（例如自动完成）时，我如何有效地收集所有子节点？

Answer 1

这取决于搜索树的实现。如果获取特定节点的所有子节点是您需要执行的常见操作，则应使用使该操作高效的实现。

例如，对于每个节点，您可以存储一个包含指向每个节点子节点的指针的子数组。

Answer 2

对于 Trie，您应该将 Node 结构设置为

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;
    }
}

每个节点将包含一个字符及其子节点的列表
所以您的搜索将看起来像这样

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 时需要任何帮助。让我们知道！

注意在 Trie 节点中，您还可以维护 aboolean marker来指示单词的结尾。您可以使用或不使用它，具体取决于您的应用程序和使用情况。