字典树

字典树/前缀树/单词查找树/键树（Trie）：

上图表示了关键字集合 {“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} 。

基本性质：

1. 根节点不包含字符，除根节点外的每一个子节点都包含一个字符。
2. 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符互不相同。
4. 从第一字符开始有连续重复的字符只占用一个节点，比如上面的to，和ten，中重复的单词t只占用了一个节点。

应用：

1. 前缀匹配
2. 字符串检索
3. 词频统计
4. 字符串排序

模版

class Trie {
	class Node {
		int num;// 有多少单词通过这个节点，即由根至该节点组成的字符串模式出现的次数
		Node[] child;// 所有的子节点
		boolean isEnd;// 是不是最后一个节点
		char value;// 节点的值

		Node() {
			num = 1;
			child = new Node[SIZE];
			isEnd = false;
		}
	}

	int SIZE = 26;
	Node root;

	/**
	 * 插入一个单词
	 * 
	 * @param str 单词
	 */
	void insert(String str) {
		if (root == null) {
			root = new Node();
			return;
		}
		if (str == null || str.length() == 0) {
			return;
		}
		Node node = root;
		char[] letters = str.toCharArray();// 将目标单词转换为字符数组
		for (int i = 0, len = str.length(); i < len; i++) {
			int pos = letters[i] - 'a';
			// 如果当前节点的儿子节点中没有该字符，则构建一个TrieNode并复值该字符
			if (node.child[pos] == null) {
				node.child[pos] = new Node();
				node.child[pos].value = letters[i];
			} else {
				// 如果已经存在，则将由根至该儿子节点组成的字符串模式出现的次数+1
				node.child[pos].num++;
			}
			node = node.child[pos];
		}
		node.isEnd = true;
	}

	/**
	 * 计算单词前缀的数量
	 * 
	 * @param prefix 前缀
	 * @return 单词前缀的数量
	 */
	int countPrefix(String prefix) {
		if (prefix == null || prefix.length() == 0) {
			return -1;
		}
		Node node = root;
		char[] letters = prefix.toCharArray();
		for (int i = 0, len = prefix.length(); i < len; i++) {
			int pos = letters[i] - 'a';
			if (node.child[pos] == null) {
				return 0;
			} else {
				node = node.child[pos];
			}
		}
		return node.num;
	}

	/**
	 * 打印指定前缀的单词
	 * 
	 * @param prefix 前缀
	 * @return 单词
	 */
	String hasPrefix(String prefix) {
		if (prefix == null || prefix.length() == 0) {
			return null;
		}
		Node node = root;
		char[] letters = prefix.toCharArray();
		for (int i = 0, len = prefix.length(); i < len; i++) {
			int pos = letters[i] - 'a';
			if (node.child[pos] == null) {
				return null;
			} else {
				node = node.child[pos];
			}
		}
		preTraverse(node, prefix);
		return null;
	}

	/**
	 * 遍历经过此节点的单词
	 * 
	 * @param node 节点
	 * @param prefix 前缀
	 */
	void preTraverse(Node node, String prefix) {
		if (!node.isEnd) {
			for (Node child : node.child) {
				if (child != null) {
					preTraverse(child, prefix + child.value);
				}
			}
			return;
		}
		System.out.println(prefix);
	}

	/**
	 * 存在完全匹配的单词
	 * 
	 * @param str 单词
	 * @return boolean
	 */
	boolean has(String str) {
		if (str == null || str.length() == 0) {
			return false;
		}
		Node node = root;
		char[] letters = str.toCharArray();
		for (int i = 0, len = str.length(); i < len; i++) {
			int pos = letters[i] - 'a';
			if (node.child[pos] != null) {
				node = node.child[pos];
			} else {
				return false;
			}
		}
		// 走到这一步，表明可能完全匹配，可能部分匹配，如果最后一个字符节点为末端节点，则是完全匹配，否则是部分匹配
		return node.isEnd;
	}

	/**
	 * 前序遍历
	 * 
	 * @param node 节点
	 */
	void preTraverse(Node node) {
		if (node != null) {
			System.out.print(node.value + "-");
			for (Node child : node.child) {
				preTraverse(child);
			}
		}
	}
}