Trie字典树

Trie字典树和我们以前学的树结构不同，他是直接从根节点遍历到叶子节点，这样重复就完成了字典树
每个节点有若干个指向下一个节点的指针，考虑不同的语言，不同的情境。我们要有一个判断单词，还有从一个节点到下一个节点的映射具体的实现代码如下：

private class Node{
		public boolean isWord;
		public TreeMap<Character,Node> next;
		
		public Node(boolean isWord) {
			this.isWord = isWord;
			next = new TreeMap<>();
		}
		public Node(){
			this(false);
		}
	}
	private Node root;
	private int size;
	public Trie() {
		root = new Node();
		size = 0;
	}

向Trie中添加一个新的单词word
我们需要设置一个新的节点表示当前节点，让当前节点指向根节点，然后依次往下遍历，我们要注意当前节点的下一个节点是不是应经有了字母，如果是空我们直接创建一个新的节点，如果不是继续往下遍历，然后依次往下遍历直到单词结束，当然有些单词是某些单词的前缀，所以我们要注意这个问题，最后要进行size++；具体的实现代码如下：

//向Trie中添加一个新的单词word
	public void add(String word) {
		Node cur = root;
		for(int i = 0;i < word.length(); i++) {
			char c = word.charAt(i);
			if(cur.next.get(c) == null) {
				cur.next.put(c, new Node());
			}
			cur = cur.next.get(c);
		}
		if(! cur.isWord) {
			cur.isWord = true;
			size ++;
		}
	}

查询单词word是否在Trie中
我们还是像添加单词一样，但是没有那么，麻烦，如果当前节点的下一个节点为空，那么我们直接返回false，如有不为空 那么我们继续往下遍历，如果有这个单词我们就可以返回true，具体实现代码如下：

//查询单词word是否在Trie中
	public boolean contains(String word) {
		Node cur = root;
		for(int i = 0; i < word.length(); i++) {
			char c = word.charAt(i);
			if(cur.next.get(c) == null) {
				return false;
			}
			cur = cur.next.get(c);
		}
		return cur.isWord;
	}

查询是否在Trie中有单词以prefix为前缀
我们需要准备一个prefix，然后在字典树中寻找这个前缀，我们需要注意，如果没有这个前缀，我们就返回false，如果有我们就继续往下遍历，如果能找到这单词，我们就返回true ，具体的实现代码如下：

//查询是否在Trie中有单词以prefix为前缀
	public boolean isPrefix(String prefix) {
		Node cur = root;
		for(int i = 0; i < prefix.length(); i++) {
			char c = prefix.charAt(i);
			if(cur.next.get(c) == null) {
				return false;
			}
			cur = cur.next.get(c);
		}
		return true;
	}

Trie的局限性：最大的问题就是空间
以上是我对trie字典树的理解，不喜勿喷。谢谢！