使用递归遍历并转换树形数据(以 TypeScript 为例)

一、前言

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

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

奥门新浦京官方网站 1

一个朋友问我应该怎么从一个树的 JSON 数组生成 HTML,使用 <ul><li>
来构建页面元素。于是我简单的画了个树型结构图

步骤:

奥门新浦京官方网站,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。

奥门新浦京官方网站 2

总结:

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

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

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

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

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

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

哦对了。

$m=M('ztree');

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

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

image

然后写了对应的模拟数据(JavaScript 对象)

const data = {
    name: "A",
    nodes: [
        { name: "B", nodes: [{ name: "F" }] },
        { name: "C" },
        {
            name: "D",
            nodes: [
                { name: "G" },
                { name: "H" },
                { name: "I", nodes: [{ name: "J" }, { name: "K" }] }
            ]
        },
        { name: "E" }
    ]
};

最后写了一个递归,生成了 HTML 的树型结构。原本是用 JavaScript ES6
写的,为了表明数据结构,这里改用 TypeScript 来写:

interface INode {
    name: string;
    nodes?: INode[];
}

function makeTree(roots: INode[]): JQuery<HTMLElement> {
    function makeNode(node: INode): JQuery<HTMLElement> {
        const $div = $("<div>").text(node.name || "");
        const $li = $("<li>").append($div);
        if (node.nodes && node.nodes.length) {
            $li.append(makeNodeList(node.nodes));
        }
        return $li;
    }

    function makeNodeList(nodes: INode[]): JQuery<HTMLElement> {
        return nodes
            .map(child => makeNode(child))
            .reduce(($ul, $li) => {
                return $ul.append($li);
            }, $("<ul>"));
    }

    return makeNodeList(roots);
}

效果还是蛮不错的

奥门新浦京官方网站 3

image

看看源码(转译成 JS
之后的):http://jsfiddle.net/y7bw4yj2/

然后朋友说没看明白,好吧,那我从头讲起

遍历方法

树形数据的遍历有两种方法,大家都知道:广度遍历和深度遍历。一般情况下,广度遍历是采用队列来实现,而深度遍历刚更适合使用递归来实现。

奥门新浦京官方网站 4

image

广度遍历

从图上大致可以理解广度遍历的过程:

  1. 准备一个空队列;
  2. 将根(单根或多根均可)节点放到队列中;
  3. 从队列中取出一个节点
  4. 处理(比如打印)这个节点
  5. 检查节点的子节点,如果有,全部依次添加到队列中
  6. 回到第 3 步开始处理,直到队列为空(处理完成)

function travelWidely(roots: INode[]) {
    const queue: INode[] = [...roots];
    while (queue.length) {
        const node = queue.shift()!;
        // 打印节点名称及其子节点数
        console.log(`${node.name} ${node.nodes && node.nodes.length || ""}`);
        if (node.nodes && node.nodes.length) {
            queue.push(...node.nodes);
        }
    }
}

// 开始遍历
travelWidely([data]);

const node = queue.shift()!,这后面的 ! 后缀表示声明其结果不为
undefinednull。这是一个 TypeScript 语法。由于 .shift()
在数组中没有元素时会返回 undefined,所以其返回类型被声明为
INode | undefined,由于从逻辑可以保证 .shift()
一定会返回一个节点对象,所以这里用 ! 后缀忽略类型中的 undefined
部分,使 node 的类型被推导为 INode

代码里稍难理解一点的是要注意 queue 的内容和长度随时在变化。如果想使用
for 代替 while 循环,节点序号会因 .shift() 而不断变化,所以
i < queue.length 这样的判断是错误的。

深度遍历

深度遍历是一个递归过程,递归一直是编程的难点

递归是一个循环往复的处理过程,它有两个点需要注意:

  • 递归调用点,递归调用自己(或另一个可能会调用自己的函数)
  • 递归结束点,退出当前函数

以树节点为例,我们期望处理过程是处理(打印)一个树结点,即
printNode(node: INode)。那么它的

  • 递归调用点:如果该节点有子节点,依次对子节点调用
    printNode(children[i])
  • 递归结束点:处理完所有子节点(子节点数量是有限的,所以一定会结束)

用一段伪代码描述这一过程

function printNode(node: INode) {
    // 处理该节点
    console.log(node.name);

    // 递归调用点:循环对子节点调用 printNode
    node.nodes!.forEach(child => printNode(child));

    // 递归结束点:循环完成,return
}

上面两句代码就完成了递归过程,但实际上情况还要复杂些,因为要处理入口和容错。

