Java 与 字典树（前缀树）

字典树

字典树又称前缀树 典型应用：统计、排序(?)和保存大量的字符串（不限于字符串），常被用于搜索引擎中：文本词频统计。 图示：

Java实现

package com;

import java.util.Arrays;

public class Tris {
          
   
   Tris[] child;
   boolean isEnd;

   public Tris(){
          
   
       this.child = new Tris[26];
       this.isEnd = false;
   }

   @Override
   public String toString() {
          
   
       return "Tris{" +
               "child=" + Arrays.toString(child) +
               };
   }


   public static void main(String[] args){
          
   
       Tris tris = new Tris();
       tris.insert("beat");
       System.out.println(tris.toString());
       boolean flag = tris.search("app");
       System.out.println(flag);
   }
   public void insert(String word){
          
   
       /**
        * 要插入的单词
        */
       Tris node = this;                   // Java对象
       for (int i=0;i<word.length();i++){
          
   
           char ch = word.charAt(i);
           int index = ch - a;
           if (node.child[index] == null){
          
   
               node.child[index] = new Tris();
           }
           node = node.child[index];
       }
       node.isEnd = true;
   }
   public boolean search(String word){
          
   
       /**
        * 要查找的单词
        */
       Tris node = this;
       for (int i=0;i<word.length();i++){
          
   
//            System.out.println(i);
           char ch = word.charAt(i);
           int index = ch - a;
           if (node.child[index] == null){
          
   
               return false;
           }
           node = node.child[index];
       }
       return node.isEnd;
   }

}

字典树的具体存储

如代码所示，存入：beat 有图示可以看出，字典树的基本单位是：大小为26的数组，对应26个英文字母（小写）。对于不存在的字符，该位置置为NULL，反之，则new一个Trie对象(代码中写成了Tris，读者留心)，置于该位置。