一篇介绍前缀树及其数组实现

前缀树

• 一、何为前缀树

• 二、前缀树相关操作

• • 1.添加字符串
  • 2.查找字符串

• 第三部分 采用数组模拟的方式构建前缀树

  • 第一部分 首先明确数据结构的设计方案

  • 第二部分 利用数组实现前缀树的存储

  • 第三部分 实现添加字符串的功能模块

  • 第五部分 完整的代码实现方案

  • 四、力扣实战

  • • 1.题目描述
    • 2.简单分析
    • 3.代码实现

一、何为前缀树

prefix tree被称为一个通过公共前缀信息高效地存储字符串集合的数据结构

该图展示了前缀树的一个实例。观察可知，在前缀树中除了根节点外的每一个节点均包含两个属性。

• 字符值
• 以该字符为终点
  ![!在这里插入图片描述\((https://ad.itadn.com/c/weblog/blog-img/images/2025-05-31/kbHq4wAuyzZg7BfR2XhTiQs38l6V.png)

其如何存储字符串？即当我们在搜索'AEP'这一特定字符串时，在对该前缀树进行深度优先遍历过程中会访问到包含该路径的'P'结点。此时我们获取到路径'AEP'并检查该结点的存在标志位（end值），若值为1则表明存在该字符串'AEP'。最后关于这段代码所代表的数据结构的内容也已明确阐述清楚。