135-1821-9792

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

一个朋友问我应该怎么从一个树的 JSON 数组生成 HTML，使用

    和
  • 来构建页面元素。于是我简单的画了个树型结构图

    创新互联长期为上1000家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为香洲企业提供专业的网站建设、成都网站设计，香洲网站改版等技术服务。拥有十多年丰富建站经验和众多成功案例,为您定制开发。

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

     
 
 
 
      
  
  
  
  
    1. const data = {
      2. 
  
  
  
  
    2.     name: "A",
      3. 
  
  
  
  
    3.     nodes: [
      4. 
  
  
  
  
    4.         { name: "B", nodes: [{ name: "F" }] },
      5. 
  
  
  
  
    5.         { name: "C" },
      6. 
  
  
  
  
    6.         {
      7. 
  
  
  
  
    7.             name: "D",
      8. 
  
  
  
  
    8.             nodes: [
      9. 
  
  
  
  
    9.                 { name: "G" },
      10. 
  
  
  
  
    10.                 { name: "H" },
      11. 
  
  
  
  
    11.                 { name: "I", nodes: [{ name: "J" }, { name: "K" }] }
      12. 
  
  
  
  
    12.             ]
      13. 
  
  
  
  
    13.         },
      14. 
  
  
  
  
    14.         { name: "E" }
      15. 
  
  
  
  
    15.     ]
      16. 
  
  
  
  
    16. }; 
      17.

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

     
 
 
 
      
  
  
  
  
    1. interface INode {
      2. 
  
  
  
  
    2.     name: string;
      3. 
  
  
  
  
    3.     nodes?: INode[];
      4. 
  
  
  
  
    4. }
      5. 
  
  
  
  
    5. 
  
  
  
  
    6. function makeTree(roots: INode[]): JQuery {
      7. 
  
  
  
  
    7.     function makeNode(node: INode): JQuery {
      8. 
  
  
  
  
    8.         const $div = $("
      ").text(node.name || "");
      9. 
  
  
  
  
    9.         const $li = $("
    10. ").append($div);
      11. 
  
  
  
  
    11.         if (node.nodes && node.nodes.length) {
      12. 
  
  
  
  
    12.             $li.append(makeNodeList(node.nodes));
      13. 
  
  
  
  
    13.         }
      14. 
  
  
  
  
    14.         return $li;
      15. 
  
  
  
  
    15.     }
      16. 
  
  
  
  
    16. 
  
  
  
  
    17.     function makeNodeList(nodes: INode[]): JQuery {
      18. 
  
  
  
  
    18.         return nodes
      19. 
  
  
  
  
    19.             .map(child => makeNode(child))
      20. 
  
  
  
  
    20.             .reduce(($ul, $li) => {
      21. 
  
  
  
  
    21.                 return $ul.append($li);
      22. 
  
  
  
  
    22.             }, $("
        "));
  
  
  
  
      •     }
        • 
  
  
  
  
      • 
  
  
  
  
      •     return makeNodeList(roots);
        • 
  
  
  
  
      • } 
        •

    效果还是蛮不错的

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

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

    遍历方法

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

    广度遍历

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

    1. 准备一个空队列;
    2. 将根(单根或多根均可)节点放到队列中;
    3. 从队列中取出一个节点
    4. 处理(比如打印)这个节点
    5. 检查节点的子节点，如果有，全部依次添加到队列中
    6. 回到第 3 步开始处理，直到队列为空(处理完成)
     
 
 
 
      
  
  
  
  
    1. function travelWidely(roots: INode[]) {
      2. 
  
  
  
  
    2.     const queue: INode[] = [...roots];
      3. 
  
  
  
  
    3.     while (queue.length) {
      4. 
  
  
  
  
    4.         const node = queue.shift()!;
      5. 
  
  
  
  
    5.         // 打印节点名称及其子节点数
      6. 
  
  
  
  
    6.         console.log(`${node.name} ${node.nodes && node.nodes.length || ""}`);
      7. 
  
  
  
  
    7.         if (node.nodes && node.nodes.length) {
      8. 
  
  
  
  
    8.             queue.push(...node.nodes);
      9. 
  
  
  
  
    9.         }
      10. 
  
  
  
  
    10.     }
      11. 
  
  
  
  
    11. }
      12. 
  
  
  
  
    12. 
  
  
  
  
    13. // 开始遍历
      14. 
  
  
  
  
    14. travelWidely([data]); 
      15.

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

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

    深度遍历

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

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

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

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

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

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

     
 
 
 
      
  
  
  
  
    1. function printNode(node: INode) {
      2. 
  
  
  
  
    2.     // 处理该节点
      3. 
  
  
  
  
    3.     console.log(node.name);
      4. 
  
  
  
  
    4.     
      5. 
  
  
  
  
    5.     // 递归调用点：循环对子节点调用 printNode
      6. 
  
  
  
  
    6.     node.nodes!.forEach(child => printNode(child));
      7. 
  
  
  
  
    7.     
      8. 
  
  
  
  
    8.     // 递归结束点：循环完成，return
      9. 
  
  
  
  
    9. } 
      10.

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

     
 
 
 
      
  
  
  
  
    1. // 注意参数支持传入单根或多根，
      2. 
  
  
  
  
    2. // 如果像 travelWidely 那样只支持多根（单根是特例）也是可以的
      3. 
  
  
  
  
    3. function travelDeeply(roots: INode | INode[]) {
      4. 
  
  
  
  
    4.     function printNode(node: INode) {
      5. 
  
  
  
  
    5.         console.log(`${node.name} ${node.nodes && node.nodes.length || ""}`);
      6. 
  
  
  
  
    6.         if (node.nodes && node.nodes.length) {
      7. 
  
  
  
  
    7.             // 依次对子节点递归调用 printNode
      8. 
  
  
  
  
    8.             node.nodes.forEach(child => printNode(child));
      9. 
  
  
  
  
    9.         }
      10. 
  
  
  
  
    10.     }
      11. 
  
  
  
  
    11. 
  
  
  
  
    12.     // 这里 printNode 和 node => printNode(node) 等价
      13. 
  
  
  
  
    13.     (Array.isArray(roots) ? roots : [roots]).forEach(printNode);
      14. 
  
  
  
  
    14. }
      15. 
  
  
  
  
    15. 
  
  
  
  
    16. // 开始遍历
      17. 
  
  
  
  
    17. travelDeeply(data); 
      18.

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

    遍历还没讲完

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

    深度遍历生成节点

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

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

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

    makeNode 和 makeNodeList 的相互调用形成了递归，上述两条都是递归调用点，而递归结束点同样也有两条：

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

    广度遍历生成节点

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

     
 
 
 
      
  
  
  
  
    1. interface INode {
      2. 
  
  
  
  
    2.     name: string;
      3. 
  
  
  
  
    3.     nodes?: INode[];
      4. 
  
  
  
  
    4.     dom: JQuery;    // 附加生成的 DOM
      5. 
  
  
  
  
    5. } 
      6. 
 
 
 
 
     
 
 
 
      
  
  
  
  
    1. function makeTreeWidely(roots: INode[]): JQuery {
      2. 
  
  
  
  
    2.     // 从一组节点生成 
        ，为每个节点生成并附加 
      • ，
        • 
  
  
  
  
      •     // 同时将 
      •  到到 
           中保存结构信息
  
  
  
  
        •     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 的函数。

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

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

     
 
 
 
      
  
  
  
  
    1. // 声明一个新结构，它把 INode 和 DOM 组合在一起。
      2. 
  
  
  
  
    2. // 这个结构将代替 INode 作为队列的元素类型
      3. 
  
  
  
  
    3. interface IDomNode {
      4. 
  
  
  
  
    4.     node: INode;
      5. 
  
  
  
  
    5.     dom: JQuery;
      6. 
  
  
  
  
    6. }
      7. 
  
  
  
  
    7. 
  
  
  
  
    8. function makeTreeWidely(roots: INode[]): JQuery {
      9. 
  
  
  
  
    9.     // convert 将节点数组转换为 IDomNode 数组，
      10. 
  
  
  
  
    10.     // 同时还干了原来 makeUl 干的事情，返回一个 $ul
      11. 
  
  
  
  
    11.     function convert(nodes: INode[]) {
      12. 
  
  
  
  
    12.         const domNodes = nodes
      13. 
  
  
  
  
    13.             .map(node => {
      14. 
  
  
  
  
    14.                 const $li = $("
    15. ")
      16. 
  
  
  
  
    16.                     .append($("
      ").text(node.name || ""));
      17. 
  
  
  
  
    17.                 return {
      18. 
  
  
  
  
    18.                     node,
      19. 
  
  
  
  
    19.                     dom: $li
      20. 
  
  
  
  
    20.                 };
      21. 
  
  
  
  
    21.             });
      22. 
  
  
  
  
    22. 
  
  
  
  
    23.         const $ul = domNodes
      24. 
  
  
  
  
    24.             .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://www.wtcwzsj.com/article/cojoghs.html

其他资讯


关于我们
我们的服务
网站建设案例
新闻动态
联系我们

135-1821-9792

公司服务热线
友情链接： 联通机柜租用   广汉锦华   联通机房服务器托管   深圳纱窗安装   抖音短视频   定制网站开发   成都奔驰发电机   成都发电机组租赁   gabanjia.cn   锦江区公司注册   

Copyright © 2009-2022 www.wtcwzsj.com 青羊区广皓图文设计工作室（个体工商户） 版权所有　蜀ICP备19037934号