奥门新浦京官方网站Ztree + PHP 无限级节点递归查找

一、前言

简单的描述一下,实习几个原理,思想,其实写很多东西,思想算是最重要的。

1、目标:将写一个无限节点的树形目录结构,如下图

奥门新浦京官方网站 1


首先我们来看数据表

步骤:

1、你的下载 插件  ztree。然后布置在你的项目中。

<script src="__PUBLIC__/js/jquery-1.4.4.min.js"></script> 
<script src="__PUBLIC__/js/jquery.ztree.core-3.5.js"></script>

2、相关CSS

<link rel="stylesheet" href="__PUBLIC__/css/zTreeStyle/zTreeStyle.css" type="text/css"> 
<link rel="stylesheet" href="__PUBLIC__/css/zTree.css" type="text/css">

以上CSS 和JS 以你自己的为准。

3、目录结构DIV

<div class="content_wrap"  style="background:#666;"> 
    <div class="zTreeDemoBackground left"> 
        <ul id="treeDemo" class="ztree"></ul> 
    </div> 
</div> 
<div class="content-text" id="text"></div>

4、自己单独js中的代码

<SCRIPT  src="__PUBLIC__/js/ztreeonload.js"></SCRIPT>

里面写的相关功能及配置!

//配置项 
var setting = { 
     isSimpleData : true,              //数据是否采用简单 Array 格式,默认false  性   
     showLine : true,                  //是否显示节点间的连线   
     checkable : true,    
     callback: { 
         onClick: zTreeOnClick       
     } 
 }; 

 var zNodes;//数据变量 

 //ajax提交数据,请求后台PHP处理返回出目录结构json数据 
 $.ajax({ 
     url:"/admin.php/Ztree", 
     type: "get", 
     async: false, 
     dataType:"json",   
     success: function (data) { 
             //alert(data); 
             zNodes=data;    //将请求返回的数据存起来 
              //alert(zNodes); 
     }, 
     error: function (){//请求失败处理函数   
         alert('请求失败');   
     },   
 }) 

 //初始化ztree目录结构视图! 
 $(document).ready(function(){ 
     //alert("111"); 
     $.fn.zTree.init($("#treeDemo"), setting, zNodes); 
 });

5、后台PHP 递归算法,从数据库中查找目录结构并且生成 JSON数据

地址:如4中,AJAX所请求的
【/admin.php/Ztree】我这里是用的ThinkPHP框架,所以url是这个样子,以你自己的接口文件为准!

<?php 
            //父节点数组 
            $arr=array(); 
            $arr_str0 = array("name" =>'函数库查询','children'=>$this->SelectSon(1));       //父节点  Pid=1; 
            $arr_str1 = array("name" =>'数据库查询','children'=>$this->SelectSon(2));       //父节点  Pid=2; 

            array_push($arr, $arr_str0); 
            array_push($arr, $arr_str1);//这里是2个父节点。 

            echo(json_encode($arr)); //这是最后返回给页面,也就是返回给AJAX请求后所得的返回数据 JSON数据 
?> 

//这里仅仅是一个方法,一个调用SelectSon()方法,返回一个数组集合!但其中用的是递归! 
<?php 
        //查找子节点        Pid=父节点ID 
        private function SelectSon($Pid){ 

            $m=M('ztree'); 

            if(($info=$m->where("Pid='$Pid'")->select())) //查找该父ID下的子ID 
            { 
                $data=array(); 
                for ($i=0; $i < count($info) ; $i++)  
                {  
                    $da=array("name" =>$info[$i]['name'],'children'=>$this->SelectSon($info[$i]['id']));  //递归算法! 

                    array_push($data, $da);//加入子节点数组 
                }; 

                return $data;//一次性返回子节点数组,他们成为同级子节点。 
            } 
            else 
            { 
                return null; 
            } 

        } 
?>

奥门新浦京官方网站,注意:由于我是用的thinkphp框架。所以在方法调用上
有些不同,纯PHP文件中,思路应该是一样的,

