();node.data.put("value", key); return node;}if (node.equals == null)node.equals = new Entry(key.charAt(i));// 这里要注意，要获取新的单词填充进去，因为i++了node = node.equals;} else if (diff < 0) {// 没有找到对应的字元，并且下一个左或右节点为NULL，则会一直创建新的节点if (node.left == null)node.left = new Entry(c);node = node.left;} else {if (node.right == null)node.right = new Entry(c);node = node.right;}}}public Entry search(String key) {if (key == null || key.trim().length() == 0)return null;Entry node = root;int count = 0, i = 0;while (true) {if (node == null)return null;int diff = key.charAt(i) - node.splitchar;count++;if (diff == 0) {i++;if (i == key.length()) {node.data.put("count", count);return node;}node = node.equals;} else if (diff < 0) {node = node.left;} else {node = node.right;}}}/*** 三叉Trie树存在3个节点，左右子节点和二叉树类似，以前key都是存放在二叉树的当前节点中，在三叉树中单词是存放在中间子树的 。*/static class Entry {Entry left;Entry right;Entry equals;// 比对成功就放到中间节点char splitchar;// 单词Map data;// 扩展数据域，存放 检索次数，关键码频率等信息 。public Entry(char splitchar) {this.splitchar = splitchar;}public Entry() {}}}三叉搜寻树的套用三叉搜寻树由于其优良的搜寻性能，常被使用于搜寻引擎的自动填充完成（Auto-complete）功能，让用户可以通过“联想”的方式更容易查找到所需要的相关模糊信息
文章插图
百度根据我们输入的“数据”关键字，提示了搜寻量较大的资料库学习，数据分析等搜寻信息，自动完成这种联想功能的核心思想即为三叉搜寻树思想 。对于Web应用程式来说，自动完成（Auto-complete）的繁重处理工作绝大部分要交给伺服器去完成 。很多时候，自动完成（Auto-complete）的备选项数目巨大，不适宜一下子全都下载到客户端 。相反，三叉树搜寻是保存在伺服器上的，客户端把用户已经输入的单词前缀送到伺服器上作查询，然后伺服器根据三叉搜寻树算法获取相应数据列表，最后把候选的数据列表返回给客户端 。
