当前位置：首页 > PHP

php 字典树实现

2026-02-16 17:08:43PHP

字典树（Trie）基础概念

字典树是一种树形数据结构，用于高效存储和检索字符串集合。核心特点是通过公共前缀共享节点，减少存储空间并提高查询效率。

PHP实现字典树

以下是一个完整的PHP字典树实现，包含插入、搜索和前缀匹配功能：

class TrieNode {
    public $children = [];
    public $isEndOfWord = false;
}

class Trie {
    private $root;

    public function __construct() {
        $this->root = new TrieNode();
    }

    public function insert($word) {
        $node = $this->root;
        $length = strlen($word);

        for ($i = 0; $i < $length; $i++) {
            $char = $word[$i];
            if (!isset($node->children[$char])) {
                $node->children[$char] = new TrieNode();
            }
            $node = $node->children[$char];
        }
        $node->isEndOfWord = true;
    }

    public function search($word) {
        $node = $this->root;
        $length = strlen($word);

        for ($i = 0; $i < $length; $i++) {
            $char = $word[$i];
            if (!isset($node->children[$char])) {
                return false;
            }
            $node = $node->children[$char];
        }
        return $node->isEndOfWord;
    }

    public function startsWith($prefix) {
        $node = $this->root;
        $length = strlen($prefix);

        for ($i = 0; $i < $length; $i++) {
            $char = $prefix[$i];
            if (!isset($node->children[$char])) {
                return false;
            }
            $node = $node->children[$char];
        }
        return true;
    }
}

使用示例

$trie = new Trie();
$trie->insert("apple");
$trie->insert("app");

var_dump($trie->search("apple"));  // true
var_dump($trie->search("app"));    // true
var_dump($trie->search("ap"));     // false
var_dump($trie->startsWith("ap")); // true