java 字典树,Java中的树

　　00-1010工作流程介绍、数据结构初始化、字典树构建、匹配有效词的关键字提示汇总应用

目录

Trie也称为前缀树或字典树，是一种有序树。它是专门用来处理字符串匹配的数据结构，用来解决在一组字符中快速找到一个字符串的问题。相信谷歌的关键词提示功能大家都很熟悉。当我们在输入框中搜索时，我们会拉出一系列候选关键词。

　　上面的关键词提示功能的基本原理就是我们今天说的数据结构：Trie树。

　　我们先来看看轮胎树是什么样子的。以简单的单词匹配为例。首先，它是一个多分支的树形结构。根节点为空字符，树中的节点分为普通节点和结束节点(红色节点如图)。结尾节点就是在前面加上前缀，可以称之为一个词，比如图中的hi和him。

简介

轮胎树和之前的字符串匹配最大的区别是，我们以前是单模字符串，可以检查主字符串中是否有子字符串匹配模式字符串，操作过程也是用模式字符串和主字符串进行比较。轮胎树是多模式串。我们先将模式串预先构建成一棵轮胎树，然后检查主串是否与模式串匹配，这更适合类似于上面关键字提示的前缀匹配。接下来，我们将通过实现一个简单的关键字提示功能来解释轮胎树。

　　00-1010一个值存储当前节点值,一个26位数组存储当前节点的孩子节点。这是一个简单但可能浪费的方法，可以通过使用有序存储和二分搜索法，或者通过使用哈希表和跳转表来优化。一个标志指示当前节点是否可以用作尾节点.

　　/** * Trie树节点*假设我们只做26个小写字母下的匹配*/public static类节点{ //当前节点值private char值；//当前节点的子节点，私有节点child node//在字尾标记当前节点是否为私有布尔isTail公共节点(char value){ this . value=value；} }

　　00-1010初始化一棵只有根节点的轮胎树，根节点值为/0 。

　　节点根；public void init(){ root=new Node( 0 )；root . child Node=new Node[26]；}

　　00-1010将需要添加的模式字符串添加到轮胎树中，遍历当前字符串字符，从轮胎树的根节点开始寻找当前字符。如果字符已经存在，则不需要处理，从这个字符节点开始，看下一个字符是否存在。如果当前节点中不存在轮胎树，则需要插入当前字符。插入最后一个字符时，需要将当前字符节点标记为尾节点。

　　/* * *将当前字符串插入字典树* @ param chars */public void insertstr(char[]chars){//首先判断第一个字符是否已经在字典树中，然后判断第二个字符，依次进行判断。找到第一个不存在的字符，插入子节点Node p=root//指示当前正在处理哪个字符int chIndex=0；while(chIndex chars . length){ while(chIndex chars . length null！=p){ Node[]children=p . child Node；布尔型find=falsefor(节点子级：个子级){ if(null==child){ continue；}如果(孩子。value==chars[CHIndex]){//当前字符已经存在，不需要存储。//从当前节点开始

　　，存储下一个字符 p = child; ++ chIndex; find = true; break; } } if (Boolean.TRUE.equals(find)) { //在孩子中找到了 不用再次存储 break; } //如果把孩子节点都找遍了，还没有找到这个字符，直接将这个字符加入当前节点的孩子节点 Node node = new Node(chars[chIndex]); node.childNode = new Node[26]; children[chars[chIndex] - a] = node; p = node; ++ chIndex; } } //字符串中字符全部进入tire树中后，将最后一个字符所在节点标志为结尾节点 p.isTail = true; }

应用

匹配有效单词

遍历字符串，从根节点出发，查看字符是否存在，只要存在不存在的情况，直接返回false，如果每个字符都存在，判断最后一个字符是否为结尾节点，如果不是，到这里还不是一个有效单词，返回false，否则，返回true。

 /** * 查看当前字符串是否可以在trie中找到 * @param str 主串 * @return true/false */ public boolean isMatch(String str) { //从root开始进行匹配，只要有一个找不到即为匹配失败 char[] chars = str.toCharArray(); int chIndex = 0; Node p = root; while (null != p) { Node[] children = p.childNode; boolean flag = false; for (Node child : children) { if (null == child) {continue;} if (child.value == chars[chIndex]) { flag = true; p = child; ++ chIndex; //当比较最后一个字符的时候，这个字符需要是结尾字符才能完全匹配 if (chIndex == chars.length && p.isTail) { return true; } break; } } if (Boolean.FALSE.equals(flag)) { return false; } } return false; }

测试样例

public static void main(String[] args) { //he, him, lot, a //初始化Tire树 Trie trie = new Trie(); trie.init(); //构建Tire树，只有以下单词才是有效单词 trie.insertStr("he".toCharArray()); trie.insertStr("him".toCharArray()); trie.insertStr("lot".toCharArray()); trie.insertStr("a".toCharArray()); //匹配字符串是否为有效单词 System.out.println(trie.isMatch("lot")); System.out.println(trie.isMatch("lit")); }

运行结果

关键词提示

根据输入的关键词前缀，匹配所有可能出现的关键词。首先遍历字符串，从节点出发，只要有一个找不到，直接返回null，直至找到最后一个字符对应的节点，从该节点出发找到所有尾节点。

 /** * 找到所有以str为前缀的字符串 * @param str 前缀串 * @return 所有以str为前缀的单词 */ public List<String> findStrPrefix(String str) { //根据str首先找到str最后一个字符，然后从这个字符出发，找到所有字符串 List<String> result = new ArrayList<>(); char[] chars = str.toCharArray(); //分成两步走 //1。找到str最后一个自字符在字典树中的node //2。从该node出发，找到所有的结尾node，即为以str为前缀的字符串 int chIndex = 0; Node p = root; while (null != p && chIndex < chars.length) { Node[] children = p.childNode; boolean flag = false; for (Node child : children) { if (null == child) {continue;} if (child.value == chars[chIndex]) { //已经找到 p = child; flag = true; ++ chIndex; break; } } //如果没有找到，直接返回空 if (Boolean.FALSE.equals(flag)) { return null; } } //找到了最后一个节点 //深度优先遍历，查找所有尾节点 this.dfs(p, new StringBuilder(str), result); return result; } public void dfs(Node p, StringBuilder str, List<String> result) { Node[] children = p.childNode; for (Node child : children) { if (null == child) { continue; } str.append(child.value); if (child.isTail) { result.add(str.toString()); } //再递归查当前节点的孩子节点 dfs(child, str, result); //需要将刚刚set进去的节点删除，否则影响当前节点的下一个孩子节点 //举个例子，h的孩子节点有e，i，当e放进去之后不拿出来，在遍历到i的时候，就会形成hei str.setLength(str.length() - 1); } }

测试样例

public static void main(String[] args) { //he, him, lot, a //初始化Tire树 Trie trie = new Trie(); trie.init(); //构建Tire树，只有以下单词才是有效单词 trie.insertStr("he".toCharArray()); trie.insertStr("him".toCharArray()); trie.insertStr("lot".toCharArray()); trie.insertStr("a".toCharArray()); //匹配字符串是否为有效单词 List<String> strings = trie.findStrPrefix("h"); }

运行结果

总结

到这里Trie树就讲完了，主要就是聚合前缀，通过树的特性，按照链路进行访问，同时标志尾节点，标志到当前节点是一个完整的字符串。

　　以上就是详解Java中字典树(Trie树)的图解与实现的详细内容，更多关于Java字典树的资料请关注盛行IT其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。