首先是: 写一个数组。一个父节点的数组。

其次:  写一个方法,传递的参数是
父节点的ID,查询其子节点,在子节点中查询之后,用递归的方式继续查找子节点的子节点,直到最后查询完毕之后,返回数组给调用方法的父节点数组。然后再

echo(json_encode($arr));

转码成 JSON 将其输出,以便于AJAX异步访问,得到JSON数据。

得到之后,回到刚刚的JS功能代码中,直接初始化树目录结构,将其JSON数据传入OK。

前言

  • 由于项目更新迭代,原有的分类采用的是层级递增并且跳转选择的模式,样式单一,且不方便用户快速选择定位类别。所以有了更新和改版的需求。采用一个界面展示一二三级目录的方式,既直观也好看,也是各大电商App青睐的方式,如京东,淘宝等App分类模块。
  • 由于公司业务比较广,类别目录有上千个,如何能够快速解析数据,构建适用的数据结构并展示,成为前端开发的一个难点,而此次实践着重解决该问题。

奥门新浦京官方网站 2

总结:

其主要思想分2步走。第一步,是如何能把目录生成出来。先测试时,可以用静态数据。类似于

var node=[ 
    {name:'父节点',children:[{name:'子节点',children:null},{name:'同级子节点',children:null}]} 
] 

先分析一下,这串数据,他有什么规律。你就会发现。其实很有规律。无限节点,其实就是每个json中,有children,而且 
还有同级子节点。

你先用固定数据 生成目录结构之后

你就可以开始考虑,动态的向node传目录结构的数据了。就是我们后面所谓的
AJAX请求 PHP得到JSON数据,

PHP处理中,我用的是递归算法,返回JSON数据。及完成了。目录结构。

哦对了。

$m=M('ztree');

这句代码是thinkphp 实例化 数据操作对象的。

用来查询数据库中,节点是否存在。就是存在子节点,就返回给子节点数组,有几个就加入子节点数组中,查询完了。然后一次性返回,他们就成了同级子节点了

业务分析

  • 采用一,二,三级目录展示方式呈现界面。(如图)
