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

本文主要是介绍数据结构-非线性结构-树形结构：Trie/字典树/前缀树【专门用于处理字符串类数据】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

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);}
}