单词查找树

Trie树高效存储和检索字符串集合Trie树，也称为字典树或者前缀树，是一种非常高效的数据结构，用于存储和检索字符串集合。

它通过利用字符串的公共前缀来减少存储空间，并且可以在O(k)的时间复杂度下查找字符串，其中k是字符串的长度。

本文将介绍Trie树的原理和应用，并展示它在存储和检索字符串集合方面的优势。

一、Trie树的原理Trie树的基本思想是通过将每个字符串拆分为字符节点，并将字符节点以树形结构连接起来，从而形成一个维护字符串集合的数据结构。

它的根节点不包含任何字符，每个子节点代表一个字符，并通过连接方式表示字符串的各个字符之间的关系。

在Trie树中，每个节点都可以包含一个或多个子节点，每个节点的子节点表示在该位置上可能存在的下一个字符。

通过遍历从根节点到叶子节点的路径，我们可以得到一个完整的字符串。

这种结构使得Trie树特别适用于存储大量的字符串，并且可以高效地检索它们。

二、Trie树的构建构建Trie树的过程需要遍历每个字符串，并将它们的字符按照顺序插入到树中。

首先创建一个根节点，然后遍历每个字符串，对于每个字符，我们检查它是否已经是当前节点的子节点。

如果是，则将当前节点更新为该子节点，并继续遍历下一个字符；如果不是，则创建一个新节点，并将其作为当前节点的子节点，然后更新当前节点为新创建的节点，并继续遍历下一个字符。

重复这个过程，直到遍历完所有的字符串。

三、Trie树的应用1. 单词查找由于Trie树可以高效地查找字符串，因此它在单词查找中得到了广泛的应用。

例如，在文本编辑器中，我们可以使用Trie树来实现自动完成功能，根据用户已输入的前缀快速找到匹配的单词。

另外，Trie 树还可以用于拼写检查和单词纠错等应用场景。

2. IP地址查找在网络领域，Trie树也被广泛应用于IP地址查找。

通过将IP地址拆分为多个部分，并构建相应的Trie树，我们可以快速检索到给定IP 地址所对应的地理位置或者网络信息。

数据结构专业英语词汇汇总
- Data structure: 数据结构
- Array: 数组
- Linked list: 链表
- Stack: 栈
- Queue: 队列
- Binary tree: 二叉树
- AVL tree: AVL树 (一种自平衡二叉查找树)
- Red-black tree: 红黑树 (一种自平衡二叉查找树)
- Hash table: 哈希表
- Graph: 图
- Vertex: 顶点
- Edge: 边
- Adjacency list: 邻接表 (一种表示图的数据结构)
- Adjacency matrix: 邻接矩阵 (一种表示图的数据结构) - Heap: 堆
- Binary heap: 二叉堆 (一种特殊的堆数据结构)
- Priority queue: 优先队列 (用堆实现的一种队列)
- Trie: 字典树 (一种用于快速检索的树形数据结构)
- Big O notation: 大O符号 (一种表示算法时间复杂度的记号) - Sorting algorithm: 排序算法
- Searching algorithm: 算法
- Abstract data type (ADT): 抽象数据类型
- Hashing: 哈希函数的计算过程
- Collision: 哈希冲突 (发生在两个不同的键值被映射到相同的哈希桶时)。

树和二叉树的基本知识Jsoi2006春季函授 B层次讲义（3）常州市第一中学林厚从 1/53树和二叉树的基本知识树是一种非线性的数据结构，用它能很好地描述有分支和层次特性的数据集合。

树型结构在现实世界中广泛存在，如把一个家族看作为一棵树，树中的结点为家族成员的姓名及相关信息，树中的关系为父子关系，即父亲是儿子的前驱，儿子是父亲的后继；把一个国家或一个地区的各级行政区划分看作为一棵树，树中的结点为行政区的名称及相关信息，树中的关系为上下级关系，如一个城市包含有若干个区，每个区又包含有若干个街道，每个街道又包含有若干个居委会；把一本书的结构看作是一棵树，树中的结点为书、章、节的名称及相关信息，树中的关系为包含关系。

