字典树（Trie Tree）

终于要开始更新我的ACM学习之路了，不过没想到却是因为一次Java大作业，有趣，%yuan老师。

字典树是一种很简单的树形结构，主要用来进行词频统计，在算法竞赛中有时也会碰到。

字典树的基本思路是，通过树这种数据结构，读入文本的时候同步建立树，每个节点通过一个指针数组保存了子树的指针，指针数组的下标存储了单词的信息，将每个单词的公共前缀都保存在同一条路径上，尽可能的节省了空间。同时因为一颗平衡二叉树的查找效率很高，因此字典树的查找效率很高，为O(logN)。

不过这种结构应该还可以用左孩子右兄弟表示法来进一步节省空间，只不过这样可能需要再多定义一个char来专门存储保存的字符。

好，既然大家都觉得这个思路那是相~~~~当的简单，那么让我们来动手实践一下吧~~

一下实现是基于java实现，因此没有释放内存的delete函数。

节点的数据结构定义如下：

class Node{
    private int num;
    private Node[] next;
    private boolean leaf;

    public Node() {
        this.num=0;
        this.next=new Node[26];
        this.leaf=true;
    }

    public int getNum() {return num;}

    public void setNum(int num) {this.num = num;}

    public Node[] getNext() {  return next;}

    public boolean isLeaf() {return leaf;}

    public void setLeaf(boolean leaf) {this.leaf = leaf;}

}

说明一下，这里的Next数组就是我们的指针数组，这里它有两个作用，第一，记录子树的位置，第二，通过下标运算，可以得知存储的字母。这里一定要记住作用二呦，这样我们就不需要再定义一个专门的char来保存字母了。当然，我呢是个大懒蛋，所以为了能少写点代码，这里还定义一个boolean类型的leaf，这样我就不用每次通过判断节点的Next数组是不是全为null来判断是不是 leaf了，哈哈哈哈。

构建树并没有必要用递归，代码如下：

 1 public void creTree() throws IOException{
 2         //initialize
 3         this.head=createNode();
 4         this.cnt=0;
 5         //create tree
 6         String s=this.read();
 7         while(s.compareTo("\\$")!=0){
 8             //处理每个单词
 9             char []words=s.toLowerCase().toCharArray();
10             Node p=head;
11             for(int i=0;i<words.length;i++) {
12                 if(p.getNext()[words[i]-'a']==null) {
13                     p.getNext()[words[i]-'a'] =createNode();
14                     p.setLeaf(false);
15                     this.cnt++;
16                 }
17                 p = p.getNext()[words[i] - 'a'];
18             }
19             p.setNum(p.getNum()+1);
20             //读取下一个单词
21             s = this.read();
22         }
23         this.res = new String[cnt];
24         this.num = new int[cnt];
25     }

在通常字典树的应用范围中，常常是查找的应用，即只需要按照给定的字符串，判断是否有，或者有几个，因此也不需要使用递归，只需要将建树的部分12行以后的代码稍加修改，就可以了，因此就不赘述了，相信以各位的智商一定是毫无问题的。但是稍稍复杂一点的是，打印树中所有的单词，并输出出现的个数，这样就需要涉及到深度优先遍历(DFS)，在处理需要输出的字符串上也稍复杂了一点，这里贴出我的解决方法，欢迎高端玩家批评指正呦~

首先在函数外定义一个StringBuffer，为什么要在函数外呢，因为遍历函数需要递归，当然不能在函数内啦，嘻嘻~~~

1  private StringBuffer sbf = new StringBuffer();

然后就是DFS了

其中String[] res和 int[]num 分别存储字符串本身以及出现的次数

 1 public void findTree(Node h) {
 2         if(h.isLeaf())return ;
 3         Node p = h;
 4         for(int i=0;i<p.getNext().length;i++) {
 5             if(p.getNext()[i]==null)continue;
 6             sbf.append((char) ((int) 'a' + i));
 7             if(p.getNext()[i].getNum()>0) {
 8                 this.res[str]=sbf.toString();
 9                 this.num[str++]=p.getNext()[i].getNum();
10             }
11             this.findTree(p.getNext()[i]);
12             sbf.deleteCharAt(sbf.length() - 1);
13         }
14     }

这样，遍历就可以完成啦~~后面有时间我会继续更新一些ACM的字典树的题上来，就这样吧~

============================================我是渣渣专用的分割线==========================================

最近在百度的编程题目中遇到了需要用到字典树的题目，原题目大概是说，给你三个操作，insert，delete，search，每个操作后面都给你一个待操作的字符串，输出为：当遇到search时，进行查找，找到输出Yes，反之输出NO。

这个题很水对吧，我目前想到两种做法，一种是用C++的STL中的map直接对出现的次数做映射，这样代码简洁，并且插入和查找的效率都是O（1），

第二种就是字典树，这个方法当然代码量大一些，不过也能做，但是在字典树在删除的时候引起了我的思考：

　　如果我将这个词所占用的内存直接释放，那么会出现这样的情况：比如app和apple两个词，如果我删除app的操作是释放内存，那么我就无法找到apple。

　　因此，我只能在通过修改标记的方法进行删除，这样和map实现的删除原理上就一致了。

综上：用map实现在时间效率上不输于Trie Tree，空间复杂度只要在比赛要求的范围内，就可以起到用很少的代码完成相同的问题的目标，性价比比较高

字典树（Trie Tree）

推荐阅读