![](https://upload-images.jianshu.io/upload_images/2158576-6b1da7173cb90219.jpg)

分类页.jpg

  • 后台一次返回所有的分类JSON数据信息,存放在一个数组中。

{
    "category": [
        {
            "cat_id": "11241",
            "cat_name": "Earbud Headphones",
            "parent_id": "11994",
            "level": "3",
            "mobile_cat_pic": "http://uidesign.gearbest.com/GB/images/banner/others/ios/.jpg",
            "cat_url": "/earphones-c_11241/"
        },
        {
            "cat_id": "11249",
            "cat_name": "Car DVR",
            "parent_id": "11247",
            "level": "2",
            "mobile_cat_pic": "http://uidesign.gearbest.com/GB/images/banner/others/ios/.jpg",
            "cat_url": "/car-dvr-c_11249/"
        },
        {
            "cat_id": "11578",
            "cat_name": "Gifts",
            "parent_id": "0",          //一级列表默认父目录节点ID 返回 0.
            "level": "1",
            "mobile_cat_pic": "https://uidesign.gearbest.com/GB/app/2016/ios_category/Gift.png",
            "cat_url": "/gifts-c_11578/",
        },
        //...
}
  • 请求并解析数据,然后做缓存处理。由于公司分类信息改动频率较低,若有更新,另通过其他接口字段进行判断更新缓存。

 

JSON数据分析

  • 上千个类目信息一并返回。那么数据的数量级若为N,
    N则为1000,即10^3级别。
  • 构建成类似系统目录方式的一个树形结构,又或者称之为一个图,并且图是保证联通的,即目录数据完整。
  • 解析数据并转化为我们可用于展示的数据结构的过程,称之为构图的过程。相当于,解析数据的时间复杂度,即为构图的时间复杂度。接下来介绍的是根据特定JSON数据源进行构图的O(N)算法。

选择合适的数据结构作为数据查询和存储

  • 为了快速根据父级目录ID获取子目录信息,查询最优便是采用Hash表,即对应OC中的NSMutableDictionary,查询时间复杂度为O(1)
  • key作为该目录节点的分类ID。
  • value对应该目录节点下的子目录集合,可用一个NSMutableArray进行存储。
  • 默认构建目录根节点为ID == 0
  • 全局声明如下:

    NSString *_categoryRootKey;             //根节点ID
    NSMutableDictionary *_categoryMap;      //图存储Hash表

从上图中可以发现,中国下有贵州,北京两个子节点,而北京有天安门一个子节点,纽约的子节点是“纽约的子类”。

构图思路

  • 第一种思路 :
    由于数据是一并返回,通过解析框架解析后,每个Model节点记录了当前分类的ID,以及父级分类ID和类目信息。大多数人很容易想到的一种方式便是从上往下进行构图,即从根节点开始,到一级目录,再到二级目录,最后三级目录的方式。那么每次需要查询level对应的所有子目录信息,这个查找过程,每次都是O(N)的查询,再结合构图的外层循环,时间复杂度达到了O(N^2)对应手机端的处理能力,N为1000的话,数据处理量将是百万级别的。初略时间统计,大概要耗时近1s才能解析成方便展示和查询使用的数据结构。对于App用户而言,显然太慢了。
  • 第二种思路:根据第一种思路进行改良,可先对所有的分类信息,根据level进行排序,再依次递归处理,时间复杂度会略微下降,但是仍然不够理想,代码可自行YY。
  • 第三种思路:
    从下往上构图,由于目录完整,那么任何一个目录节点一定会有对应的父级目录节点。那么遍历分类信息数组,先判断对应的父节点是否已经生成,如果生成了,则将当前的目录节点加到Hash表对应的孩子数组中,若当前父级目录节点还未创建并存在于Hash表中,则生成一个父节点,再将当前的分类节点添加到新创建的父目录节点的子目录数组中。通过这种构建方式,则可以遍历一次分类数组就可完成,时间复杂度为O(N)。代码如下:

 - (void)dealCategoryData:(NSArray *)categoryArray {
        //防止缓存数据导致显示重复。
        [_categoryMap removeAllObjects];
        [categoryArray enumerateObjectsUsingBlock:^(GBCategoryModel  * _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
            @autoreleasepool {
                /*
                 * 先扫描获取到的Model 分类数据
                 * 获取到当前 model的父节点, 判断_categoryMap是否存在对应子节点数组
                 * 如果_categoryMap中父节点key值不存在,创建一个父节点,key值为model.parentId, value为子节点数组
                 * 如果父节点存在,那么直接将model的值添加到数组里面。
                 * 最后,将所有第一层的节点连接到 _categoryRootKey 节点对应的数组中,完成此次数据解析。
                 */
                if ([_categoryMap objectForKey:obj.parentId]) {
                    //存在对应的key值
                    NSMutableArray *childArray = [_categoryMap objectForKey:obj.parentId];
                    [childArray addObject:obj];
                    [_categoryMap setObject:childArray forKey:obj.parentId];
                } else {  
                    //不存在对应父节点key值
                    NSMutableArray *newChildArray = [NSMutableArray array];
                    [newChildArray addObject:obj];
                    [_categoryMap setObject:newChildArray forKey:obj.parentId];
                }
            }
        }];
        //最后遍历一次数组,将对应的节点是否存在子节点进行标记
        [categoryArray enumerateObjectsUsingBlock:^(GBCategoryModel  *  _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
            if ([_categoryMap objectForKey:obj.catId]) {
                NSMutableArray *childArray = [_categoryMap objectForKey:obj.catId];
                obj.hasNext = (childArray != nil && childArray.count > 0) ? YES : NO;
            }
        }];
        _categoryRootKey = @"0";
    }

从pid为0看出,中国和纽约是顶级节点。

UI实现

  • 结构上分类顶部搜索栏,左边一级列表模块,右边二三级列表模块。
  • 左边实现一个UITableView,右边使用UICollectionView。
  • 通过点击UITableView中的cell,回调更新UICollectionView的数据源并显示。
  • UICollectionView可实现HearderView展示二级列表信息,cell布局排版显示三级列表信息。

因为贵州的pid是1,而中国的id为1,所以贵州的父节点是中国,至于type字段,可以不用管,只是我自己的项目需要。

重构心得

  • 本次重构该分类模块,通过算法的优化,在App端做到快速解析。自己并不想争论算法数据结构对于前端开发是否有用的问题,更多的对于自己而言只是一种尝试。当然也见过大多数App采用点击第一级分类再进行刷新请求的做法,这些均可根据实际业务场景进行选择,例如京东和淘宝貌似也是采用这种方式,当然服务器得足够快,那么也是完美的。对于服务器优化并不够完善的场景下,也可以采用这种将数据解析一步到位,并缓存和展示,或许只是牵强地提升那么一点性能吧。编码本该是种脑力思考的产物,而非体力劳动的成果,仁者见仁,智者见智。

可以发现,着写数据在数据表中是无序的,并没有我们想象中的层次结构分明并且可读性很好。

那么,当使用无限极分类之后数据的输出是怎样的呢?如下:

奥门新浦京官方网站 3

这样就能够很清晰的看出他们的层次结构了,那么这样的效果在thinkphp5.0是怎么实现的呢?

好了,贴出代码:

<?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;
    }
}

