键树，又称数字查找树(Digital Search Trees)是一棵度>=2的树，每个结点只含有组成关键字的符号。

键树有两种存储结构：

1、树的孩子-兄弟链表来表示键树。

每个Node有三个域：first指向第一棵子树的根指针；next指向右兄弟；info（可选的）记录附加数据。如下图：

查找过程是，从根结点出发，顺着first查找，如果相等，继续下一个first。否则沿着next查找。直到到了空指针为止。此时若仍未完成key的匹配，查找不成功。

2、以树的多重链表表示键树(Trie树)。

每个结点中含有d个指针域，此时又称Trie树。

Trie树中有两种结点：
(1)分支结点：含有d个指针域，整数n记录非空指针域的个数(可选)。
(2)叶子结点：含有关键字域(完整的关键字、可选)、附加数据域名(可选)。

实际实现的时候，一般都偷懒，只包含那d个指针域。

如下图：

在标准Trie树的基础上，可以压缩：若从键树中某个结点到叶子结点的路径上每个结点都只有一个孩子，则可将该路径上的所有结点压缩成一个叶子结点。如下图所示：

一个标准Trie树的Java实现如下：

import java.util.Arrays;

public class TrieNode {

	public TrieNode() {
		ptr = new TrieNode[BRANCH];
		Arrays.fill(ptr, null);
	}

	public static final int BRANCH = 27;
	public TrieNode[] ptr = null;
	public int nptr = 0;
}

public class Trie {

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

	public void Insert(String key) {
		TrieNode p = root;
		for (int i = 0; i < key.length(); i++) {
			int offset = key.charAt(i) - 'a';
			if (p.ptr[offset] == null) {
				p.ptr[offset] = new TrieNode();
				p.nptr++;
			}
			p = p.ptr[offset];
		}
	}

	public boolean Search(String key) {
		TrieNode p = root;
		for (int i = 0; i < key.length(); i++) {
			int offset = key.charAt(i) - 'a';
			if (p.ptr[offset] == null) {
				return false;
			}
			p = p.ptr[offset];
		}
		return true;
	}

	private TrieNode root = null;

	public static void main(String[] args) {
		Trie trie = new Trie();
		trie.Insert("liheyuan");
		trie.Insert("liheyuan");
		System.out.println(trie.Search("liheyuan"));
	}
}

 延伸阅读：中文Trie树

摘抄自：http://hxraid.iteye.com/blog/618962

由于中文的字远比英文的26个字母多的多。因此对于trie树的内部结点，不可能用一个26的数组来存储指针。如果每个结点都开辟几万个中国字的指针空间。估计内存要爆了，就连磁盘也消耗很大。

一般我们采取这样种措施：

(1) 以词语中相同的第一个字为根组成一棵树。这样的话，一个中文词汇的集合就可以构成一片Trie森林。这篇森林都存储在磁盘上。森林的root中的字和root所在磁盘的位置都记录在一张以Unicode码值排序的有序字表中。字表可以存放在内存里。

(2) 内部结点的指针用可变长数组存储。

特点：由于中文词语很少操作4个字的，因此Trie树的高度不长。查找的时间主要耗费在内部结点指针的查找。因此将这项指向字的指针按照字的Unicode码值排序，然后加载进内存以后通过二分查找能够提高效率。

补充：我觉得对于字典这种应用，改动会很小的，真的可以内存中Trie树+二分查找搞定。