0

我想知道是否可以修改三元搜索树以检查该单词是否存在并找到以该单词开头的所有单词（或以该单词结尾？）？例如do=>dog dogs等。

从这个站点是一个示例代码。首先将所有单词加载到三叉树中，然后我们可以使用方法检查单词是否存在。

public class TernaryTree
{
    private Node m_root = null;

    private void Add(string s, int pos, ref Node node)
    {
        if (node == null) { node = new Node(s[pos], false); }

        if (s[pos] < node.m_char) { Add(s, pos, ref node.m_left); }
        else if (s[pos] > node.m_char) { Add(s, pos, ref node.m_right); }
        else
        {
            if (pos + 1 == s.Length) { node.m_wordEnd = true; }
            else { Add(s, pos + 1, ref node.m_center); }
        }
    }

    public void Add(string s)
    {
        if (s == null || s == "") throw new ArgumentException();

        Add(s, 0, ref m_root);
    }

    public bool Contains(string s)
    {
        if (s == null || s == "") throw new ArgumentException();

        int pos = 0;
        Node node = m_root;
        while (node != null)
        {
            int cmp = s[pos] - node.m_char;
            if (s[pos] < node.m_char) { node = node.m_left; }
            else if (s[pos] > node.m_char) { node = node.m_right; }
            else
            {
                if (++pos == s.Length) return node.m_wordEnd;
                node = node.m_center;
            }
        }

        return false;
    }
}

class Node
{
    internal char m_char;
    internal Node m_left, m_center, m_right;
    internal bool m_wordEnd;

    public Node(char ch, bool wordEnd)
    {
        m_char = ch;
        m_wordEnd = wordEnd;
    }
}

这让我在我脑海中浮现出巨大的:(
任何得到那个词的方法都可以。但是我在那个级别的算法上很弱。
我希望我不会重复任何关于这个的问题。任何建议我都会感激.

4

1 回答 1

1

为此可以使用三叉树，但我不建议这样做（这样做不容易）。

我认为您可以使用两种不同的方法：

A.，使用标准Trie而不是三叉树，因此无论 Trie 中有多少项目，您的查找时间都将被视为恒定。AC# 实现是可以实现的，但请记住，Trie 需要平均/高级别的算法知识。

B.，使用标准的排序数组（字符串 []）。由于您的要求只是根据前缀创建自动补全，因此将所有单词存储在 string[] 中并对其进行二进制搜索。搜索时间不是恒定的，而是对数的，但即使您在该数组中存储了数百万个单词，每次搜索也可以在几分之一毫秒内进行测量（例如，如果您在该数组中有一百万个单词，则只有 20 次操作需要找到您正在寻找的那个）。即使二分查找不成功，您也会有一个最接近匹配的索引（但索引将为负值，表示匹配不成功）。所以，在这个数组中：

A 
C
D 
E

如果您搜索 B，您将获得索引 0，指向 A。如果您开始加紧，您将看到“B”（或您的示例中的“狗”）之后的项目。

因此，即使您在二分搜索后有完全或部分匹配，也要继续列出数组中的项目，直到搜索到的关键字位于字典单词的开头。

于 2012-01-25T09:53:36.763 回答