C++实现Trie树 |21xrx.com

C++实现Trie树

2023-07-10 01:26:54 深夜i -- --

C++ Trie树数据结构字符串匹配前缀搜索

Trie树（又称字典树）是一种树形结构，用于存储关联数组，其中键通常是字符串。它的基本思想是把每个键看作一个字符序列，通过对各个字符在树中不断分支的方式进行存储和索引。通过这种方式，Trie树可以实现高效的单词查找和插入。

在C++中，可以通过使用指针或者数组等方式来实现Trie树。本篇文章将介绍一种通过数组实现Trie树的方法。

定义：

首先，需要定义一个结构体，表示Trie树的节点。每个节点包含一个bool值，表示从根节点到当前节点所表示的字符串是否是一个单词的结束位置；以及一个指向子节点的指针数组，数组长度为26（因为字母表有26个字母）。

struct TrieNode {

bool isEnd;//标识从根节点到该节点是否构成一个字符串

TrieNode *child[26];

TrieNode() {

isEnd = false;

memset(child, NULL, sizeof(child));//初始化所有子节点指针为空

}

};

插入：

然后，就可以通过数组实现Trie树的插入操作。首先，需要对每个单词进行遍历，将其转化为一个个字符。在遍历的过程中，依次向下搜索并在每个节点上创建一个子节点，直到遍历完单词的所有字符。最后，在单词的最后一个字符所在的节点上标记isEnd为true，表示该节点以上构成的字符串是一个单词。

void insert(TrieNode *root, string word) {

TrieNode *node = root;

for (char c : word) {

int index = c - 'a';

if (!node->child[index]) {

node->child[index] = new TrieNode();

}

node = node->child[index];

}

node->isEnd = true;

}

查询：

查询操作也很简单，只需要按照待查询单词的字符顺序向下遍历Trie树，同时判断节点上的isEnd标志位即可。

bool search(TrieNode *root, string word) {

TrieNode *node = root;

for (char c : word) {

int index = c - 'a';

if (!node->child[index])

return false;

node = node->child[index];

}

return node->isEnd;

}

如果想要查询某个前缀是否存在于Trie树中，也很容易，只需要在查询的过程中，一旦出现isEnd为true的节点，就将其加入到结果集合中即可。

void searchPrefix(TrieNode *root, string prefix, vector &result) {

TrieNode *node = root;

for (char c : prefix) {

int index = c - 'a';

if (!node->child[index])

return;

node = node->child[index];

}

traverseTrie(node, prefix, result);

}

void traverseTrie(TrieNode *node, string prefix, vector &result) {

if (node->isEnd) {

result.push_back(prefix);

}

for (int i = 0; i < 26; ++i) {

if (node->child[i]) {

traverseTrie(node->child[i], prefix + char('a' + i), result);

}

总结：

通过使用数组实现Trie树的插入、查询等操作，可以实现高效的单词处理。在实际应用中，Trie树常常被用来实现字符串的自动补全、拼写检查、单词频率统计等功能。

上一篇: idea打包java可执行jar包

下一篇: C++编程实现图形用户界面

评论区

()

相似文章