PHP 函数中如何使用递归来实现 Trie 树？-php教程-PHP中文网

PHP 函数中如何使用递归来实现 Trie 树？

WBOY

发布： 2024-09-02 21:21:03

原创

511人浏览过

使用递归实现 trie 树：创建 trie 树：递归创建子节点，直至单词末尾。搜索 trie 树：递归遍历节点，直至单词末尾或节点不存在。

PHP 函数中如何使用递归来实现 Trie 树？

在 PHP 函数中使用递归实现 Trie 树

介绍

Trie 树，也称为前缀树或单词查找树，是一种用于高效存储和查找字符串的树形数据结构。它特别适用于匹配查找，即查找包含特定模式的字符串。本文将向您展示如何在 PHP 函数中使用递归来实现 Trie 树。

立即学习“PHP免费学习笔记（深入）”；

递归算法

递归是一种解决问题的技术，其中函数会调用自身来解决更简单的子问题，直到达到基本情况。对于 Trie 树，我们可以使用递归来创建和搜索树形结构。

创建 Trie 树

创建 Trie 树的过程如下：

来画数字人直播

来画数字人自动化直播，无需请真人主播，即可实现24小时直播，无缝衔接各大直播平台。

查看详情

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'

登录后复制

以上就是PHP 函数中如何使用递归来实现 Trie 树？的详细内容，更多请关注php中文网其它相关文章！

大家都在看：

PHP递归函数怎么用于缓存管理_PHP递归函数在缓存结构中的应用实例 PHP递归函数如何记录路径_PHP在递归过程中跟踪当前路径的技巧 PHP递归和迭代哪个快_PHP递归与迭代执行效率对比评测 PHP递归函数如何实现递归构建_PHP递归函数构建复杂数据结构的代码示例 PHP递归实现文件搜索_PHP通过递归查找指定目录下文件的方法