字典树（Trie树）的原理与实现

喜欢ヅ旅行 2022-01-30 00:51 176阅读 0赞

## 一、概述 ##

## 1.1 基本概念 ##

字典树，又称为单词查找树，Tire数，是一种树形结构，它是一种哈希树的变种。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nX2Jv_size_16_color_FFFFFF_t_70]

### 1.2 基本性质 ###

*  根节点不包含字符，除根节点外的每一个子节点都包含一个字符
 *  从根节点到某一节点。路径上经过的字符连接起来，就是该节点对应的字符串
 *  每个节点的所有子节点包含的字符都不相同

### 1.3 应用场景 ###

典型应用是用于统计，排序和保存大量的字符串(不仅限于字符串)，经常被搜索引擎系统用于文本词频统计。

### 1.4 优点 ###

利用字符串的公共前缀来减少查询时间，最大限度的减少无谓的字符串比较，查询效率比哈希树高。

## 二、trie树的构建与操作实现 ##

### 2.1 字典树节点定义 ###

//定义字典表节点（简化设计，仅兼容26个小写英文字符）
    class TrieNode { 
    	
    	private int num; //有多少单词经过当前节点，即由根节点到该节点组成的字符串模式出现的次数
    	private TrieNode[] son;//子节点数组
    	private boolean wordEnd;//是否是叶子结点
    	private char val;//当前节点的值
    	
    	TrieNode() { 
    		num =1;
    		son = new TrieNode[engNum];
    		wordEnd = false;
    	}
    }

### 2.2 字典树构造函数 ###

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

### 2.3 建立字典树 ###

//建立字典树
    public void insert(String str) { 
    	if(StringUtils.isEmpty(str)) { 
    		return;
    	}
    	TrieNode curNode = root;
    	char[] arr = str.toCharArray();
    	for(char c:arr) { 
    		int index = c-'a';
    		TrieNode node = curNode.son[index];
    		if(node == null) { 
    			//当前节点为空则创建
    			curNode.son[index] = new TrieNode();
    			curNode.son[index].val = c;
    		}else { 
    			//不为空则加一
    			node.num = node.num +1;
    		}
    		curNode = curNode.son[index];
    	}
    	curNode.wordEnd = true;
    }

### 2.4 在字典树中查找是否完全匹配一个指定的字符串 ###

//在字典中查找一个完全匹配的单词
    public boolean has(String str) { 
    	if(StringUtils.isEmpty(str)) { 
    		return false;
    	}
    	TrieNode node = root;
    	//找到指定前缀在字典树的位置
    	char[] arr = str.toCharArray();
    	for(int i=0;i<arr.length;i++) { 
    		int index = arr[i] -'a';
    		if(node.son[index] == null) { 
    			return false;
    		}
    		node = node.son[index];
    	}
    	//到这里，如果最后的字符是叶子结点，则完全匹配；否则为部分匹配；
    	return node.wordEnd;
    }

### 2.5 前序遍历字典树 ###

//前序遍历字典树
    public void preTraverse(TrieNode root) { 
    	if(root != null) { 
    		System.out.println(root.val);
    		for(TrieNode son: root.son) { 
    			preTraverse(son);
    		}
    	}
    }

### 2.6 计算指定前缀的单词的数量 ###

//计算指定前缀的单词的数量
    public int countPrefix(String prefix) { 
    	if(StringUtils.isEmpty(prefix)) { 
    		return 0;
    	}
    	TrieNode node = root;
    	char[] arr = prefix.toCharArray();
    	for(int i=0;i<arr.length;i++) { 
    		int index = arr[i] -'a';
    		if(node.son[index] == null) { 
    			return 0;
    		}
    		node = node.son[index];
    	}
    	
    	return node.num;
    }

### 2.7 完整代码 ###

public class Trie { 
    	
    	public static int asciiNum = 128;
    	public static int engNum = 26;
    	
    	private TrieNode root;
    	
    	public Trie() { 
    		root = new TrieNode();
    	}
    	
