PHP数据结构(十四) ——键树(双链树)

PHP数据结构(十四)

——键树(双链树)

(原创内容,转载请注明来源,谢谢)

一、概念

键树又称为数字查找树,该树的度>=2,每个节点不是存储关键字,而是存储组成关键字的一个字符或数值的一个数字。例如现有下列字符串:lin、li、linhxx、php、pdo、phper,使用键树存储的结果如下图:

从上图可以看出,键树由一个不代表任何内容的根节点、若干字符节点和一个结束节点组成,结束节点统一用$表示。

二、存储

键树有两种存储方式,一种称为双链树存储,另一种称为多重链表存储(又称Trie树)。

1、双链树存储

以树的孩子兄弟表示键树,每个节点包括三个域:symbol域,存储关键字的字符;first域,存储第一棵子树的节点;next域,存储下一个兄弟指针。

双链树对于查找而言非常便利,而对于增加、删除节点较为复杂。双链树存储如下图所示。

从双链树进行查找和插入的方法,即字符串逐个比较的方法,用第一个字符和根节点下面的所有第一级子节点进行比较,如果存在则进入该子树,再用第二个字符和子树的第一级子节点进行比较;如果比较失败,则插入一个子树。

编程思想:

1)把字符串逐个进行遍历,遍历第一个字符串的时候在双链树的第一行,第二个进入第二行;

2)先横向遍历,如果没有找到节点,则生成一个节点,并让上一个兄弟节点指向该节点,再进入其子节点进行循环。如果找到节点,则直接进入其子节点。

3)子节点生成后,需要将其父节点指向该子节点。

4)代码的关键在于用两个临时栈,一个是兄弟节点栈,在横向遍历的时候暂存;一个是双亲节点栈,用于在纵向遍历的时候暂存。

代码执行结果如下:

源码如下:

<?php
//键树-双链树结构-节点
class Node{
         public $symbol;//标记字符
         public $last;//标记第一个兄弟节点
         public $first;//标记第一个子节点
         public function __construct($symbol =null, $first = null, $last = null){
                   $this->symbol = $symbol;
                   $this->first = $first;
                   $this->last = $last;
         }
}
classDoubleLinkKeyTree{
         private $tree;
         public function __construct(){
                   $this->tree = newNode();//根节点
                   $this->tree->first =new Node();
         }
         //构造双链树
         //格式:array($str1,$str2, $str3)
         public function generate(array$arrStr){
                   //初始情况:把最后一个字符串直接生成到树
                   $strLast =array_pop($arrStr);//剔除最后一个字符串,采用最后一个不采用第一个是因为array_pop速度比array_shift快
                   $strLast .= '$';//加上结束符
                   $curNode = $this->tree;
                   for($i=0;$i<strlen($strLast);$i++){
                            $curNode->first =new Node($strLast[$i]);
                            $curNode =$curNode->first;
                   }
                   $curNode =$this->tree->first;//当前节点回到根节点的第一个子树 
                   $broStack = array();//兄弟节点栈
                   $parStack = array();//双亲节点栈
                   //逐个字符串生成双链树的节点
                   foreach($arrStr as $str){
                            $str .= '$';//加上结束符 
                            //遍历字符串str的每一个字符
                            for($i=0;$i<strlen($str);$i++){
                                     //如果节点是空,则
                                     if(null ==$curNode){
                                               //获取双亲节点
                                               $parNode= array_pop($parStack);
                                               //构造子节点并入栈
                                               $curNode= new Node($str[$i]);
                                               array_push($parStack,$curNode);
                                               //修改双亲阶段指向
                                               $parNode->first= $curNode;
                                               //修改子节点指向
                                               $curNode= $curNode->first;
                                               continue;
                                     }
                                     //遍历兄弟节点
                                     while(null!= $curNode && $curNode->symbol != $str[$i]){
                                               array_push($broStack,$curNode);
                                               $curNode= $curNode->last;
                                     }
                                     if(null ==$curNode){
                                               //回溯上一个兄弟节点
                                               $lastNode= array_pop($broStack);
                                               //建立节点并入栈
                                               $curNode= new Node($str[$i]);
                                               array_push($parStack,$curNode);
                                               //将上一个节点指向该节点
                                               $lastNode->last= $curNode;
                                               //开始遍历该节点的子节点
                                               $curNode= $curNode->first;
                                               continue;
                                     }
                                     //如果兄弟节点找到相同的节点,则遍历子节点
                                     if($curNode->symbol== $str[$i]){
                                               array_push($parStack,$curNode);
                                               $curNode= $curNode->first;
                                               continue;
                                     }
                                     $broStack =array();//释放兄弟节点栈(因为每一个字符结束要去下一行搜索,本行的兄弟节点栈没有意义)
                            }                          
                            //遍历完一个字符串,回到根节点
                            $curNode =$this->tree->first;
                   }
                   return $this->tree;
         }
         //查询是否存在树中
         public function search($str){
                   $curNode = $this->tree;
                   //如果树还没生成,返回false
                   if(null == $curNode){
                            return false;
                   }
                   $curNode =$this->tree->first;
                   //如果树还没生成,返回false
                   if(null == $curNode){
                            return false;
                   }
                   $isExist = true;
                   $str .= '$';//拼接上结束符
                   for($i=0;$i<strlen($str);$i++){
                            if(null ==$curNode){
                                     $isExist =false;
                                     break;
                            }                          
                            //如果匹配,则查下一个字符
                            if($str[$i] ==$curNode->symbol){
                                     $curNode =$curNode->first;
                                     continue;
                            }
                            //查找兄弟节点
                            while(null !=$curNode && $str[$i] != $curNode->symbol){
                                     $curNode =$curNode->last;
                            }
                            //兄弟节点都没有匹配的,则返回false
                            if(null ==$curNode){
                                     $isExist =false;
                                     break;
                            }
                            //兄弟节点匹配的,查找其子节点 
                            $curNode =$curNode->first;
                   }
                   return $isExist;
         }
}
$doubleLinkKeyTree= new DoubleLinkKeyTree();
$res =$doubleLinkKeyTree->generate(array('lin', 'php', 'li'));
print_r($res);

