Tir（字典树）入门及实现

2023-10-31 15:10

文章标签 实现入门字典 tir

本文主要是介绍Tir（字典树）入门及实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

它的优点是：
利用字符串的公共前缀来节约存储空间，最大限度的减少无谓的字符串比较，查询效率比哈希表高。

比如说我们想储存3个单词，sky、skyline、skymoon。如果只是单纯的按照以前的字符数组存储的思路来存储的话，那么我们需要定义三个字符串数组。但是如果我们用字典树的话，只需要定义一个树就可以了。在这里我们就可以看到字典树的优势了。

它有三个基本性质:
(1)根节点不包含字符;
(2) 除根节点外每一个节点都只包含一个字符:

(3) 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串，每个节点的所有子节点包含的字符都不相同。

Java实现：

import java.util.Scanner;
public class TireTree {public static void main(String args[]){Scanner in=new Scanner(System.in);int inNum=in.nextInt();for(int i=0;i<inNum;i++){insert(in.next());}int countNum=in.nextInt();for(int j=0;j<countNum;j++){System.out.println(countNum(in.next()));System.out.println(isExist(in.next()));}}public static TireNode root=new TireNode();private static class TireNode{					   //字典树节点private int num;                               //通过这个节点的数量，即单词的个数private TireNode[] son;                        //这个节点的子节点private boolean isEnd;                         //是不是最后一个节点private char value;                            //节点字符的值TireNode(){num=1;son=new TireNode[26];isEnd=false;}}public static void insert(String str){            //把单词插入字典树if(str==null||str.length()==0){return;}TireNode node=root;char[] toChar=str.toCharArray();for(int i=0;i<str.length();i++){int posNum=toChar[i]-'a';if(node.son[posNum]==null){node.son[posNum]=new TireNode();node.son[posNum].value=toChar[i];}else{node.son[posNum].num++;}node=node.son[posNum];}node.isEnd=true;}public static int countNum(String str){          //统计字典树中含有此前缀的个数if(str==null||str.length()==0){return -1;}TireNode node=root;char[] toChar=str.toCharArray();for(int i=0;i<str.length();i++){int posNum=toChar[i]-'a';if(node.son[posNum]==null){return 0;}else{node=node.son[posNum];}}return node.num;}public static boolean isExist(String str){      //判断树中单词是否存在if(str==null||str.length()==0){return false;}TireNode node=root;char[] toChar=str.toCharArray();for(int i=0;i<str.length();i++){int posNum=toChar[i]-'a';if(node.son[posNum]==null){return false;}else{node=node.son[posNum];}}return node.isEnd;}
}

这篇关于Tir（字典树）入门及实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！