    	//定义字典表节点（简化设计，仅兼容26个小写英文字符）
    	class TrieNode { 
    		
    		private int num; //有多少单词经过当前节点，即由根节点到该节点组成的字符串模式出现的次数
    		private TrieNode[] son;//子节点数组
    		private boolean wordEnd;//是否是叶子结点
    		private char val;//当前节点的值
    		
    		TrieNode() { 
    			num =1;
    			son = new TrieNode[engNum];
    			wordEnd = false;
    		}
    	}
    	
    	//建立字典树
    	public void insert(String str) { 
    		if(StringUtils.isEmpty(str)) { 
    			return;
    		}
    		TrieNode curNode = root;
    		char[] arr = str.toCharArray();
    		for(char c:arr) { 
    			int index = c-'a';
    			TrieNode node = curNode.son[index];
    			if(node == null) { 
    				//当前节点为空则创建
    				curNode.son[index] = new TrieNode();
    				curNode.son[index].val = c;
    			}else { 
    				//不为空则加一
    				node.num = node.num +1;
    			}
    			curNode = curNode.son[index];
    		}
    		curNode.wordEnd = true;
    	}
    	
    	//计算指定前缀的单词的数量
    	public int countPrefix(String prefix) { 
    		if(StringUtils.isEmpty(prefix)) { 
    			return 0;
    		}
    		TrieNode node = root;
    		char[] arr = prefix.toCharArray();
    		for(int i=0;i<arr.length;i++) { 
    			int index = arr[i] -'a';
    			if(node.son[index] == null) { 
    				return 0;
    			}
    			node = node.son[index];
    		}
    		
    		return node.num;
    	}
    	
    	//打印指定前缀的单词
    	public void hasPrefix(String prefix) { 
    		if(StringUtils.isEmpty(prefix)) { 
    			return;
    		}
    		TrieNode node = root;
    		//找到指定前缀在字典树的位置
    		char[] arr = prefix.toCharArray();
    		for(int i=0;i<arr.length;i++) { 
    			int index = arr[i] -'a';
    			if(node.son[index] == null) { 
    				return;
    			}
    			node = node.son[index];
    		}
    		
    		//前序遍历字典树
    		preTraverse(node, prefix);
    		
    	}
    	
    	private void preTraverse(TrieNode node, String prefix) { 
    		if(node.wordEnd) { 
    			System.out.println(prefix);
    		}
    		for(TrieNode son : node.son) { 
    			if(son != null) { 
    				preTraverse(son, prefix + son.val);
    			}
    		}
    	}
    	
    	//在字典中查找一个完全匹配的单词
    	public boolean has(String str) { 
    		if(StringUtils.isEmpty(str)) { 
    			return false;
    		}
    		TrieNode node = root;
    		//找到指定前缀在字典树的位置
    		char[] arr = str.toCharArray();
    		for(int i=0;i<arr.length;i++) { 
    			int index = arr[i] -'a';
    			if(node.son[index] == null) { 
    				return false;
    			}
    			node = node.son[index];
    		}
    		//到这里，如果最后的字符是叶子结点，则完全匹配；否则为部分匹配；
    		return node.wordEnd;
    	}
    	
    	//前序遍历字典树
    	public void preTraverse(TrieNode root) { 
    		if(root != null) { 
    			System.out.println(root.val);
    			for(TrieNode son: root.son) { 
    				preTraverse(son);
    			}
    		}
    	}
    	
    	public static void main(String[] args) { 
    		Trie trie = new Trie();
    		String [] arr = new String[]{ "string","str","study","strong","tech", "teach","teacher"};
    		trie.insert("");
    		for(String str: arr) {  
    			trie.insert(str);
    		}
    // trie.preTraverse(trie.root);
    		String prefix ="tea";
    		System.out.println(trie.countPrefix(prefix));
    		trie.hasPrefix(prefix);
    		
    		String word = "teach";
    		System.out.println(trie.has(word));
    		
    	}
    	
    	
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nX2Jv_size_16_color_FFFFFF_t_70]: /images/20220130/b322a4917e404ed5a4613f7c78d45635.png