Trie的递归实现和非递归实现

傷城~ 2022-02-22 01:29 316阅读 0赞

**关于Trie:** 在计算机科学中，Trie，又称字典树、单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。  
![在这里插入图片描述][20190408191927795.png]

import java.util.TreeMap;
    
    /** * @author BestQiang */
    public class Trie { 
        private class Node { 
            public boolean isWord;
            public TreeMap<Character, Node> next;
    
            public Node(boolean isWord) { 
                this.isWord = isWord;
                next = new TreeMap<>();
            }
    
            public Node() { 
                this(false);
            }
        }
    
        private Node root;
        private int size;
    
        public Trie() { 
            root = new Node();
            size = 0;
        }
    
        /** * 获得Trie中储存的单词数量 * * @return */
        public int getSize() { 
            return size;
        }
    
        /** * 向Trie中添加一个新的单词word(非递归写法) * * @param word 传入单词 */
        public void add(String word) { 
            Node cur = root;
            // 取字符串中的字符,在树上进行查询,无则添加,有则下一个
            for (int i = 0; i < word.length(); i++) { 
                char c = word.charAt(i);
                if (cur.next.get(c) == null) { 
                    cur.next.put(c, new Node());
                }
                cur = cur.next.get(c);
            }
            // 此时一个单词已经遍历完成了,如果这个结束节点没有标记为单词,就标记为单词
            if (!cur.isWord) { 
                cur.isWord = true;
                size++;
            }
        }
    
        /** * 向Trie中添加一个新的单词word(递归写法接口) * * @param word */
        public void recursionAdd(String word) { 
            Node cur = root;
            add(root, word, 0);
        }
    
        /** * 递归写法调用方法实现递归添加 * * @param node 传入要进行添加的节点 * @param word 传入要进行添加的单词 */
        public void add(Node node, String word, int index) { 
            // 确定终止条件,这个终止条件在没加index这个参数时,很难确定
            // 此时一个单词已经遍历完成了,如果这个结束节点没有标记为单词,就标记为单词
            if (!node.isWord && index == word.length()) { 
                node.isWord = true;
                size++;
            }
    
            if (word.length() > index) { 
                char addLetter = word.charAt(index);
                // 判断trie的下个节点组中是否有查询的字符,如果没有,就添加
                if (node.next.get(addLetter) == null) { 
                    node.next.put(addLetter, new Node());
                }
                // 基于已经存在的字符进行下个字符的递归查询
                add(node.next.get(addLetter), word, index + 1);
            }
        }
    
        /** * 查询单词word是否在Trie中(非递归写法) * * @param word * @return */
        public boolean contains(String word) { 
            Node cur = root;
            for (int i = 0; i < word.length(); i++) { 
                char c = word.charAt(i);
                if (cur.next.get(c) == null) { 
                    return false;
                } else { 
                    cur = cur.next.get(c);
                }
            }
            return cur.isWord;
        }
    
        /** * 查询单词word中是否在Trie中接口(递归写法) * * @param word * @return */
        public boolean recursionContains(String word) { 
            Node cur = root;
            return contains(root, word, 0);
        }
    
        /** * 查询word中是否在Trie中递归写法 * * @param node * @param word * @param index * @return */
        private boolean contains(Node node, String word, int index) { 
            if (index == word.length()) { 
                return node.isWord;
            }
            char c = word.charAt(index);
            if (node.next.get(c) == null) { 
                return false;
            } else { 
                return contains(node.next.get(c), word, index + 1);
            }
        }
    
        /** * 查询是否在Trie中有单词一prefix为前缀 * * @param prefix * @return */
        public boolean isPrefix(String prefix) { 
            Node cur = root;
            for (int i = 0; i < prefix.length(); i++) { 
                char c = prefix.charAt(i);
                if (cur.next.get(c) == null) { 
                    return false;
                }
                cur = cur.next.get(c);
            }
            return true;
        }
    
        /** * 查询是否在Trie中有单词一prefix为前缀(递归调用) * * @param prefix * @return */
        public boolean recursionIsPrefix(String prefix) { 
            Node node = root;
            return recursionIsPrefix(root, prefix, 0);
        }
    
        /** * 查询是否在Trie中有单词一prefix为前缀(递归实现) * * @return */
        public boolean recursionIsPrefix(Node root, String prefix, int index) { 
            if (prefix.length() == index) { 
                return true;
            }
            char c = prefix.charAt(index);
            if (root.next.get(c) == null) { 
                return false;
            } else { 
                return recursionIsPrefix(root.next.get(c), prefix, ++index);
            }
        }
    }

[20190408191927795.png]: /images/20220222/91742baae7454728915e896ff130b09c.png