树在计算机领域中也有广泛应用，如在编译系统中，用树表示源程序的语法结构；在数据库系统中，树型结构是数据库层次模型的基础，也是各种索引和目录的主要组织形式。

在许多算法中，常用树型结构描述问题的求解过程、所有解的状态和求解的对策等。

在树型结构中，二叉树是最常用的结构，它的分支个数确定，又可以为空，具有良好的递归特性，特别适宜于程序设计，因此我们常常将一般树型结构转换成二叉树进行处理。

第一节树一、树的定义一棵树（tree）是由n（n>0）个元素组成的有限集合，其中：1．每个元素称为结点(node)；2．有一个特定的结点，称为根结点或树根（root）；3．除根结点外，其余结点被分成m（m>=0）个互不相交的有限集合T0,T1,T2,……Tm-1，而每一个子集Ti又都是一棵树（称为原树的子树subtree）。

图1图1就是一棵典型的树结构。

从树的定义可以看出：1．树是递归定义的，这就决定了树的操作和应用大都是采用递归思想来解决；2．一棵树中至少有1个结点，这个结点就是根结点，如上图中的结点1；3．只有根结点没有前趋结点，其余每个结点都有唯一的一个前趋结点；4．所有结点都可以有0或多个后继结点；二、树的基本概念下面以图1为例给出树结构中的一些基本概念：1．一个结点的子树个数，称为这个结点的度（degree），如结点1的度为3，结点3的度为0。

·AVL树·红黑树·伸展树·树堆·节点大小平衡树·B+树·B*树·B x树·UB树·2-3树·2-3-4·(a,b)-树·Dancing tree ·H树·基数树·八叉树·k-d树·vp-树·R树·R*树·R+树·X ·线段树·希尔伯特R树·优先R树并且左右两个子树都是一棵平衡二叉树。

构造与调整方法平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树等。

堆（二叉堆）---------------------------------------------------------------------------------------------------------------堆是一种完全二叉树，效率很高，常用的排序算法、Dijkstra算法、Prim算法等都要用堆（优先级队列）优化。

一般的二叉堆不能进行有效查找和堆之间的合并。

（插入，获得及删除最小值）可并堆可以在O(logN)时间内完成两个堆的合并操作的二叉堆。

如左偏堆，二项堆，斐波那契堆。

最优二叉树（哈夫曼树）-----------------------------------------------------------------------------------------------------------------给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

字典树----------------------------------------------------------------------------------------------------------------又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。

树和二叉树作业（一）一、基础知识题1、已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，n m个度为m的结点，问树中有多少个叶子结点？2、由四个结点a、b、c、d组成二叉树，共有多少种不同的结构？3、已知一棵具有n个结点的完全二叉树被顺序地存储于一维数组A中，试编写一个算法，打印出编号为i的结点的双亲和所有孩子。

4、写出对二叉树进行中序遍历的非递归算法。

5、已知一组元素为（46，25，78，62，12，37，70，29），画出按元素排列顺序输入生成的一棵二叉排序树。

6、已知一棵二叉排序树如下图所示，若从中依次删除72、12、49、28结点，试分别画出每删除一个结点后得到的二叉排序树。

7、有七个带权结点a、b、c、d、e、f、g，分别带权3、7、8、2、5、8、4，试以它们为叶子结点构造一棵哈夫曼树（请按照左子树根结点的权小于等于右子树根结点的权的次序构造）。

8、在一份电文中，共用到了五种字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的编码哈夫曼树（请按照左子树根结点的权小于等于右子树根结点的要的次序构造），求出每个字符的哈夫曼编码。

二、编程题1、二叉树的遍历问题【问题描述】输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。

输入：输入文件为tree.in，共两行，第一行一个字符串，表示树的先序遍历；第二行一个字符串，表示树的中序遍历。

