Python中的Trie实现
Tries是我们用来存储字符串的数据结构。它们允许我们以最有效的方式搜索文本字符串。
本文将讨论我们如何在Python中实现一个Trie。
Python中的Trie数据结构
你可以把Trie看作一棵树，每个节点由一个字符组成。每个节点都有一个或多个子节点，这取决于它是一个字符串的内部字符还是最后一个字符。
代表字符串最后一个字符的节点没有子节点，它标志着字符串的结束。我们将在类的定义中加入一个标志变量来标记字符串的结束。
如果我们存储只由小写英文字母组成的字符串，那么Trie中的每个节点最多可以有26个子节点。如果字符串有字母以外的字符，那么某个节点的最大子节点数就等于不同字符的总数。
你可以在 Python 中定义一个 Node 类来实现 Trie 的一个节点，如下面的例子所示。
class Node:
def __init__(self):
self.children = []
for i in range(26):
self.children.append(None)
self.isLeafNode = False
在这里，我们创建了一个名为children 的列表，用来定义一个字符是否是当前节点的子节点。由于我们考虑了26个字符，我们用26个None 的值初始化了这个列表。
如果一个字符不是当前节点的孩子，它的位置将包含值None 。否则，与该字符相对应的位置将存储该字符的节点。
在向children 列表中插入字符时，我们按照字符的字母顺序存储子节点。换句话说，字母a 的子节点将被存储在索引0，字母b 的子节点将被存储在索引1，等等。
在创建一个节点之后，我们需要创建一个类来定义一个Trie。在这个类中，我们将定义一个空节点，其列表中包含26个None ，代表英文字母的26个字符。
我们将称这个空节点为root 节点。
class Trie:
def __init__(self):
self.root = Node()
每当一个字符串被插入到Trie中，代表该字符串第一个字符的节点就会成为root 节点的子节点。请注意，我们将把包含字符串下一个字符的节点按照其位置作为列表元素来存储。
在创建了root 节点后，我们将在下面的章节中实现在三联体中插入一个词和在三联体中搜索一个词的方法。
在Python中的Trie中插入一个字符串
为了在Trie中插入一个字符，我们将首先找到要插入的字符串的长度。之后，我们将从三联体的root 节点开始爬行三联体。
以下是向Trie中插入字符串的算法：
- 计算要插入到Trie中的字符串的长度。将其存储在一个变量
strLen。 - 取一个变量
crawler，并将三联体的root节点分配给该变量。 - 如果你在
n，检查字符串的第n个字符是否存在于Trie中的那一层。如果是，将其在children列表中的位置存储到变量position；然后，转到5– 否则，转到4。 - 为Trie创建一个新的节点，并将其分配给
crawler的索引position。 - 将
crawler移到下一级。 - 检查我们是否已经到达了字符串的末端；如果是，转到
7– 否则，转到3。 - 将当前节点标记为字符串的结尾。
在讨论了这个算法之后，现在让我们在Python中实现这个算法，将一个字符串插入到一个Trie中。
def insert(self, input_str):
strLen = len(input_str)
crawler = self.root
for level in range(strLen):
character = input_str[level] [position] [position] [position] 在Python中搜索三联体中的一个元素
为了搜索一个字符串是否存在于Trie中，我们将使用以下算法。
- 初始化一个变量
crawler，并将Trie的root节点分配给该变量。 - 计算Trie中要搜索的字符串的长度。将其存储在变量
strLen。 - 在
n，查找字符串的第n个字符是否存在于children列表中。如果是，转到4；否则，返回False。 - 检查当前节点是否是一个叶子节点。如果是，返回
True；否则，递增n并转到3。
我们已经定义了在Trie中搜索一个字符串的算法。让我们在Python中实现它。
def search(self, input_str):
crawler = self.root
strLen = len(input_str)
for level in range(strLen):
character = input_str[level] [position] [position] 在Python中实现Trie
由于我们已经在Python中实现了搜索和插入操作的方法，让我们用一些操作实例来执行代码。
class Node:
def __init__(self):
self.children = []
for i in range(26):
self.children.append(None)
self.isLeafNode = False
class Trie:
def __init__(self):
self.root = Node()
def insert(self, input_str):
strLen = len(input_str)
crawler = self.roothave
for level in range(strLen):
character = input_str[level] [position] [position] [position] [level] [position] [position] 输出：
Inserting the string: aditya
Inserting the string: delftstack
Inserting the string: aaditya
aditya is present in the trie: True
delftstack is present in the trie: True
python is present in the trie: False
我们首先在Python中使用本例中讨论的算法实现了一个Trie。之后，我们在Trie中插入了三个字符串：aditya,delftstack, 和aaditya 。
然后，我们对Trie进行搜索操作，以检查字符串aditya,delftstack, 和python 是否存在于Trie中。你可以观察例子中的输出。
