数据结构-非线性结构-树形结构：Trie/字典树/前缀树【专门用于处理字符串类数据】

Dear 丶 2023-10-04 12:27 28阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70]

## Trie的代码实现 ##

import java.util.TreeMap;
    
    /**
     * Trie树（前缀树、字典树）
     *
     * @author whx
     * @version 2018/9/1
     */
    public class Trie {
        
    
    	/**
    	 * 节点类
    	 *
    	 * @author whx
    	 * @version 2018/9/1
    	 */
    	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;
    	}
    
    	public int getSize(){
        
    		return size;
    	}
    
    	/**
    	 * 添加一个单词
    	 *
    	 * @param word
    	 * @return void
    	 * @author whx
    	 * @version 2018/9/1
    	 */
    	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 ++;
    		}
    	}
    
    	/**
    	 * 递归添加一个单词
    	 *
    	 * @param word
    	 * @return void
    	 * @author whx
    	 * @version 2018/9/1
    	 */
    	public void addRecursion(String word){
        
    		root = addRecursion(root,word);
    	}
    
    	/**
    	 * 在node节点添加一个单词
    	 *
    	 * @param node
    	 * @param word
    	 * @return Trie.Node
    	 * @author whx
    	 * @version 2018/9/1
    	 */
    	private Node addRecursion(Node node, String word){
        
    		if(node == null){
        
    			return null;
    		}
    		if(word.length() > 0){
        
    			if(node.next.get(word.charAt(0)) == null) {
        
    				node.next.put(word.charAt(0), new Node());
    			}
    			node.next.put(word.charAt(0),addRecursion(node.next.get(word.charAt(0)), word.substring(1)));
    			if(word.length() == 1 && !node.next.get(word.charAt(0)).isWord){
        
    				node.next.get(word.charAt(0)).isWord = true;
    				size ++;
    			}
    		}
    		return node;
    	}
    
    	/**
    	 * 是否包含某个单词
    	 *
    	 * @param word
    	 * @return boolean
    	 * @author whx
    	 * @version 2018/9/1
    	 */
    	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;
    			}
    			cur = cur.next.get(c);
    		}
    		return cur.isWord;
    	}
    
    	/**
    	 * 递归查询是否包含某个单词
    	 *
    	 * @param word
    	 * @return boolean
    	 * @author whx
    	 * @version 2018/9/1
    	 */
    	public boolean containsRecurison(String word){
        
    		return containsRecurison(root,word);
    	}
    
    	/**
    	 * 递归查询某个节点中是否包含某个单词
    	 *
    	 * @param node
    	 * @param word
    	 * @return boolean
    	 * @author whx
    	 * @version 2018/9/1
    	 */
    	private boolean containsRecurison(Node node, String word) {
        
    		if(node == null){
        
    			return false;
    		}
    		if(word.length() > 0){
        
    			if(node.next.get(word.charAt(0)) == null) {
        
    				return false;
    			}else if (word.length() == 1 && node.next.get(word.charAt(0)).isWord){
        
    				return true;
    			}
    			return containsRecurison(node.next.get(word.charAt(0)), word.substring(1));
    		}
    		return false;
    	}
    
    	/**
    	 * 是否包含此前缀的单词
    	 *
    	 * @param prefix
    	 * @return boolean
    	 * @author whx
    	 * @version 2018/9/1
    	 */
    	private 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;
    	}
    
    
    	/**
    	 * 递归查询是否包含此前缀的单词
    	 *
    	 * @param word
    	 * @return boolean
    	 * @author whx
    	 * @version 2018/9/1
    	 */
    	public boolean isPrefixRecurison(String word){
        
    		return isPrefixRecurison(root,word);
    	}
    
    	/**
    	 * 递归查询是否包含此前缀的单词
    	 *
    	 * @param node
    	 * @param word
    	 * @return boolean
    	 * @author whx
    	 * @version 2018/9/1
    	 */
    	private boolean isPrefixRecurison(Node node, String word) {
        
    		if(node == null){
        
    			return false;
    		}
    		if(word.length() > 0){
        
    			if(node.next.get(word.charAt(0)) == null) {
        
    				return false;
    			}else if (word.length() == 1){
        
    				return true;
    			}
    			return isPrefixRecurison(node.next.get(word.charAt(0)), word.substring(1));
    		}
    		return false;
    	}
    
    
    
    }

Main.java

/**
     * @author whx
     * @version 2018/9/1
     */
    public class Main {
        
    	public static void main(String[] args) {
        
    		Trie trie = new Trie();
    		trie.add("word");
    		boolean isContains = trie.contains("word");
    		System.out.println(isContains);
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210512101829633.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70