树的结点一律用小写字母表示。

输出：输出文件为tree.out，仅一行，表示树的后序遍历序列。

【样例输入】abdecdbeac【样例输出】debca2、假定一棵树采用标准形式存储，试写出以广义表形式输出树的算法。

3、假定树采用标准形式存储，试写出求其深度的算法。

4、FBI树(fbi.pas)【问题描述】我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。

1337：【例3-2】单词查找树时间限制: 1000 ms 内存限制: 65536 KB提交数: 1732 通过数: 910【题⽬描述】在进⾏⽂法分析的时候，通常需要检测⼀个单词是否在我们的单词列表⾥。

为了提⾼查找和定位的速度，通常都画出与单词列表所对应的单词查找树，其特点如下：1．根结点不包含字母，除根结点外每⼀个结点都仅包含⼀个⼤写英⽂字母；2．从根结点到某⼀结点，路径上经过的字母依次连起来所构成的字母序列，称为该结点对应的单词。

单词列表中的每个单词，都是该单词查找树某个结点所对应的单词；3．在满⾜上述条件下，该单词查找树的结点数最少。

4．例如图3-2左边的单词列表就对应于右边的单词查找树。

注意，对⼀个确定的单词列表，请统计对应的单词查找树的结点数（包含根结点）。

【输⼊】为⼀个单词列表，每⼀⾏仅包含⼀个单词和⼀个换⾏/回车符。

每个单词仅由⼤写的英⽂字母组成，长度不超过63个字母。

⽂件总长度不超过32K，⾄少有⼀⾏数据。

【输出】仅包含⼀个整数，该整数为单词列表对应的单词查找树的结点数。

【输⼊样例】AANASPASASCASCIIBASBASIC【输出样例】13【来源】No算法分析⾸先要对建树的过程有⼀个了解。

对于当前被处理的单词和当前树：在根节点的⼦结点中找单词的第⼀位字母，若存在，则进位在该节点的⼦结点中寻找第⼆位…如此下去直到单词结束，即不需要在该树中添加节点；或单词的第n位不能被找到，即将单词的第n位及其后的字母依次加⼊单词查找树中去。

但是，本题只是问节点总数，且有32K⽂件，所以应该考虑能不能不通过建树就直接算出节点总数。

定义⼀个单词相对于另⼀个单词的差：设单词1的长度为L,且与单词2从第N位开始不⼀致，则说单词1相对于单词2的差为L-N+1；，这是描述单词相似程度的量。

可见，将⼀个单词加⼊单词树的时候，须加⼊的节点等于该单词树中已有单词的差的最⼩值。

单词的字典顺序排序后的序列则具有类似的特性，即在⼀个字典顺序序列中，第m个单词相对于第m-1个单词的差必定是它对于前m-1个单词的差中最⼩的。

字典树Trie树的应用场景有哪些字典树（Trie 树）的应用场景有哪些在计算机科学领域，数据结构和算法的选择对于解决各种问题至关重要。

字典树（Trie 树）作为一种高效的数据结构，在众多应用场景中发挥着重要作用。

首先，我们来了解一下什么是字典树。

字典树，又称前缀树，是一种用于快速检索和存储字符串的数据结构。

它的特点是利用字符串的公共前缀来节省存储空间和提高查询效率。

那么，字典树具体在哪些方面有出色的应用呢？在搜索引擎中，字典树被广泛用于快速匹配关键词。

当用户输入搜索词时，搜索引擎需要在海量的网页数据中迅速找到相关的内容。

通过构建字典树，可以将常见的词汇和短语预先存储起来。

这样，在搜索过程中，能够快速判断输入的关键词是否存在，并快速定位相关的网页信息，从而大大提高搜索的响应速度和准确性。

在文本自动完成功能中，字典树也大显身手。

比如我们在输入文字时，输入法常常能够智能地给出可能的后续词汇。

这背后就可能使用了字典树。