// 注意参数支持传入单根或多根,
// 如果像 travelWidely 那样只支持多根(单根是特例)也是可以的
function travelDeeply(roots: INode | INode[]) {
    function printNode(node: INode) {
        console.log(`${node.name} ${node.nodes && node.nodes.length || ""}`);
        if (node.nodes && node.nodes.length) {
            // 依次对子节点递归调用 printNode
            node.nodes.forEach(child => printNode(child));
        }
    }

    // 这里 printNode 和 node => printNode(node) 等价
    (Array.isArray(roots) ? roots : [roots]).forEach(printNode);
}

// 开始遍历
travelDeeply(data);

关于递归,我正好在慕课网上讲生成数据解决方案的时候讲到了,有兴趣可以看看。

遍历还没讲完

上面两种遍历都讲到了,但是还没讲完——因为两种遍历都是以打印为例,而我们的目的是要生成
DOM 树。生成 DOM
树与纯打印信息的不同之处在于,我们不仅要使用节点信息,还要从节点信息生成
DOM 返回出来。

深度遍历生成节点

这次先讲深度遍历,因为递归更容易实现。递归本身具有层次信息,每进入一个递归调用点,就会深入一层,每离开一个递归结束点,就会减少一层。所以这个算法本身能够保留结构信息,相应代码也会更容易实现。而且在本文一开始,就已经实现出来了。

需要注意的一点是那段代码用了两个函数来完成递归过程:

  • makeNode 处理单个节点,它调用 makeNodeList 处理子节点列表
  • makeNodeList 遍历节点列表,分别对其调用 makeNode 来进行处理

makeNodemakeNodeList
的相互调用形成了递归,上述两条都是递归调用点,而递归结束点同样也有两条:

  • makeNode 处理的节点没有子节点时,不会调用 makeNodeList
  • makeNodeList 中的循环结束时,不会再调用 makeNode

广度遍历生成节点

广度遍历的过程是把所有节点扁平化到一个队列中了,这个过程是不可逆
的,换句话说,我们在处理过程中丢掉了树形结构信息。然后我们要生成的 DOM
树,是需要结构信息的——因此,需要将结构信息附加在每个节点上。这里我们把生成的
DOM 和数据节点绑定起来,由 DOM 保存结构信息。为此,需要修改一下节点类型

interface INode {
    name: string;
    nodes?: INode[];
    dom: JQuery;    // 附加生成的 DOM
}

function makeTreeWidely(roots: INode[]): JQuery {
    // 从一组节点生成 <ul>,为每个节点生成并附加 <li>,
    // 同时将 <li> 到到 <ul> 中保存结构信息
    function makeUl(nodes: INode[]) {
        return nodes
            .map(node => {
                const $li = $("<li>")
                    .append($("<div>").text(node.name || ""));
                node.dom = $li;
                return $li;
            })
            .reduce(($ul, $li) => $ul.append($li), $("<ul>"));
    }

    const $rootUl = makeUl(roots);

    const queue: INode[] = [...roots];
    while (queue.length) {
        const node = queue.shift()!;

        if (node.nodes && node.nodes.length) {
            const $ul = makeUl(node.nodes);
            node.dom.append($ul);
            queue.push(...node.nodes);
        }
    }
    return $rootUl;
}

虽然这里和上面讲递归遍历 printNode 的时候一样定义了局部函数表达式
makeUl,但这里没有递归,因为 makeUl 内部没有调用自身,或者某个会调用
makeUl 的函数。

但问题还是再深入一点,因为上面的代码改变了原数据。而一般情况下,我们应该尽量避免这样的副作用

没有副作用的广度遍历生成节点

// 声明一个新结构,它把 INode 和 DOM 组合在一起。
// 这个结构将代替 INode 作为队列的元素类型
interface IDomNode {
    node: INode;
    dom: JQuery;
}

function makeTreeWidely(roots: INode[]): JQuery {
    // convert 将节点数组转换为 IDomNode 数组,
    // 同时还干了原来 makeUl 干的事情,返回一个 $ul
    function convert(nodes: INode[]) {
        const domNodes = nodes
            .map(node => {
                const $li = $("<li>")
                    .append($("<div>").text(node.name || ""));
                return {
                    node,
                    dom: $li
                };
            });

        const $ul = domNodes
            .reduce(($ul, dn) => $ul.append(dn.dom), $("<ul>"));

        // 将两个数组组成一个元组(对象)返回
        return {
            domNodes,
            $ul
        };
    }

    // 解析元组,声明变量 queue 和 $rootUl,
    // 并分别将 domNodes 和 $ul 的值赋值给 queue 和 $rootUl 两个变量
    const { domNodes: queue, $ul: $rootUl } = convert(roots);

    while (queue.length) {
        const { node, dom } = queue.shift()!;

        if (node.nodes && node.nodes.length) {
            const { domNodes, $ul } = convert(node.nodes);
            dom.append($ul);
            queue.push(...domNodes);
        }
    }
    return $rootUl;
}

看疗效:http://jsfiddle.net/y7bw4yj2/1/

发表评论

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