字典树

字典树(Trie Tree)

三向单词查找树(TST)

字典树又叫单词查找树,三向单词查找树中，每个节点都含有一个字符，三条链接和一个值。这三条链接分别对应着当前字母小于，等于和大于节点字母的所有键。三向单词查找树可以避免R向单词查找树过度的空间消耗.查找和插入时，首先比较键的首字母和根节点的字母，如果键的首字母较小，就选择左链接；如果较大，就选择右链接；如果相等就选择中链接。然后递归的使用相同的算法。查找时，如果遇到一个空链接或者当前键结束时节点的值为空，那么未命中；如果键结束时节点的值非空则查找命中。

package 字典树;

import javafx.concurrent.WorkerStateEvent;

import java.util.ArrayList;
import java.util.List;

/**
 * 三向单词查找树
 */
public class TST {
    Node head=null;
    public List tree=new ArrayList<>();
    class Node{//节点
        char ch;
        Node left,mid,right;//左中右分支
        int val;
      Node(){
          this.val=-1;
      }
      Node(char ch){
          this.ch=ch;
          this.val=-1;
      }
    }

    public void put(String[] words){

        for(int i=0;iroot.ch){
            root.right=put(root.right,word,index,value);
        }else if(indexroot.ch){//字符大于该节点字符  则从该节点左子节点查找
            return get(root.right,word,index);
        }else if(index

package 字典树;

import java.awt.*;
import java.util.ArrayList;
import java.util.List;

public class TrieTree {



    public List tree=new ArrayList<>();



    public  void insert(String word, int index){//往字典树里插单词
        int len=word.length(),cursor=0;//从字典树最开头的那个node节点开始往下存
        for(int i=0;i