输入法软件将常见的词汇和短语构建成字典树，当用户输入部分字符时，通过在字典树中进行查找和匹配，迅速给出可能的完整词汇，为用户提供便捷的输入体验。

字典树在拼写检查工具中也有着不可或缺的地位。

当我们输入一段文本时，拼写检查工具需要快速判断每个单词是否正确。

通过将正确的单词构建成字典树，然后对输入的单词在树中进行查找，如果找不到匹配项，就可以提示可能存在拼写错误。

在 IP 路由查找中，字典树同样能发挥作用。

IP 地址通常具有一定的规律和前缀，通过将 IP 地址段和对应的路由信息构建成字典树，可以实现快速的路由查找和转发，提高网络通信的效率。

在数据压缩方面，字典树也有其独特的价值。

对于重复出现的字符串序列，可以使用字典树来进行编码压缩，减少存储空间的占用。

在生物信息学领域，字典树用于处理基因序列等大量的字符串数据。

例如，在对基因序列进行相似性比较和分类时，字典树能够快速找到相同的基因片段，从而加速研究进程。

字典树（Trie树）实现与应⽤⼀、概述 1、基本概念 字典树，⼜称为单词查找树，Tire数，是⼀种树形结构，它是⼀种哈希树的变种。

2、基本性质根节点不包含字符，除根节点外的每⼀个⼦节点都包含⼀个字符从根节点到某⼀节点。

路径上经过的字符连接起来，就是该节点对应的字符串每个节点的所有⼦节点包含的字符都不相同 3、应⽤场景 典型应⽤是⽤于统计，排序和保存⼤量的字符串(不仅限于字符串)，经常被搜索引擎系统⽤于⽂本词频统计。

4、优点 利⽤字符串的公共前缀来减少查询时间，最⼤限度的减少⽆谓的字符串⽐较，查询效率⽐哈希树⾼。

