Tire树

单词查找树可以用于搜索引擎的搜索匹配，利用树结构与键值对，键是构成词组的所有结点的集合，而值存在于最深的结点之中，类似于二叉排序树之类的树结构，Tire树的生成，查询，删除都基于递归实现；

具体实现见代码：

java

package trie;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author lszzz
 * @create 2020/4/17
 */
public class TrieST<V> {
	/**
	 * 基数：所有链接,之所以为256个是因为(在英文中)ASCII码一共有256个字符编码0-255,如果考虑汉字则需要进行拓展；】‘
	 */
	private static int R=65293;
	/**
	 * 单词查找树根节点
	 */
	private Node root;

	/**
	 * 使用静态内部类对外部进行隐藏
	 */
	private static class Node{
		//具体的每个结点内容
		private Object val;
		//有多个向下的节点链接
		private Node[] next=new Node[R];
	}

	/**
	 * 进行重载方便外界使用
	 * @param key
	 * @return
	 */
	public V get(String key)
	{
		Node x=get(root,key,0);
		if(x==null)
		{
			return null;
		}
		return (V) x.val;
	}
	/**
	 * 实现原理，利用递归，查找每一层的字符，知道查找到为null或深度达到单词长度结束递归。
	 * @param x
	 * @param key
	 * @param d
	 * @return
	 */
	public Node get(Node x,String key,int d)
	{
		//返回以x作为根结点的子单词查找树中与key相关联的值。
		if(x==null)
		{
			return null;
		}
		if(d==key.length())
		{
			return x;
		}
		//找到第d个单词
		char c=key.charAt(d);
		//使用字符编码作为c的值
		return get(x.next[c],key,d+1);
	}
	public void put(String key,V val)
	{
		root=put(root,key,val,0);
	}
	public Node put(Node x,String key,V val,int d)
	{
		//如果没有此节点就创建节点。
		if(x==null)
		{
			x=new Node();
		}
		//Trie的值存于键的最后一个结点中。
		if(d==key.length())
		{
			x.val=val;
			//返回最后结点
			return x;
		}
		//找到第d个字符对应的单词查找树
		char c=key.charAt(d);
		x.next[c]=put(x.next[c],key,val,d+1);
		//返回结点，将结点从底部连接起来。
		return x;
	}
	public int size()
	{
		return size(root);
	}
	public int size(Node x)
	{
		if(x==null)
		{
			return 0;
		}
		int cnt=0;
		//访问到末尾有值算一个。
		if(x.val!=null) cnt++;
		for(char c=0;c<R;c++)
		{
			cnt+=size(x.next[c]);
		}
		return cnt;
	}
	//递归，使用queue存取以pre为前缀的所有字符串，如果想要遍历，pre="",即·pre为root
	public Iterable<String> keys()
	{
		return keysWithPrefix("");
	}
	public Iterable<String> keysWithPrefix(String pre)
	{
		Queue<String> q=new LinkedList<>();
		collect(get(root,pre,0),pre,q);
		return q;
	}
	private void collect(Node x,String pre,Queue<String>q)
	{
		if(x==null)
		{
			return;
		}
		if(x.val!=null)
		{
			q.add(pre);
		}
		for(char c=0;c<R;c++)
		{
			//继续递归增加下一个字符，判断存不存在。
			collect(x.next[c],pre+c,q);
		}
	}

	/**
	 * 通配符匹配，在每个字节点比较的时候加上一个.条件即可，但结束条件必须既满足长度匹配，有满足是最终节点
	 * @param pat
	 * @return
	 */
	public Iterable<String> keysThatMatch(String pat)
	{
		Queue<String>q=new LinkedList<>();
		collect(root,"",pat,q);
		return q;
	}
	private void collect(Node x,String pre,String pat,Queue<String> q)
	{
		int d=pre.length();
		if(x==null)
		{
			return;
		}
		if(x.val!=null&&d==pat.length()){
			q.add(pre);
		}
		if(d==pat.length())
		{
			return;
		}
		char next=pat.charAt(d);
		for(char c=0;c<R;c++)
		{
			if(next=='.'||next==c)
			{
				collect(x.next[c],pre+c,pat,q);
			}
		}
	}
	/**
	 * 最长前缀，类似于get的递归
	 */
	public String longestPrefixOf(String s)
	{
		int length=search(root,s,0,0);
		return s.substring(0,length);
	}
	public int search(Node x,String s,int length,int d)
	{
		if(x==null)
		{
			return length;
		}
		if(x.val!=null)
		{
			length=d;
		}
		if(d==s.length())
		{
			return s.length();
		}
		char c=s.charAt(d);
		return search(x.next[c],s,length,d+1);
	}
	/**
	 * 删除一个键值对，首先找到键对应的节点，将其值设为null，若其有子节点结束操作，若无子节点则删除该节点。
	 * 同样使用递归的方法。
	 */
	public void delete(String key)
	{
		root=delete(root,key,0);
	}
	public Node delete(Node x,String key,int d)
	{
		if(x==null)
		{
			return null;
		}
		if(d==key.length())
		{
			x.val=null;
		}
		else
		{
			char c=key.charAt(d);
			x.next[c]=delete(x.next[c],key,d+1);
		}
		//防止给的key过长，val会不为null；
		if(x.val!=null)
		{
			//返回的x不变
			return x;
		}
		for(char c=0;c<R;c++)
		{
			//判断子节点是否为空，不为空返回x，空则返回null;
			if(x.next[c]!=null)
			{
				return x;
			}
		}
		return null;
	}
}