数据结构基础19：字典树

三、字典树的构建

Trie树的创建要考虑的是父节点如何保存孩子节点&＃xff0c;主要有链表和数组两种方式&＃xff1a;

&＃xff08;1&＃xff09;使用节点数组&＃xff0c;因为是英文字符&＃xff0c;可以用Node[26]来保存孩子节点(如果是数字我们可以用Node[10])&＃xff0c;这种方式最快&＃xff0c;但是并不是所有节点都会有很多孩子&＃xff0c;所以这种方式浪费的空间太多
&＃xff08;2&＃xff09;用一个链表根据需要动态添加节点。这样我们就可以省下不小的空间&＃xff0c;但是缺点是搜索的时候需要遍历这个链表&＃xff0c;增加了时间复杂度。

给出一组单词&＃xff0c;inn, int, at, age, adv, ant, 我们可以得到下面的Trie&＃xff1a;

可以看出&＃xff1a;
每条边对应一个字母。
每个节点对应一项前缀。叶节点对应最长前缀&＃xff0c;即单词本身。
单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支&＃xff0c;root->i->in。同理&＃xff0c;ate, age, adv, 和ant共享前缀"a"&＃xff0c;所以他们共享从根节点到节点"a"的边。

&＃xff08;1&＃xff09;查询操作

查询操作非常简单。比如要查找int&＃xff0c;顺着路径i -> in -> int就找到了。

&＃xff08;2&＃xff09;如何构建

Trie树的构建也很简单&＃xff0c;无非是逐一把每则单词的每个字母插入Trie。
插入前先看前缀是否存在。如果存在&＃xff0c;就共享&＃xff0c;否则创建对应的节点和边。
比如要插入单词add&＃xff0c;就有下面几步&＃xff1a;
考察前缀"a"&＃xff0c;发现边a已经存在。于是顺着边a走到节点a。
考察剩下的字符串"dd"的前缀"d"&＃xff0c;发现从节点a出发&＃xff0c;已经有边d存在。于是顺着边d走到节点ad
考察最后一个字符"d"&＃xff0c;这下从节点ad出发没有边d了&＃xff0c;于是创建节点ad的子节点add&＃xff0c;并把边ad->add标记为d。

四、Java实现字典树

/** 字典树*/public class Trie18
{private int SIZE&＃61;26;private TrieNode root;//字典树的根Trie18() //初始化字典树{root&＃61;new TrieNode();}private class TrieNode //字典树节点{private int num;//有多少单词通过这个节点,即由根至该节点组成的字符串模式出现的次数private TrieNode[] son;//所有的儿子节点private boolean isEnd;//是不是最后一个节点private char val;//节点的值TrieNode(){num&＃61;1;son&＃61;new TrieNode[SIZE];isEnd&＃61;false;}}//1、建立字典树public void insert(String str) //在字典树中插入一个单词{if(str&＃61;&＃61;null||str.length()&＃61;&＃61;0){return;}TrieNode node&＃61;root;char[]letters&＃61;str.toCharArray();for(int i&＃61;0,len&＃61;str.length(); i}