无限极分类(adjacency list)的三种方式(迭代、递

作者:编程技术

司空见惯来讲是将数据总体从数据库读取后,然后再组装数组来得以达成,当然也能够每趟递归等都查询数据库,不过会变成数据库压力,且不便于封装成方法,不提议那样做。

 

自个儿去,那间隔,第二种艺术真是逆天了。可是再度提示,那只是一回性读取多的数额的时候,当数据量十分小的时候,八九不离十,不确定非要用最高效用的,还能透过懒加载等任何方法来完成。

第意气风发大家透过

 

如上是thinkphp的沙盘模拟经营标签,volist和foreach是同生机勃勃的道理

上边所说的都为adjacency list的样式,数据表格式相同id,pid,name这种格式。

$value的值表示数据Curry面包车型客车意气风发行,是叁个数组,$value['名字']表示大器晚成行里面包车型大巴一个字段。

2、第三种是应用入栈、出栈的递归来计量,功用比上个好点,可是也挺慢的。流程是先反转数组,然后抽取顶尖数组入栈,起先while循环,先出栈二个搜索其下有未有子节点,要是有子节点,则将此子节点也入栈,后一次while循环就能够查子节点的,依次类推:

$value['pid'] == $pid
判断当前的pid是否为0,因为我们在sort方法一开始的时候就给了一个默认值0,此时$pid为0。

这样做的目的就是选出第一个顶级节点。

如果找到了第一个顶级节点,假如是中国,那么满足if的条件,就进入条件体,先给$value数组加一个level值,然后再把$value整个假如到静态数组当中去。

然后开始递归,注意,此刻sort方法的pid参数接受的是当前节点的id。为什么要这样传呢?

举个例子:

如果我们循环到了中国,如下图

 

那便是说那是怎么输出的吧?

相符的分类树状构造有三种办法:

美高梅4858官方网站 1

下一场再递归生成select下拉菜单所要求的,由于上方的诡异格式,引致递归起来十分快:

这般就可以预知很清晰的见到他们的等级次序布局了,那么这么的功力在thinkphp5.0是怎么落到实处的吗?

3、利用征引来管理,这一个真的很奇妙,而且功能最高,可参照这里,假若想看再详尽的分解,可以查阅那几个问答。

当数码传入sort方法之后,声澳优个静态数组,保险每一遍递归调用的时候数组里面的多寡不会变动,然后循环从数据Curry面查询的数量。

  1 /**
  2  * parent_id类型树结构相关
  3  * 没必要非要写成静态的方法,静态方法参数太多,所以用实例在构造函数中修改参数更合适
  4  * 需要首先将所有数据取出,然后再用此方法重新规划数组,其它的边取边查询数据库的方法不推荐
  5  * 经测试第一种方法要快很多,建议使用
  6  * @author   vishun <nadirvishun@gmail.com>
  7  */
  8 
  9 class Tree
 10 {
 11     /**
 12      * 图标
 13      */
 14     public $icon = '└';
 15     /**
 16      * 填充
 17      */
 18     public $blank = '&nbsp;&nbsp;&nbsp;';
 19     /**
 20      * 默认ID字段名称
 21      */
 22     public $idName = 'id';
 23     /**
 24      * 默认PID字段名称
 25      */
 26     public $pidName = 'pid';
 27     /**
 28      * 默认名称字段名称
 29      */
 30     public $titleName = 'name';
 31     /**
 32      * 默认子元素字段名称
 33      */
 34     public $childrenName = 'items';
 35 
 36     /**
 37      * 构造函数,可覆盖默认字段值
 38      * @param array $config
 39      */
 40     function __construct($config = [])
 41     {
 42         if (!empty($config)) {
 43             foreach ($config as $name => $value) {
 44                 $this->$name = $value;
 45             }
 46         }
 47     }
 48 
 49     /**
 50      * 生成下拉菜单可用树列表的方法
 51      * 经测试4000条地区数据耗时0.02左右,比另外两种方法快超级多
 52      * 流程是先通过引用方法来生成一种特殊树结构,再通过递归来解析这种特殊的结构
 53      * @param array $list
 54      * @param int $pid
 55      * @param int $level
 56      * @return array
 57      */
 58     public function getTreeOptions($list, $pid = 0, $level = 0)
 59     {
 60         //先生成特殊规格的树
 61         $tree = $this->getTree($list, $pid);
 62         //再组装成select需要的形式
 63         return $this->formatTree($tree, $level);
 64     }
 65 
 66     /**
 67      * 通过递归来解析特殊的树结构来组装成下拉菜单所需要的样式
 68      * @param array $tree 特殊规格的数组
 69      * @param int $level
 70      * @return array
 71      */
 72     protected function formatTree($tree, $level = 0)
 73     {
 74         $options = [];
 75         if (!empty($tree)) {
 76             $blankStr = str_repeat($this->blank, $level) . $this->icon;
 77             if ($level == 0) {//第一次无需有图标及空格
 78                 $blankStr = '';
 79             }
 80             foreach ($tree as $key => $value) {
 81                 $options[$value[$this->idName]] = $blankStr . $value[$this->titleName];
 82                 if (isset($value[$this->childrenName])) {//查询是否有子节点
 83                     $optionsTmp = $this->formatTree($value[$this->childrenName], $level   1);
 84                     if (!empty($optionsTmp)) {
 85                         //$options = array_merge($options, $optionsTmp);//发现一个问题,这里直接用array_merge会导致key重排
 86                         $options = $options $optionsTmp;
 87                        //$options = ArrayHelper::merge($options, $optionsTmp);//如果是用yii2带话可以用助手类,需要use其命名空间
 88                     }
 89                 }
 90             }
 91         }
 92         return $options;
 93     }
 94 
 95     /**
 96      * 生成类似下种格式的树结构
 97      * 利用了引用&来实现,参照:http://blog.csdn.net/gxdvip/article/details/24434801
 98      * [
 99      *  'id'=>1,
100      *  'pid'=>0,
101      *  'items'=>[
102      *      'id'=>2,
103      *      'pid'=>'1'
104      *       。。。
105      *  ]
106      * ]
107      * @param array $list
108      * @param int $pid
109      * @return array
110      */
111     protected function getTree($list, $pid = 0)
112     {
113         $tree = [];
114         if (!empty($list)) {
115             //先修改为以id为下标的列表
116             $newList = [];
117             foreach ($list as $k => $v) {
118                 $newList[$v[$this->idName]] = $v;
119             }
120             //然后开始组装成特殊格式
121             foreach ($newList as $value) {
122                 if ($pid == $value[$this->pidName]) {
123                     $tree[] = &$newList[$value[$this->idName]];
124                 } elseif (isset($newList[$value[$this->pidName]])) {
125                     $newList[$value[$this->pidName]][$this->childrenName][] = &$newList[$value[$this->idName]];
126                 }
127             }
128         }
129         return $tree;
130     }
131 
132     /**
133      * 第二种方法,利用出入栈迭代来实现
134      * 经测试4000条地区数据耗时6.5s左右,比较慢
135      * @param $list
136      * @param int $pid
137      * @param int $level
138      * @return array
139      */
140     public function getTreeOptions2($list, $pid = 0, $level = 0)
141     {
142         $tree = [];
143         if (!empty($list)) {
144 
145             //先将数组反转,因为后期出栈时会有限出最上面的
146             $list = array_reverse($list);
147             //先取出顶级的来压入数组$stack中,并将在$list中的删除掉
148             $stack = [];
149             foreach ($list as $key => $value) {
150                 if ($value[$this->pidName] == $pid) {
151                     array_push($stack, ['data' => $value, 'level' => $level]);//将层级记录下来,方便填充空格
152                     unset($list[$key]);
153                 }
154             }
155             while (count($stack)) {
156                 //先从栈中取出第一项
157                 $info = array_pop($stack);
158                 //查询剩余的$list中pid与其id相等的,也就是查找其子节点
159                 foreach ($list as $key => $child) {
160                     if ($child[$this->pidName] == $info['data'][$this->idName]) {
161                         //如果有子节点则入栈,while循环中会继续查找子节点的下级
162                         array_push($stack, ['data' => $child, 'level' => $info['level']   1]);
163                         unset($list[$key]);
164                     }
165                 }
166                 //组装成下拉菜单格式
167                 $blankStr = str_repeat($this->blank, $info['level']) . $this->icon;
168                 if ($info['level'] == 0) {//第一次无需有图标及空格
169                     $blankStr = '';
170                 }
171                 $tree[$info['data'][$this->idName]] = $blankStr . $info['data'][$this->titleName];
172             }
173         }
174         return $tree;
175     }
176 
177     /**
178      * 第三种普通列表转为下拉菜单可用的树列表
179      * 经测试4000条地区数据耗时8.7s左右,最慢
180      * @param array $list 原数组
181      * @param int $pid 起始pid
182      * @param int $level 起始层级
183      * @return array
184      */
185     public function getTreeOptions3($list, $pid = 0, $level = 0)
186     {
187         $options = [];
188         if (!empty($list)) {
189             $blankStr = str_repeat($this->blank, $level) . $this->icon;
190             if ($level == 0) {//第一次无需有图标及空格
191                 $blankStr = '';
192             }
193             foreach ($list as $key => $value) {
194                 if ($value[$this->pidName] == $pid) {
195                     $options[$value[$this->idName]] = $blankStr . $value[$this->titleName];
196                     unset($list[$key]);//销毁已查询的,减轻下次递归时查询数量
197                     $optionsTmp = $this->getTreeOptions3($list, $value[$this->idName], $level   1);//递归
198                     if (!empty($optionsTmp)) {
199                         //$options = array_merge($options, $optionsTmp);//发现一个问题,这里直接用array_merge会导致key重排
200                         $options = $options $optionsTmp;
201                        //$options = ArrayHelper::merge($options, $optionsTmp);//如果是用yii2带话可以用助手类,需要use其命名空间
202                     }
203                 }
204             }
205         }
206         return $options;
207     }
208 }

那怎么获得如下的格式化数据吧?

现阶段以来常用的有二种办法,大家来兑现select下拉菜单体现的体裁:

当递归回来时,江西出栈,这时栈空间里面保存的是友好邻邦的多寡,包含pid为0那一个变量,level为0这些变量,以致静态数组。当实行下四个周而复始时,$value['pid'] == $pid

  • 首先种办法(递归)耗费时间:8.9441471099854左右
  • 其次种方法(迭代)耗费时间:6.7250330448151左右
  • 其二种方式(援用)耗时:0.028863906860352左右

从pid为0看出,中中原人民共和国和伦敦是第一流节点。

1、首先是最常用最日常,相仿也是效能最低的递归方法:就是不停的foreach循环递归。

由从此台分配而来的cateList数据(也正是上面包车型大巴静态数组卡塔尔国,通过

  • 生机勃勃种是adjacency list,也正是是id,parent id那中方式。
  • 另少年老成种是nested set,即左右值的款式。

先是我们得以见见,在cateTree方法中我们通过select(卡塔尔(英语:State of Qatar)方法获得到了数据Curry面包车型地铁保有数据,然后将数据传入到sort里面,此刻大家注意到sort有八个参数,pid表示如今节点的父节点的id,level表示方今节点

function getTreeOptions2($list, $pid = 0)
{
    $tree = [];
    if (!empty($list)) {
        //先将数组反转,因为后期出栈时会优先出最上面的
        $list = array_reverse($list);
        //先取出顶级的来压入数组$stack中,并将在$list中的删除掉
        $stack = [];
        foreach ($list as $key => $value) {
            if ($value['pid'] == $pid) {
                array_push($stack,$value);
                unset($list[$key]);
            }
        }
        while (count($stack)) {
            //先从栈中取出第一项
            $info = array_pop($stack);
            //查询剩余的$list中pid与其id相等的,也就是查找其子节点
            foreach ($list as $key => $child) {
                if ($child[pid] == $info['id']) {
                    //如果有子节点则入栈,while循环中会继续查找子节点的下级
                    array_push($stack,  $child);
                    unset($list[$key]);
                }
            }
            //组装成下拉菜单格式
            $tree[$info['id']] = $info['name'];
        }
    }
    return $tree;
}

接下去的步骤就好多了,首先foreach循环齐化门的子节点,发掘并未有子节点,递归截止,相同的时间将sort($data,7,3)出栈,回到递归步向出,以上为例,则赶回西安门这段代码的sort处,同临时候实践foreach循环,查找是或不是有此外的节点的pid为6,即查看新加坡下是或不是还大概有其他子节点。假若有,则将该节点的多寡入栈,若无则出栈,回到首都那块代码的sort处,相配pid为1的是或不是还应该有别的节点。若无则赶回最开端的sort处,那个时候递归完全告竣。

美高梅4858官方网站 2美高梅4858官方网站 3

 

 

 

function formatTree($tree)
{
    $options = [];
    if (!empty($tree)) {
        foreach ($tree as $key => $value) {
            $options[$value['id']] = $value['name'];
            if (isset($value['items'])) {//查询是否有子节点
                $optionsTmp = $this->formatTree($value['items']);
                if (!empty($optionsTmp)) {
                    //$options = array_merge($options, $optionsTmp);
                    $options =$options  $optionsTmp;//用array_merge会导致索引重排
                }
            }
        }
    }
    return $options;
}

美高梅4858官方网站 4

顺手封装个类,能够追加一些填充什么的。越来越多的细节可以查阅上边包车型地铁类:

 

如上二种,对于数据量小的来讲,不在乎用哪一种,然则对于数据量大的来讲就十二分醒目了,用4000条地点数据测量检验结果成效相比:

好了,贴出代码:

以上记录下,如转发请证明源于地址

美高梅4858官方网站 5

View Code

从上海教室中能够发掘,中中原人民共和国下有海南,新加坡八个子节点,而新加坡市有西华门二个子节点,纽约的子节点是“London的子类”。

/**
* 先生成类似下面的形式的数据
* [
*  'id'=>1,
*  'pid'=>0,
*  'items'=>[
*      'id'=>2,
*      'pid'=>'1'
*       。。。
*  ]
* ]
*/
function getTree($list, $pid = 0)
{
    $tree = [];
    if (!empty($list)) {
        //先修改为以id为下标的列表
        $newList = [];
        foreach ($list as $k => $v) {
            $newList[$v['id']] = $v;
        }
        //然后开始组装成特殊格式
        foreach ($newList as $value) {
            if ($pid == $value['pid']) {//先取出顶级
                $tree[] = &$newList[$value['id']];
            } elseif (isset($newList[$value['pid']])) {//再判定非顶级的pid是否存在,如果存在,则再pid所在的数组下面加入一个字段items,来将本身存进去
                $newList[$value['pid']]['items'][] = &$newList[$value['id']];
            }
        }
    }
    return $tree;
}

为几级。(一级节点是0级,拔尖节点的子节点是1级),那么level的用途届期候输出的时候会用到,此处不用郁结。

function getTreeOptions3($list, $pid = 0)
{
    $options = [];
    foreach ($list as $key => $value) {
        if ($value['id'] == $pid) {//查看是否为子元素,如果是则递归继续查询
            $options[$value['id']] = $value['name'];
            unset($list[$key]);//销毁已查询的,减轻下次递归时查询数量
            $optionsTmp = $this->getTreeOptions3($list, $value['id']);//递归
            if (!empty($optionsTmp)) {
                //$options = array_merge($options, $optionsTmp);//销毁已查询的,减轻下次递归时查询数量
               $options =$options  $optionsTmp;//用array_merge会导致索引重排
            }
        }
    }
    return $options;
} 
 <td><?php echo str_repeat("-",$cate["level"]*8)?>{$cate.cate_name}</td>
得到最终的结果。

 

那会儿我们来观看数组,能够看来,通过递归,数组里的多寡带头变得有序起来,如广东是神州的一级子节点,所以紧跟在神州以后,当第意气风发轮递总结束,到了第一轮递归时,第三个找到的是京城,所以数组里面第八个因素是新加坡。

左右值方式查询起来相比较飞快,不需求递归等,推荐使用,可是从未pid情势轻易直观,何况有个别旧的数据库相仿地区等布局划杜撰计一向是pid这种格局(貌似也是有算法能够将两个调换,不做长远摸底),所以。。。

大家能够开采,新加坡和湖南的level是均等的,注意:大家的数组还保存得有level消息(图中的level有个别错误,不建议我们参照他事他说加以考察)。

第一次递归的时候,会将static 数组入栈,以及将变量入栈,并保存程序的断点,以便递归完成之后能够顺利的找到进入递归出并继续执行程序。


如上图,找到中国后,递归,入栈,此刻静态数组里面只有“中国”一个数据。(注意:数组是一个二维数组,我只是为了简便才画了一维数组,数组里面还包含了level的信息)。通过pid判断中国下方是否有子节点,然后匹配到贵州之后,进入递归,数据入栈。此时静态数组里面又增加了贵州这个数据。

到了贵州之后,发现在我们的数据表里面并没有贵州的子节点,此时递归结束,程序返回递归入口处,继续执行循环体,栈空间如下:

率先我们来看数据表

美高梅4858官方网站 6

因为栈空间里面保存的pid是0,所以会找到上海以此数目。

level数值大的近日的短线就更加多,表示级数就越大。

那正是说,当使用Infiniti极分类之后数据的输出是哪些的吗?如下:

能够发掘,着写多少在数额表中是冬日的,并未大家想像中的档次构造分明并且可读性很好。

 

因为浙江的pid是1,而中华的id为1,所以福建的父节点是炎黄,至于type字段,能够不用管,只是自己要好的品类供给。

<?php
/**
 * Created by PhpStorm.
 * User: Administrator
 * Date: 2017/9/24
 * Time: 17:14
 */

namespace appadminmodel;
use thinkModel;
class Cate extends Model
{
    public function cateTree(){
        $res=$this->select();
        if($res){
            $result=$this->sort($res);
            return $result;
        }
    }
    public function sort($data,$pid=0,$level=0){
    //此处数据必须是静态数组,不然递归的时候每次都会声明一个新的数组
       static $arr=array();
        foreach ($data as $key=>$value){
            if($value['pid'] == $pid){
                $value["level"]=$level;
                $arr[]=$value;
                $this->sort($data,$value['id'],$level 1);
            }
        }
        return $arr;
    }
}

美高梅4858官方网站 7

                                        {volist name="cateList" id="cate"}
                                        <!--设置URL值,方便JS删除的时候获取路径-->
                                        <tr id="{:url('delete',array('id'=>$cate.id))}" class="url">
                                            <td align="center">{$cate.id}</td>
                                            <td><?php echo str_repeat("-",$cate["level"]*8)?>{$cate.cate_name}</td>
{/volist}

美高梅4858官方网站 8

本文由分分快三计划发布,转载请注明来源

关键词: 无限级分类 php 递归 thinkphp5.0