實現(xiàn)Trie 的核心是每個節(jié)點包含子節(jié)點映射和是否為單詞結(jié)尾的標記。具體步驟如下：1. 定義TrieNode 類，使用Map 或數(shù)組保存子節(jié)點，並設(shè)置isEndOfWord 標記；2. 構(gòu)建Trie 類，提供insert、search 和startsWith 方法；3. 插入時利用computeIfAbsent 簡化子節(jié)點處理，搜索時需判斷是否存在且為完整單詞，前綴判斷只需檢查路徑存在性；4. 注意空字符串及標記設(shè)置等細節(jié)問題。

實現(xiàn)一個Trie（前綴樹）在Java 中其實並不復(fù)雜，但很多人第一次接觸時可能會覺得有點繞。 Trie 是一種樹形結(jié)構(gòu)，特別適合處理字符串相關(guān)的查找問題，比如自動補全、拼寫檢查等。

我們先簡單說一下重點：Trie 的核心是每個節(jié)點保存子節(jié)點的映射，並通過標記來判斷是否是一個完整單詞的結(jié)尾。

什麼是Trie 節(jié)點

Trie 的基本單位是節(jié)點（Node）。每個節(jié)點通常包含兩個部分：

• 一個字符映射到子節(jié)點的哈希表（或數(shù)組）
• 一個標誌位，表示該節(jié)點是否是一個單詞的結(jié)尾

我們可以用一個類來表示Trie 節(jié)點：

 class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;

    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

這樣設(shè)計的好處是靈活性強，能支持各種字母組合。如果你確定只處理小寫字母，也可以用長度為26 的數(shù)組替代哈希表，效率會更高。

如何構(gòu)建Trie 類

整個Trie 結(jié)構(gòu)從根節(jié)點開始，對外提供插入（insert）、搜索（search）和前綴判斷（startsWith）三個方法比較常見。

下面是一個完整的Trie 實現(xiàn)框架：

 public class Trie {
    private TrieNode root;

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

    // 插入一個單詞public void insert(String word) {
        TrieNode current = root;
        for (char ch : word.toCharArray()) {
            current = current.children.computeIfAbsent(ch, c -> new TrieNode());
        }
        current.isEndOfWord = true;
    }

    // 判斷某個單詞是否存在public boolean search(String word) {
        TrieNode node = getNode(word);
        return node != null && node.isEndOfWord;
    }

    // 判斷是否有以該字符串為前綴的單詞public boolean startsWith(String prefix) {
        return getNode(prefix) != null;
    }

    // 輔助方法：獲取某個字符串對應(yīng)的最後一個節(jié)點private TrieNode getNode(String prefix) {
        TrieNode current = root;
        for (char ch : prefix.toCharArray()) {
            current = current.children.get(ch);
            if (current == null) {
                return null;
            }
        }
        return current;
    }
}

這段代碼的關(guān)鍵在於insert方法中使用了computeIfAbsent ，可以避免每次都手動判斷是否已經(jīng)存在子節(jié)點。

使用示例與註意事項

你可以像下面這樣使用這個Trie：

 Trie trie = new Trie();
trie.insert("apple");
System.out.println(trie.search("apple")); // true
System.out.println(trie.search("app")); // false
System.out.println(trie.startsWith("app")); // true
trie.insert("app");
System.out.println(trie.search("app")); // true

幾點需要注意的地方：

• 插入空字符串不會出錯，但也不會創(chuàng)建任何節(jié)點
• search("app")返回false 是因為雖然路徑存在，但沒有被標記為單詞結(jié)尾
• 如果你只需要判斷前綴， startsWith比search更合適

基本上就這些了。 Trie 的結(jié)構(gòu)清晰，邏輯也不算複雜，但細節(jié)上容易忽略，比如忘記設(shè)置isEndOfWord或者沒處理好空字符串的情況。只要理清每一步操作的目的，實現(xiàn)起來還是挺順手的。

以上是在Java中實現(xiàn)Trie（前綴樹）的詳細內(nèi)容。更多資訊請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！