本文介绍了字典树的实现原理，又名查词树、Trie树，是一种树结构，是hash树的变种。典型应用用于对大量字符串（但不限于字符串）进行统计、排序和保存，因此常被搜索引擎系统用于文本词频统计。其优点是：利用字符串的公共前缀减少查询时间，尽量减少不必要的字符串比较，查询效率高于哈希树。1.Trie示意图2.节点定义classNode{public$isWord;public$value;//可以存储其他信息public$next;//这是一个Map树，指向其他25个字母publicfunction__construct(){$this->next=newBinarySearchTreeMap();}}3。Trietrie类定义如下定义一个Trie，其中add()方法可以向Trie添加单词，contains()可以查询某个单词是否包含在Trie中，isPrefix()方法可以判断是否包含单词Trie中有一个带有指定字符串前缀的词：root=newTrieNode();}/***添加*@到Trieparamstring$word添加元素到字段树*/publicfunctionadd(string$word,$value){$node=$this->root;对于($i=0;$inext->get($c)==null){$node->next->add($c,newTrieNode($value));}$node=$node->next->get($c);}如果（！$node->isWord){$node->isWord=true;$这个->尺寸++；}}/***检查单词word是否存在于Trie树中*@param$word*/publicfunctioncontains($word){$node=$this->root;对于($i=0;$inext->get($c)==null){returnfalse;}$node=$node->next->get($c);}if($node->isWord){返回真；}else{返回错误；}}/***获取字段树节点信息*@param$word*/publicfunctionget($word){$node=$this->root;对于($i=0;$inext->get($c)==null){返回null;}$node=$node->next->get($c);}返回$node->value;}/***判断某个字符串是否为单词前导*@paramstring$prefix*@returnbool*/publicfunctionisPrefix(string$prefix){$node=$this->root;对于($i=0;$inext->get($c)==null）{returnfalse;}$node=$node->next->get($c);}返回假；}publicfunctiongetSize(){return$this->size;}}classTrieNode{public$isWord=false;公共$下一个；公共$值=空；公共函数__construct($value=null){$this->value=$value;$this->next=newBinarySearchTreeMap();}}4.输出显示add('qsx',123);$trie->add('dog',456);$trie->add('cat',789);$trie->add('else',111);$trie->add('good',111);var_dump($trie->contains('qsx'));var_dump($trie->contains('dog'));var_dump($trie->contains('aaaa'));var_dump($trie->contains('ddd'));var_dump($trie->get('qsx'));var_dump($trie->get('cat'));var_dump($trie->get('dog'));var_dump($trie->get('good'));var_dump($trie->isPrefix('go'));var_dump($trie->isPrefix('goo'));var_dump($trie->isPrefix('goop'));代码仓库：https://gitee.com/love-for-po...扫码关注爱因世贤
