Trie

添加

IsWord表示一个单词的结束
单词字母内容由平衡二叉树存储

查询

非递归实现

递归实现

前缀

Ternary Search Trie

待更新
在这里插入图片描述

public class Trie
{ 
   
    private class Node
    { 
   
        public bool IsWord;
        public SortedDictionary<char, Node> Next;

        public Node(bool isWord)
        { 
   
            IsWord = isWord;
            Next = new SortedDictionary<char, Node>();
        }

        public Node():this(false)
        { 
   
            
        }
    }

    private Node root;
    private int size;

    public Trie()
    { 
   
        root = new Node(false);
        size = 0;
    }

    public int Size()
    { 
   
        return size;
    }

    // 向 Trie 中添加一个 单词
    public void Add(string word)
    { 
   
        Node cur = root;
        foreach (var ch in word)
        { 
   
            if (!cur.Next.ContainsKey(ch))
                cur.Next[ch] = new Node(false);
            cur = cur.Next[ch];
        }

        if (cur.IsWord) return;

        cur.IsWord = true;
        ++size;
    }

    // 查询单词是否在 Trie 中 非递归实现
    public bool Contains(string word)
    { 
   
        Node cur = root;
        foreach (var ch in word)
        { 
   
            if (!cur.Next.ContainsKey(ch))
                return false;
            cur = cur.Next[ch];
        }

        return cur.IsWord;
    }
    // 递归实现
	public bool ContainsRecursive(string word)
    { 
   
        return Contains(root, word, 0);
    }

    private bool Contains(Node node, string str, int index)
    { 
   
        if (index > str.Length - 1)
            return node.IsWord;
        if (!node.Next.ContainsKey(str[index]))
            return false;
        return Contains(node.Next[str[index]], str, ++index);
    }

    public bool IsPrefix(string prefix)
    { 
   
        Node cur = root;
        foreach (var ch in prefix)
        { 
   
            if (!cur.Next.ContainsKey(ch))
                return false;
            cur = cur.Next[ch];
        }

        return true;
    }
}