先上張圖汛聚，從百度百科盜過來的。
字典樹
又稱單詞查找樹短荐，是一種[樹形結(jié)構(gòu)]倚舀，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計忍宋，排序和保存大量的字符串（但不僅限于字符串）痕貌，所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是：利用字符串的公共前綴來減少查詢時間讶踪，最大限度地減少無謂的字符串比較芯侥，查詢效率比哈希樹高。
根節(jié)點不包含字符乳讥，除根節(jié)點外每一個節(jié)點都只包含一個字符柱查； 從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字符連接起來云石，為該節(jié)點對應(yīng)的字符串唉工； 每個節(jié)點的所有子節(jié)點包含的字符都不相同。
圖中紅點表示有單詞結(jié)尾汹忠，比如兩個單詞app跟apple淋硝，其實apple是涵蓋了app的，所以必須得有一個End來表示單詞是否結(jié)尾宽菜，一個end來表示一個單詞谣膳。
這里我們用Java來模擬一個Trie樹
class TrieNode {
TrieNode preNode = null;
boolean isEnd = false;
int deep = 0;//做hash使用，防止一個單詞里面有多個char的時候hash是一樣的铅乡，可能導(dǎo)致刪除出錯
char content = 0;
LinkedList<TrieNode> child = new LinkedList<>();
}
其實就幾個必要的東西：
1. isEnd：是否是紅點继谚，也就是是否是word的結(jié)尾
2. content：當(dāng)前節(jié)點到parent節(jié)點存儲的字母
3. LinkedList<TrieNode> child：子節(jié)點，當(dāng)前節(jié)點后續(xù)節(jié)點
其實字典樹最常見的兩個操作是 查詢 跟 添加 操作阵幸，其實就是很簡單的邏輯了花履，代碼貼在下面。
稍微復(fù)雜些的是刪除的操作挚赊，比如我有這么一個樹诡壁，樹中有這么兩個單詞apple跟app：
字典樹
如果我需要刪除 app這個單詞，我只需要把 紅點 p這個節(jié)點由紅色變?yōu)榘咨秃昧塑睿涂梢粤恕?br> 但如果我需要刪掉apple妹卿，那我要做的不止要把e變?yōu)榘咨€需要找到父節(jié)點l，把l也刪掉纽帖。
當(dāng)然如果我要刪掉apk這個樹中不存在的單詞宠漩，顯然也是失敗的。
所以移除word懊直，三種情況：
- word在list中不存在扒吁，直接返回失敗
- word最后一個char 沒有child，則刪掉此節(jié)點并朝 root 查找沒有child && isEnd=false 的節(jié)點都刪掉
- word最后一個char 有child室囊，則把isEnd置為false
而為了能找到父節(jié)點雕崩，我在Node中加了個parentNode屬性，可能還有更好的解決辦法融撞。
還有個稍微復(fù)雜些的是遍歷操作盼铁，樹的遍歷需要用到遞歸，說到遞歸尝偎，就得想到回溯法饶火，可以看一下我寫的回溯法的一個文章。
import util.LogUtil;
import java.util.LinkedList;
/**
* Created by yocn on 2019/6/13.
* 字典樹實現(xiàn)
*/
public class TrieTree {
private TrieNode root = new TrieNode();
public void test() {
addWord("abc");
addWord("abcd");
addWord("abe");
// addWord("akl");
// addWord("apple");
// addWord("world");
// addWord("word");
// traverseTree();
// removeWord("abcd");
removeWord("abc");
traverseTree();
}
static class TrieNode {
TrieNode preNode = null;
boolean isEnd = false;
int deep = 0;//做hash使用致扯，防止一個單詞里面有多個char的時候hash是一樣的肤寝，可能導(dǎo)致刪除出錯
char content = 0;
LinkedList<TrieNode> child = new LinkedList<>();
TrieNode() {
}
TrieNode(char content) {
this.content = content;
}
@Override
public String toString() {
return "\n" + "{" +
"End=" + isEnd +
", d=" + deep +
", c=" + content +
", c=" + child +
'}';
}
public String toSimpleString() {
return "\n" + "{" +
"End=" + isEnd +
", d=" + deep +
", c=" + content +
'}';
}
@Override
public int hashCode() {
return content + deep;
}
@Override
public boolean equals(Object obj) {
return obj instanceof TrieNode && (((TrieNode) obj).content == content);
}
void setPreNode(TrieNode node) {
preNode = node;
}
TrieNode getPreNode() {
return preNode;
}
/**
* child中刪掉某個Node
*
* @param node 需要刪掉的node
*/
void removeChild(TrieNode node) {
for (TrieNode aChild : child) {
if (aChild.content == node.content) {
child.remove(aChild);
break;
}
}
}
/**
* child中是否有此Node
*
* @param character 保存的char
* @return 存在返回不存在返回Null
*/
TrieNode getNode(Character character) {
for (TrieNode aChild : child) {
if (aChild.content == character) {
return aChild;
}
}
return null;
}
}
/**
* 添加一個word
* apple
*
* @param word 需要添加的詞
*/
public void addWord(String word) {
int deep = 0;
TrieNode currNode = root;
while (deep < word.length()) {
/*
* 判斷當(dāng)前node的child，如果為空直接添加抖僵，不為空鲤看，查找是否含有，不含有則添加并設(shè)為currNode耍群，含有則找到并設(shè)置為currNode
*/
char c = word.charAt(deep);
if (currNode.child.contains(new TrieNode(c))) {
currNode = currNode.getNode(c);
} else {
TrieNode node = new TrieNode(c);
node.setPreNode(currNode);
node.deep = deep + 1;
currNode.child.add(node);
currNode = node;
}
if (deep == word.length() - 1) {
currNode.isEnd = true;
}
deep++;
}
}
/**
* word在map中是否存在
*
* @param word 需要查找的word
* @return 是否存在
*/
public boolean hasWord(String word) {
int deep = 0;
TrieNode currNode = root;
while (deep < word.length()) {
char c = word.charAt(deep);
if (currNode.child.contains(new TrieNode(c))) {
currNode = currNode.getNode(c);
} else {
return false;
}
if (deep == word.length() - 1) {
return currNode.isEnd;
}
deep++;
}
return false;
}
/**
* 移除word义桂，幾種情況：
* 1、word在list中不存在蹈垢，直接返回失敗
* 2慷吊、word最后一個char 沒有child，則刪掉此節(jié)點并朝 root 查找沒有child && isEnd=false 的節(jié)點都刪掉
* 3曹抬、word最后一個char 有child罢浇，則把isEnd置為false
*
* @param word 需要移除的word
* @return 是否移除成功
*/
public boolean removeWord(String word) {
if (word == null || word.trim().equals("")) {
return false;
}
if (!hasWord(word)) {
return false;
}
int deep = 0;
TrieNode currNode = root;
while (deep < word.length()) {
char c = word.charAt(deep);
if (currNode.child.contains(new TrieNode(c))) {
currNode = currNode.getNode(c);
} else {
return false;
}
if (deep == word.length() - 1) {
// 把isEnd置為false
currNode.isEnd = false;
if (currNode.child.size() > 0) {
//3、word最后一個char 有child，結(jié)束
return true;
} else {
//2、word最后一個char 沒有child掩浙，則刪掉此節(jié)點并朝 root 查找沒有child && isEnd=false 的節(jié)點都刪掉
TrieNode parent = currNode.getPreNode();
while (parent != null) {
if (parent.child.size() == 0 && !parent.isEnd) {
parent.removeChild(currNode);
currNode = parent;
parent = currNode.preNode;
} else {
parent.removeChild(currNode);
return true;
}
}
}
}
deep++;
}
return false;
}
/**
* 前序遍歷所有節(jié)點星立，需要用到回溯法
*/
public void traverseTree() {
visitNode(root, "");
}
private void visitNode(TrieNode node, String result) {
LogUtil.Companion.d(node.toSimpleString());
String re = result + node.content;
for (TrieNode n : node.child) {
visitNode(n, re);
// LogUtil.Companion.d("result->" + re);
}
}
}
