1. 前缀树简介

前缀树，又叫 Trie 树，是一种多叉树的数据结构，其中每个节点表示一个字符。它的特点是，从根节点到某一个节点，路径上经过的字符连接起来，就构成了一个字符串，即前缀。前缀树可以解决一些字符串相关的问题，比如查找，插入，删除等操作。

2. php 实现前缀树

使用 php 实现前缀树，首先要实现一个前缀树节点类，用来表示每个节点：

123456789101112
class TrieNode {
    public $children;
    public $isEnd;
    public $value;
 
    public function __construct($value) {
        $this->value = $value;
        $this->children = [];
        $this->isEnd = false;
    }
}
PHP

3. 如何使用前缀树实现关键词查找

使用前缀树实现关键字查找，首先要构建一棵前缀树，将所有的关键字插入到前缀树中。插入的过程也就是构建前缀树的过程：

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253
class Trie {
    private $root;
 
    public function __construct() {
        $this->root = new TrieNode(null);
    }
 
    public function insert($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $char = $word[$i];
            if (!isset($node->children[$char])) {
                $newNode = new TrieNode($char);
                $node->children[$char] = $newNode;
            }
            $node = $node->children[$char];
        }
        $node->isEnd = true;
    }
 
    public function search($word) {
        $node = $this->root;
        for ($i = 0; $i < strlen($word); $i++) {
            $char = $word[$i];
            if (!isset($node->children[$char])) {
                return false;
            }
            $node = $node->children[$char];
        }
        return $node->isEnd;
    }
}
PHP

构建完前缀树之后，就可以使用前缀树来查找关键字了。只需要在前缀树中查找输入字符串，如果能够找到，则说明字符串存在于前缀树中，即存在于关键字列表中。