——written by linhxx 2017.07.14

相关阅读:

PHP数据结构(十三) ——动态查找表(二叉排序树)

PHP数据结构(十二) ——静态查找表​

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)

PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏King_3的技术专栏

leetcode-136-Single Number

2044
来自专栏coding for love

JS入门难点解析10-创建对象

(注1:如果有问题欢迎留言探讨,一起学习!转载请注明出处,喜欢可以点个赞哦!) (注2:更多内容请查看我的目录。)

793
来自专栏一个会写诗的程序员的博客

《Kotlin极简教程》第3章 Kotlin语言基础第3章 Kotlin语言基础《Kotlin极简教程》正式上架:参考资料

学习任何东西,都是一个由表及里的过程。学习一门编程语言也一样。对于一门编程语言来说,“表” 就是基本词汇(关键字、标识符等)、句子(表达式)和语法。

1042
来自专栏逸鹏说道

我为NET狂官方面试题-基础篇

最近帮人过一遍C#基础,出了点题目,有需要的同志拿走 答案不唯一,官方答案只供参考,若有错误欢迎提出~ 答案明天发 面向过程 99乘法表 ? 用循环来输出以...

3109
来自专栏老九学堂

【超全】C语言小白最容易犯的17种错误,你中了几个?

C编译的程序对语法检查并不像其它高级语言那么严格,这就给编程大佬们留下了“灵活的余地”,但还是由于这个灵活给程序的调试带来了许多不便,尤其对刚刚接触C语言的人来...

3305
来自专栏mathor

TRIE(3)

 搜索引擎现在一般都有关键词提示或者说是补全功能。就是当你在搜索框里输入一个关键词s时,搜索引擎会自动提示你一些频率比较高,同时前缀是s的关键词  这道...

792
来自专栏CSDN技术头条

12个非常有用的JavaScript技巧

在这篇文章中,我将分享12个非常有用的JavaScript技巧。这些技巧可以帮助你减少并优化代码。 1) 使用!!将变量转换成布尔类型 有时,我们需要检查一些变...

2046
来自专栏阮一峰的网络日志

Javascript 面向对象编程(一):封装

学习Javascript,最难的地方是什么? 我觉得,Object(对象)最难。因为Javascript的Object模型很独特,和其他语言都不一样,初学者不容...

3407
来自专栏编程坑太多

JS实现运算符重载

1742
来自专栏web前端教室

重学javascript 红皮高程(2)

为了送礼三八女王节,今晚跟同学一起喝酒去了。更新的有点晚,哈哈。。 让我们继续重新温习JS高程,今天来复习下基本概念。 JS它的语法是区分大小写地,并且函数名不...

1718

扫码关注云+社区