网站建设资讯

NEWS

网站建设资讯

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

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

精河网站制作公司哪家好,找创新互联建站!从网页设计、网站建设、微信开发、APP开发、成都响应式网站建设公司等网站项目制作,到程序开发,运营维护。创新互联建站从2013年成立到现在10年的时间,我们拥有了丰富的建站经验和运维经验,来保证我们的工作的顺利进行。专注于网站建设就选创新互联建站

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

然后写了对应的模拟数据(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 {
    function makeNode(node: INode): JQuery {
        const $div = $("
").text(node.name || ""); const $li = $("
  • ").append($div); if (node.nodes && node.nodes.length) { $li.append(makeNodeList(node.nodes)); } return $li; } function makeNodeList(nodes: INode[]): JQuery { return nodes .map(child => makeNode(child)) .reduce(($ul, $li) => { return $ul.append($li); }, $("
      ")); } return makeNodeList(roots); }
  • 效果还是蛮不错的

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

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

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

    遍历方法

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

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

    广度遍历

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

    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 {
        // 从一组节点生成 
      ,为每个节点生成并附加
    • , // 同时将
    • 到到
        中保存结构信息 function makeUl(nodes: INode[]) { return nodes .map(node => { const $li = $("
      • ") .append($("
        ").text(node.name || "")); node.dom = $li; return $li; }) .reduce(($ul, $li) => $ul.append($li), $("
          ")); } 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 = $("
  • ") .append($("
    ").text(node.name || "")); return { node, dom: $li }; }); const $ul = domNodes .reduce(($ul, dn) => $ul.append(dn.dom), $("
      ")); // 将两个数组组成一个元组(对象)返回 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/


    当前文章:使用递归遍历并转换树形数据(以TypeScript为例)
    文章路径:http://njwzjz.com/article/pgcsig.html