使用递归实现 trie 树:创建 trie 树:递归创建子节点,直至单词末尾。搜索 trie 树:递归遍历节点,直至单词末尾或节点不存在。
在 PHP 函数中使用递归实现 Trie 树
介绍
Trie 树,也称为前缀树或单词查找树,是一种用于高效存储和查找字符串的树形数据结构。它特别适用于匹配查找,即查找包含特定模式的字符串。本文将向您展示如何在 PHP 函数中使用递归来实现 Trie 树。
立即学习“PHP免费学习笔记(深入)”;
递归算法
递归是一种解决问题的技术,其中函数会调用自身来解决更简单的子问题,直到达到基本情况。对于 Trie 树,我们可以使用递归来创建和搜索树形结构。
创建 Trie 树
创建 Trie 树的过程如下:
function createTrie(array $words): TrieNode
{
$root = new TrieNode(''); // 创建根节点
foreach ($words as $word) {
$node = $root;
for ($i = 0; $i < strlen($word); $i++) {
$letter = $word[$i];
if (!isset($node->children[$letter])) {
$node->children[$letter] = new TrieNode($letter);
}
$node = $node->children[$letter];
}
$node->endOfWord = true;
}
return $root;
}
搜索 Trie 树
搜索 Trie 树的过程如下:
function searchTrie(TrieNode $root, string $word): bool
{
$node = $root;
for ($i = 0; $i < strlen($word); $i++) {
$letter = $word[$i];
if (!isset($node->children[$letter])) {
return false;
}
$node = $node->children[$letter];
}
return $node->endOfWord;
}
实战案例
假设我们有一个以下单词列表:
$words = ['apple', 'banana', 'cherry', 'dog', 'fish'];
我们可以使用 createTrie 函数创建一个 Trie 树,如下所示:
$root = createTrie($words);
然后,我们可以使用 searchTrie 函数搜索单词,如下所示:
if (searchTrie($root, 'apple')) {
echo "找到了 'apple'n";
} else {
echo "未找到 'apple'n";
}
输出:
找到了 'apple'