⼆、构建过程 1、字典树节点定义class TrieNode // 字典树节点{private int num;// 有多少单词通过这个节点,即由根⾄该节点组成的字符串模式出现的次数private TrieNode[] son;// 所有的⼉⼦节点private boolean isEnd;// 是不是最后⼀个节点private char val;// 节点的值TrieNode(){num = 1;son = new TrieNode[SIZE];isEnd = false;}} 2、字典树构造函数Trie() // 初始化字典树{root = new TrieNode();} 3、建⽴字典树// 建⽴字典树public void insert(String str) // 在字典树中插⼊⼀个单词{if (str == null || str.length() == 0){return;}TrieNode node = root;char[] letters = str.toCharArray();//将⽬标单词转换为字符数组for (int i = 0, len = str.length(); i < len; i++){int pos = letters[i] - 'a';if (node.son[pos] == null) //如果当前节点的⼉⼦节点中没有该字符，则构建⼀个TrieNode并复值该字符{node.son[pos] = new TrieNode();node.son[pos].val = letters[i];}else//如果已经存在，则将由根⾄该⼉⼦节点组成的字符串模式出现的次数+1{node.son[pos].num++;}node = node.son[pos];}node.isEnd = true;} 4、在字典树中查找是否完全匹配⼀个指定的字符串// 在字典树中查找⼀个完全匹配的单词.public boolean has(String str){if(str==null||str.length()==0){return false;}TrieNode node=root;char[]letters=str.toCharArray();for(int i=0,len=str.length(); i<len; i++){int pos=letters[i]-'a';if(node.son[pos]!=null){node=node.son[pos];}else{return false;}}//⾛到这⼀步，表明可能完全匹配，也可能部分匹配，如果最后⼀个字符节点为末端节点，则是完全匹配，否则是部分匹配return node.isEnd;} 5、前序遍历字典树 // 前序遍历字典树.public void preTraverse(TrieNode node){if(node!=null){System.out.print(node.val+"-");for(TrieNode child:node.son){preTraverse(child);}}} 6、计算单词前缀的数量 // 计算单词前缀的数量public int countPrefix(String prefix){if(prefix==null||prefix.length()==0){return-1;}TrieNode node=root;char[]letters=prefix.toCharArray();for(int i=0,len=prefix.length(); i<len; i++){int pos=letters[i]-'a';if(node.son[pos]==null){return 0;}elsenode=node.son[pos];}}return node.num;} 完整代码：package com.xj.test;public class Trie{private int SIZE = 26;private TrieNode root;// 字典树的根class TrieNode // 字典树节点{private int num;// 有多少单词通过这个节点,即由根⾄该节点组成的字符串模式出现的次数private TrieNode[] son;// 所有的⼉⼦节点private boolean isEnd;// 是不是最后⼀个节点private char val;// 节点的值TrieNode(){num = 1;son = new TrieNode[SIZE];isEnd = false;}}Trie() // 初始化字典树{root = new TrieNode();}// 建⽴字典树public void insert(String str) // 在字典树中插⼊⼀个单词{if (str == null || str.length() == 0){return;}TrieNode node = root;char[] letters = str.toCharArray();//将⽬标单词转换为字符数组for (int i = 0, len = str.length(); i < len; i++){int pos = letters[i] - 'a';if (node.son[pos] == null) //如果当前节点的⼉⼦节点中没有该字符，则构建⼀个TrieNode并复值该字符 {node.son[pos] = new TrieNode();node.son[pos].val = letters[i];}else//如果已经存在，则将由根⾄该⼉⼦节点组成的字符串模式出现的次数+1{node.son[pos].num++;}node = node.son[pos];}node.isEnd = true;}// 计算单词前缀的数量public int countPrefix(String prefix){if(prefix==null||prefix.length()==0){return-1;}TrieNode node=root;char[]letters=prefix.toCharArray();for(int i=0,len=prefix.length(); i<len; i++){int pos=letters[i]-'a';if(node.son[pos]==null){return 0;}else{node=node.son[pos];}return node.num;}// 打印指定前缀的单词public String hasPrefix(String prefix){if (prefix == null || prefix.length() == 0){return null;}TrieNode node = root;char[] letters = prefix.toCharArray();for (int i = 0, len = prefix.length(); i < len; i++){int pos = letters[i] - 'a';if (node.son[pos] == null){return null;}else{node = node.son[pos];}}preTraverse(node, prefix);return null;}// 遍历经过此节点的单词.public void preTraverse(TrieNode node, String prefix){if (!node.isEnd){for (TrieNode child : node.son){if (child != null){preTraverse(child, prefix + child.val);}}return;}System.out.println(prefix);}// 在字典树中查找⼀个完全匹配的单词.public boolean has(String str){if(str==null||str.length()==0){return false;}TrieNode node=root;char[]letters=str.toCharArray();for(int i=0,len=str.length(); i<len; i++){int pos=letters[i]-'a';if(node.son[pos]!=null){node=node.son[pos];}else{return false;}}//⾛到这⼀步，表明可能完全匹配，可能部分匹配，如果最后⼀个字符节点为末端节点，则是完全匹配，否则是部分匹配return node.isEnd;}// 前序遍历字典树.public void preTraverse(TrieNode node){if(node!=null){System.out.print(node.val+"-");for(TrieNode child:node.son){preTraverse(child);}}}public TrieNode getRoot(){return this.root;}public static void main(String[]args){Trie tree=new Trie();String[]strs= {"banana","band","bee","absolute","acm",};String[]prefix= {"ba","b","band","abc",};for(String str:strs){tree.insert(str);}System.out.println(tree.has("abc"));tree.preTraverse(tree.getRoot());System.out.println();//tree.printAllWords();for(String pre:prefix){int num=tree.countPrefix(pre);System.out.println(pre+"数量:"+num);}}}View Code 执⾏结果截图：三、简单应⽤ 下⾯讲⼀个简单的应⽤，问题是这样的： 现在有⼀个英⽂字典(每个单词都是由⼩写的a-z组成)，单词量很⼤，⽽且还有很多重复的单词。