首先我们可以看到,在cateTree方法中我们通过select()方法获取到了数据库里面的所有数据,然后将数据传入到sort里面,此刻我们注意到sort有三个参数,pid表示当前节点的父节点的id,level表示当前节点

为几级。(顶级节点是0级,顶级节点的子节点是1级),那么level的用处到时候输出的时候会用到,此处不用纠结。

当数据传入sort方法之后,声明一个静态数组,保证每次递归调用的时候数组里面的数据不会改变,然后循环从数据库里面查询的数据。

$value的值表示数据库里面的一行,是一个数组,$value[‘名字’]表示一行里面的一个字段。

首先我们通过

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

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

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

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

举个例子:

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

奥门新浦京官方网站 4

 

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


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

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

奥门新浦京官方网站 5

 

当递归回来时,贵州出栈,此时栈空间里面保存的是中国的数据,包括pid为0这个变量,level为0这个变量,以及静态数组。当执行下一个循环时,$value[‘pid’]
== $pid

因为栈空间里面保存的pid是0,所以会找到北京这个数据。

奥门新浦京官方网站 6

 

接下来的步骤就差不多了,首先foreach循环天安门的子节点,发现没有子节点,递归结束,同时将sort($data,7,3)出栈,回到递归进入出,以上为例,则回到天安门那段代码的sort处,同时执行foreach循环,查找是否有其他的节点的pid为6,即查看北京下是否还有其他子节点。如果有,则将该节点的数据入栈,如果没有则出栈,回到北京那块代码的sort处,匹配pid为1的是否还有其他节点。如果没有则回到最开始的sort处,此时递归完全结束。

此刻我们来观察数组,可以看出,通过递归,数组里的数据开始变得有序起来,如贵州是中国的一级子节点,所以紧跟在中国之后,当第一轮递归结束,到了第二轮递归时,第一个找到的是北京,所以数组里面第三个元素是北京。

那怎么得到如下的格式化数据呢?

奥门新浦京官方网站 7

我们可以发现,北京和贵州的level是相同的,注意:我们的数组还保存得有level信息(图中的level有些错误,不建议大家参考)。

level数值大的前面的短线就越多,表示级数就越大。

那么这是怎么输出的呢?

                                        {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}

以上是thinkphp的模板标签,volist和foreach是一样的道理

通过后台分配而来的cateList数据(也就是上面的静态数组),通过

 <td><?php echo str_repeat("-",$cate["level"]*8)?>{$cate.cate_name}</td>
得到最终的结果。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注