TrieTree的代码实现，TrieTree代码实现,字典树,支持增删查找以及
分享于 点击 11973 次 点评：64
TrieTree的代码实现，TrieTree代码实现,字典树,支持增删查找以及
字典树,支持增删查找以及树结构的优化
这里对标准字典树进行改造,将节点数据不存在的无分支路径进行垂直合并
package com.nianien.core.collection;import java.util.ArrayList;import java.util.List;/** * 字典树,支持增删查找以及树结构的优化<br> * 这里对标准字典树进行改造,将节点数据不存在的无分支路径进行垂直合并 * */public class TrieTree { /** * 字典树节点 * * */ public static class TrieNode { /** * 当前节点数据 */ private String value; /** * 第一个孩子节点 */ private TrieNode firstChild; /** * 下一个兄弟节点 */ private TrieNode nextBrother; /** * 节点数据存在标志 */ private boolean exists; /** * 构造方法 * * @param value * 节点数据 */ public TrieNode(String value) { this(value, false); } /** * 构造方法 * * @param value * 节点数据 * @param exists * 节点数据是否存在 */ public TrieNode(String value, boolean exists) { this.value = value; this.exists = exists; } /** * 节点数据 * * @return */ public String value() { return value; } /** * 设置节点数据 * * @param value */ public void value(String value) { this.value = value; } /** * 节点数据是否存在 * * @return */ public boolean exists() { return exists; } /** * 指定节点数据是否存在 * * @param exists */ public void exists(boolean exists) { this.exists = exists; } /** * 第一个孩子节点 * * @return */ public TrieNode firstChild() { return firstChild; } /** * 指定第一个孩子节点 * * @param node */ public void firstChild(TrieNode node) { this.firstChild = node; } /** * 下一个兄弟节点 * * @return */ public TrieNode nextBrother() { return nextBrother; } /** * 指定下一个兄弟节点 * * @return */ public void nextBrother(TrieNode node) { this.nextBrother = node; } /** * 显示节点数据内容 */ public String toString() { return value + "[" + exists + "]"; } } /** * 字典树节点处理接口,常用于字典树的遍历 * * * */ public static interface TrieNodeHandler { /** * 处理字典树的节点 * * @param node */ void doHandle(TrieNode node); } /** * 根节点,不存储数据 */ private TrieNode root = new TrieNode("`"); /** * 查找数据 * * @param data * @return */ public boolean find(String data) { TrieNode firstChild = root.firstChild(); if (firstChild == null) return false; TrieNode node = find(firstChild, data); return node != null ? node.exists() : false; } /** * 插入数据 * * @param data * @return */ public void insert(String data) { TrieNode firstChild = root.firstChild(); if (firstChild == null) { root.firstChild(new TrieNode(data, true)); } else { insert(firstChild, data); } } /** * 删除数据 * * @param node * @param data */ public void delete(String data) { TrieNode firstChild = root.firstChild(); if (firstChild == null) return; TrieNode node = find(firstChild, data); if (node != null) node.exists(false); } /** * 推荐以指定数据为前缀的数据 * * @param data * @return */ public List<String> suggest(String data) { List<String> list = new ArrayList<String>(); TrieNode firstChild = root.firstChild(); if (firstChild != null) { TrieNode node = suggest(firstChild, data); if (node != null) pathes(node, list, new StringBuilder(data)); } return list; } /** * 字典树结构优化 */ public void optimize() { // 根节点不能被合并 TrieNode firstChild = root.firstChild(); if (firstChild != null) { this.optimize(root); } } /** * 层次遍历访问节点 * * @param handler */ public void visit(TrieNodeHandler handler) { TrieNode child = root.firstChild(); if (child == null) return; List<TrieNode> list = new ArrayList<TrieNode>(); list.add(child); while (!list.isEmpty()) { TrieNode node = list.remove(0); handler.doHandle(node); if (node.firstChild() != null) { list.add(node.firstChild()); } TrieNode brother = node.nextBrother(); while (brother != null) { handler.doHandle(brother); if (brother.firstChild() != null) { list.add(brother.firstChild()); } brother = brother.nextBrother(); } } } /** * 字典树的图形显示,用于调试分析<br> * 当节点较多时,调用该方法可能会造成堆栈溢出错误 */ public String dispaly() { List<TrieNode> list = new ArrayList<TrieNode>(); StringBuilder sb = new StringBuilder(); list.add(root); TrieNode tail = list.get(0); while (!list.isEmpty()) { TrieNode node = list.remove(0); if (node == null) { sb.append("-|"); continue; } sb.append(node); list.add(node.firstChild()); TrieNode brother = node.nextBrother(); while (brother != null) { sb.append("→").append(brother); list.add(brother.firstChild()); brother = brother.nextBrother(); } if (node != tail) { sb.append("|"); continue; } while (!list.isEmpty()) { tail = list.get(list.size() - 1); if (tail != null) break; list.remove(list.size() - 1); } if (!list.isEmpty()) { sb.append("\\n↓\\n"); } } return sb.toString(); } /** * 从指定节点开始插入数据 * * @param node * @param data * @return */ private void insert(TrieNode node, String data) { String value = node.value(); if (data.equals(value)) { // 插入数据存在 node.exists(true); return; } int index = mixed(data, value); if (index == 0) {// 没有公共开始部分,将数据插入兄弟节点 TrieNode brother = node.nextBrother(); if (brother != null) { insert(brother, data); } else { node.nextBrother(new TrieNode(data, true)); } } else { if (value.length() > index) {// 节点数据多于公共部分,则节点进行纵向分裂 // 将多余部分插入孩子节点 TrieNode temp = new TrieNode(value.substring(index), node.exists()); TrieNode child = node.firstChild(); // 将原节点的孩子节点变为孙子节点 if (child != null) { temp.firstChild(child); } // 原节点的数据更新为公共部分 node.value(value.substring(0, index)); // 公共部分是否为插入数据 node.exists(node.value().equals(data)); node.firstChild(temp); } if (data.length() > index) {// 插入数据多于公共部分,则多余部分插入孩子节点 TrieNode firstChild = node.firstChild(); if (firstChild == null) {// 如果没有孩子节点,则创建孩子节点 node.firstChild(new TrieNode(data.substring(index), true)); } else {// 否则直接插入孩子节点 insert(firstChild, data.substring(index)); } } } } /** * 从指定节点开始查找数据 * * @param node * @param data */ private TrieNode find(TrieNode node, String data) { String value = node.value(); if (data.equals(value)) { // 查询数据存在 return node; } int index = mixed(data, value); if (index == 0) {// 不存在公共部分,查询兄弟节点 TrieNode brother = node.nextBrother(); return brother != null ? find(brother, data) : null; } TrieNode firstChild = node.firstChild(); // 节点数据为查询数据的前缀,则继续查询子节点 return data.startsWith(value) && firstChild != null ? find(firstChild, data.substring(value.length())) : null; } /** * 从指定节点开始优化字典树结构,节点数据不存在的无分支路径进行垂直合并 * * @param node */ private void optimize(TrieNode node) { TrieNode child = node.firstChild(); if (child == null) return; // 只有一个孩子节点,且父子节点数据都不存在 if (!node.exists() && !child.exists() && child.nextBrother() == null) { // 合并内容 node.value(node.value() + child.value()); // 孙子节点变为孩子节点 node.firstChild(child.firstChild()); optimize(node); } else { optimize(node.firstChild()); } } /** * 两个字符串公共开始部分的长度 * * @param str1 * @param str2 * @return */ private static int mixed(String str1, String str2) { int len = str1.length() < str2.length() ? str1.length() : str2.length(); int index = -1; for (int i = 0; i < len; i++) { if (str1.charAt(i) != str2.charAt(i)) break; index = i; } return index + 1; } /** * 查询以指定字符串为前缀且相似度最大的字符串<br> * 该方法返回一个虚拟节点,节点的数据为不包含指定数据后的剩余部分<br> * 该节点的孩子节点为查找到的节点的孩子节点 * * @param node * @param data * @return */ private TrieNode suggest(TrieNode node, String data) { String value = node.value(); if (value.startsWith(data)) { TrieNode temp = new TrieNode(value.substring(data.length())); temp.firstChild(node.firstChild); temp.exists(node.exists() && !temp.value().isEmpty()); return temp; } int index = mixed(data, value); if (index == 0) {// 不存在公共部分,查询兄弟节点 TrieNode brother = node.nextBrother(); return brother != null ? suggest(brother, data) : null; } TrieNode firstChild = node.firstChild(); // 节点数据为查询数据的前缀,则继续查询子节点 return data.startsWith(value) && firstChild != null ? suggest(firstChild, data.substring(value.length())) : null; } /** * 获取指定节点存在的全部子路径 * * @param node * @param list * @param sb */ private void pathes(TrieNode node, List<String> list, StringBuilder sb) { sb.append(node.value()); // 节点存在,加入路径 if (node.exists()) list.add(sb.toString()); if (node.firstChild() != null) { pathes(node.firstChild(), list, sb); } // 回退该节点,查找兄弟节点 sb.delete(sb.length() - node.value().length(), sb.length()); if (node.nextBrother() != null) { pathes(node.nextBrother(), list, sb); } }}//该片段来自于http://byrx.net
用户点评