本文共 1984 字，大约阅读时间需要 6 分钟。

字典树(前缀树)

数据节点：class Node{
       Node nodes[];    boolean isEnd;    String str;    public  Node()    {
           //该成员用于判断当前节点是否在字典树的末尾        this.isEnd = false;        //该成员用于存储其指向的下一个节点,我们假设只考虑26个小写字母，索引值与字母对应关系如下        //0-'a'  '1'-'b' ... 25-'z'        this.nodes = new Node[26];        //保存当前节点的对应字符串        this.str = null;    }    //添加字符串    public  void add(Node root,String target)//root是根节点，target是目标字符串    {
           Node cur = root;        for(char c : target.toCharArray())        {
               if(cur.nodes[c-'a']==null)                cur.nodes[c-'a'] = new Node();            if(cur.str!=null)//将新的节点的str赋值，但                cur.nodes[c-'a'].str = cur.str+c;            else                cur.nodes[c-'a'].str = ""+c;            cur = cur.nodes[c-'a'];        }        boolean flag = false;        for (Node node : cur.nodes) {
               if(node!=null)                flag = true;//说明cur并不是end        }        if(!flag)            cur.isEnd = true;    }    //查询前缀是target的字符串    public List
   
     SearchPre(Node root,String pre)//root是根节点，pre是前缀字符串    {
           List
    
      list =new ArrayList<>();        Node cur = root;        for(char c : pre.toCharArray())        {
               if(cur.nodes[c-'a']==null)                return list;            cur = cur.nodes[c-'a'];        }        dfs(cur,list);        return  list;    }    //该函数利用深度优先搜索来添加    void dfs(Node root ,List
     
       list)    {
           if(root.isEnd)            list.add((root.str));       for(int i=0;i<26;i++)       {
              if(root.nodes[i]!=null)               dfs(root.nodes[i],list);       }    }}
     
    
   

演示例子:

public class Test1 {
       @Test    public  void Test()    {
           Node root = new Node();        root.add(root,"abc");        root.add(root,"abcd");        root.add(root,"acde");        List
   
     ab = root.SearchPre(root, "abc");        for (String s : ab) {
               System.out.println(s);        }    }}
   

结果：

转载地址：http://hslzi.baihongyu.com/