前缀树（字典树）Trie Java实现

仅适用a-z的版本

package com.algorithm.offer;
/**
 * Trie树(前缀树、字典树)
 * @author Lenovo
 *
 */
class TrieNode{
          
   
	// 假设字符只有a-z
	TrieNode[] children = new TrieNode[26];
	// 是否是末尾节点
	boolean isEnd;
}
public class Trie {
          
   
	static TrieNode trie;
	// 构建一棵Trie树
	public Trie() {
          
   
		trie = new TrieNode();
	}
	public void insert(String word) {
          
   
		// 从根节点开始搜索
		TrieNode cur = trie;
		char[] words = word.toCharArray();
		for(int i = 0;i < words.length;i++) {
          
   
			int idx = words[i] - a;
			// 说明不存在该节点
			if(cur.children[idx] == null) {
          
   
				TrieNode tmp = new TrieNode();
				if(i == words.length - 1) {
          
   
					tmp.isEnd = true;
				}
				cur.children[idx] = tmp;
			}
			cur = cur.children[idx];
		}
	}
	public boolean search(String word) {
          
   
		TrieNode cur = trie;
		char[] words = word.toCharArray();
		for(int i = 0;i < words.length;i++) {
          
   
			int idx = words[i] - a;
			// 说明不存在该节点
			if(cur.children[idx] == null) {
          
   
				return false;
			}
			else {
          
   
				cur = cur.children[idx];
			}
		}
		if(!cur.isEnd) return false;
 		return true;
	}
	public boolean isPrefix(String prefix) {
          
   
		TrieNode cur = trie;
		char[] words = prefix.toCharArray();
		for(int i = 0;i < words.length;i++) {
          
   
			int idx = words[i] - a;
			// 说明不存在该节点
			if(cur.children[idx] == null) {
          
   
				return false;
			}
			else {
          
   
				cur = cur.children[idx];
			}
		}
		if(cur.isEnd) return false;
 		return true;
	}
	
	
	public static void main(String[] args) {
          
   
		Trie trie = new Trie();
		trie.insert("abc");
		System.out.println(trie.search("abc"));
		System.out.println(trie.search("ab"));
		System.out.println(trie.search("abcd"));
		System.out.println(trie.isPrefix("ab"));
		System.out.println(trie.isPrefix("a"));
		System.out.println(trie.isPrefix("b"));
	}
	
}

适用所有字符的版本

package com.algorithm.offer;

import java.util.HashMap;
import java.util.Map;

/**
 * 实现动态增加的Trie,动态数组或者HashMap
 * @author Lenovo
 *
 */
class TrieNodeD{
          
   
	Map<Character,TrieNodeD> map = new HashMap<Character,TrieNodeD>();
	boolean isEnd;
}
public class TrieDynamic {
          
   
	TrieNodeD trie;
	public TrieDynamic() {
          
   
		trie = new TrieNodeD();
	}
	public void insert(String word) {
          
   
		TrieNodeD cur = trie;
		char[] words = word.toCharArray();
		for(int i = 0;i < words.length;i++) {
          
   
			if(cur.map.get(words[i]) == null) {
          
   
				TrieNodeD tmp = new TrieNodeD();
				if(i == words.length - 1) tmp.isEnd = true;
				cur.map.put(words[i],tmp);
			}
			cur = cur.map.get(words[i]);
		}
	}
	
	public boolean search(String word) {
          
   
		TrieNodeD cur = trie;
		char[] words = word.toCharArray();
		for(int i = 0;i < words.length;i++) {
          
   
			if(cur.map.get(words[i]) == null) {
          
   
				return false;
			}
			cur = cur.map.get(words[i]);
		}
		if(!cur.isEnd) return false;
		return true;
	}
	
	public boolean isPrefix(String word) {
          
   
		TrieNodeD cur = trie;
		char[] words = word.toCharArray();
		for(int i = 0;i < words.length;i++) {
          
   
			if(cur.map.get(words[i]) == null) {
          
   
				return false;
			}
			cur = cur.map.get(words[i]);
		}
		if(cur.isEnd) return false;
		return true;
	}
	
	public static void main(String[] args) {
          
   
		TrieDynamic trie = new TrieDynamic();
		trie.insert("abc");
		trie.insert("aB.S#");
		System.out.println(trie.search("ab"));
		System.out.println(trie.search("abc"));
		System.out.println(trie.isPrefix("ab"));
		System.out.println(trie.isPrefix("abc"));
		System.out.println(trie.search("aB.S#"));
		System.out.println(trie.isPrefix("aB."));	
	}
}

很多功能有待实现…