java实现tire树

Trie树，又称前缀树或字典树，是一种用于快速检索字符串数据集中字符串的树形数据结构。它是一种哈希树的变种，通常用于实现搜索引擎中的自动补全和拼写检查等功能。

在Java中实现Trie树，你可以按照以下步骤进行：

1. 定义Trie树的节点结构。每个节点包含一个字典，用于存储其子节点，以及一个标志位来标识该节点是否是一个单词的结束。

2. 创建Trie树类，其中包含插入（insert）、查找（search）和删除（delete）等基本操作。

3. 插入操作将字符串分解成字符，并在Trie树中从根节点开始逐个字符地向下构建路径，直到字符串末尾。如果路径不存在，则创建新的节点。

4. 查找操作将字符串分解成字符，并在Trie树中从根节点开始逐个字符地查找，直到字符串末尾。如果能够找到路径并且最后一个字符对应的节点标记为单词的结束，则查找成功。

5. 删除操作需要从叶子节点开始，向上遍历并删除节点，直到遇到一个标记为其他单词的一部分的节点为止。

以下是一个简单的Trie树实现示例：

class TrieNode {
    private TrieNode[] children;
    private boolean isEndOfWord;

    public TrieNode() {
        children = new TrieNode[26]; // 假设字符集只有小写英文字母
        isEndOfWord = false;
    }

    public boolean containsKey(char ch) {
        return children[ch - 'a'] != null;
    }

    public TrieNode get(char ch) {
        return children[ch - 'a'];
    }

    public void put(char ch, TrieNode node) {
        children[ch - 'a'] = node;
    }

    public void setEndOfWord() {
        isEndOfWord = true;
    }

    public boolean isEndOfWord() {
        return isEndOfWord;
    }
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.containsKey(ch)) {
                node.put(ch, new TrieNode());
            }
            node = node.get(ch);
        }
        node.setEndOfWord();
    }

    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEndOfWord();
    }

    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }

    private TrieNode searchPrefix(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (node.containsKey(ch)) {
                node = node.get(ch);
            } else {
                return null;
            }
        }
        return node;
    }
}

在上述代码中，`TrieNode` 类表示Trie树的节点，`Trie` 类提供了基本的插入、搜索和前缀匹配操作。