字典树 python
时间: 2023-10-28 16:00:18 浏览: 48
字典树(Trie)是一种用于高效存储和搜索字符串集合的数据结构。Python 中可以使用以下代码实现一个简单的字典树:
```python
class TrieNode:
def __init__(self):
self.children = {} # 子节点的映射表
self.is_word = False # 标记当前节点是否为单词的结尾
class Trie:
def __init__(self):
self.root = TrieNode() # 根节点
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_word
def startsWith(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
```
使用示例:
```python
trie = Trie()
trie.insert("apple")
print(trie.search("apple")) # 输出 True
print(trie.search("app")) # 输出 False
print(trie.startsWith("app")) # 输出 True
trie.insert("app")
print(trie.search("app")) # 输出 True
```
这是一个基本的字典树实现,可以用于存储字符串集合,并进行搜索和前缀匹配操作。如果有更复杂的需求,还可以对该实现进行扩展。