实现字典树

题目：实现字典树 （算法课第七课）

Trie树，又称为字典树、单词查找树或者前缀树，是一种用于快速检索的多叉数结构。

英文字母的字典树是26叉数，数字的字典树是10叉树。
Trie树的基本性质有三点，归纳为：

• 根节点不包含字符，根节点外每一个节点都只包含一个字符
• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
• 每个节点的所有子节点包含的字符串不相同

作用

查前缀。

TrieNode

class TrieNode {
    boolean isWord;
    HashMap<Character, TrieNode> nexts;

    public TrieNode() {
        nexts = new HashMap<Character, TrieNode>();
    }
}

代码

public class TrieTree {
	public static class TrieNode {//切记把字母放在边上，不要放在节点里
		public int path;//有多少字符串 以此节点为前缀（被划过多少次）
		public int end;//有多少字符串 以此节点结尾的
		public TrieNode[] nexts;

		public TrieNode() {
			path = 0;
			end = 0;
			nexts = new TrieNode[26];//小写字母a~z
		}
	}

	public static class Trie {
		private TrieNode root;
		public Trie() {
			root = new TrieNode();
		}

		public void insert(String word) {//插入一个word
			if (word == null) {
				return;
			}
			char[] chs = word.toCharArray();
			TrieNode node = root;//从头开始
			int index = 0;
			for (int i = 0; i < chs.length; i++) {
				index = chs[i] - 'a';//减去ASCII码
				if (node.nexts[index] == null) {//有没有 走向下（）对应的字母值的路
					node.nexts[index] = new TrieNode();//向下建路
				}
				node = node.nexts[index];//往下跳一个节点
				node.path++;//被划过多一次
			}
			node.end++;//end 只对应整个String word的尾巴
		}

		public void delete(String word) {
			if (search(word) != 0) {//存在 才能被删除
				char[] chs = word.toCharArray();
				TrieNode node = root;
				int index = 0;
				for (int i = 0; i < chs.length; i++) {
					index = chs[i] - 'a';
					//path减少到0了，直接断掉这条链子	
					if (--node.nexts[index].path == 0) {
						node.nexts[index] = null;//底下节点直接全null
						return;
					}
					node = node.nexts[index];
				}
				node.end--;//以此为结束节点的路又少了一条
			}
		}

		public int search(String word) {
			if (word == null) {
				return 0;
			}
			char[] chs = word.toCharArray();
			TrieNode node = root;
			int index = 0;
			for (int i = 0; i < chs.length; i++) {
				index = chs[i] - 'a';
				if (node.nexts[index] == null) {
					return 0;
				}
				node = node.nexts[index];
			}
			return node.end;//总的
		}
		public int startsWith(String pre) {
			if (pre == null) {
				return 0;
			}
			char[] chs = pre.toCharArray();
			TrieNode node = root;
			int index = 0;
			for (int i = 0; i < chs.length; i++) {
				index = chs[i] - 'a';
				if (node.nexts[index] == null) {
					return 0;
				}
				node = node.nexts[index];
			}
			return node.path;//前缀数量
		}
	}

	public static void main(String[] args) {
		Trie trie = new Trie();
		System.out.println(trie.search("tree"));//0
		trie.insert("tree");
		System.out.println(trie.search("tree"));//1
		trie.delete("tree");
		System.out.println(trie.search("tree"));//0
		
		trie.insert("treea");
		trie.insert("treec"); 
		trie.insert("treeb");
		System.out.println(trie.startsWith("tree"));//3
	}
}

输出：

0
1
0
1
3