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

有朋友问我如何从树型JSON数组生成HTML，使用

和
• 构建页面元素。于是就简单的画了一个树结构图，写了对应的模拟数据（JavaScript对象）constdata={name:"A",nodes:[{name:"B",nodes:[{name:"F"}]},{名称：“C”}，{名称：“D”，节点：[{名称：“G”}，{名称：“H”}，{名称：“I”，节点：[{名称：“J”},{name:"K"}]}]},{name:"E"}]};***写一个递归生成HTML的树形结构。本来是用JavaScriptES6写的，为了展示数据结构，改用TypeScript写的：interfaceINode{name:string;nodes?:INode[];}functionmakeTree(roots:INode[]):JQuery{functionmakeNode（节点：INode）：JQuery{const$div=$("
  ").text(node.name||"");const$li=$("
• ").append($div);if(node.nodes&&node.nodes.length){$li.append(makeNodeList(node.nodes));}return$li;}functionmakeNodeList(nodes:INode[]):JQuery{returnnodes.map(child=>makeNode(child)).reduce(($ul,$li)=>{return$ul.append($li);},$("
  "));}returnmakeNodeList(根);}效果还不错。看源码（翻译成JS后）：http://jsfiddle.net/y7bw4yj2/然后朋友说没看懂。好吧，让我从头开始。遍历树数据的遍历方法有两种，大家都知道：广度遍历和深度遍历。一般来说，广度遍历是用队列来实现的，而深度遍历只是更适合用递归来实现。广度遍历广度遍历的过程可以从图中大致理解：准备一个空队列；将根（单根或多根）节点放入队列；从队列中取一个节点处理（比如打印）这个节点，检查该节点是否有子节点，一个一个添加到队列中，返回第3步开始处理，直到队列为空（处理为complete)functiontravelWidely(roots:INode[]){constqueue:INode[]=[...roots];while(queue.length){constnode=queue.shift()!;//打印节点名和子节点个数console.log(`${node.name}${node.nodes&&node.nodes.length||""}`);if(node.nodes&&node.nodes.length){queue.push(...node.nodes);}}}//开始遍历travelWidely([data]);constnode=queue.shift()!,the!这之后的后缀表示声明的结果不是undefined或null。这是一种TypeScript语法。由于.shift()在数组中没有元素时返回undefined，因此其返回类型声明为INode|不明确的。由于可以从逻辑上保证.shift()将返回一个节点对象，所以!这里使用后缀来忽略type的未定义部分，导致节点的类型被推导为INode。代码中有点难理解的是注意队列的内容和长度是随时变化的。如果要用for代替while循环，节点序号会因为.shift()而不断变化，所以iprintNode(child));//递归终点：循环完成，返回}上面两段代码完成了递归过程，但实际上由于需要处理入口和容错，情况更复杂。//注意参数支持传入单根或多根，//如果像travelWidely只支持多根（单根是特例），也可以functiontravelDeeply(roots:INode|INode[]){functionprintNode(node:INode){console.log(`${node.name}${node.nodes&&node.nodes.length||""}`);if(node.nodes&&node.nodes.length){//递归调用printNodenode。子节点上的节点依次.forEach(child=>printNode(child));}}//这里printNode和node=>printNode(node)是等价的(Array.isArray(roots)?roots:[roots])。forEach(printNode);}//开始遍历travelDeeply(data);关于递归，刚好在MOOC网站上讲生成数据方案的时候讲到。如果你有兴趣，你可以看看。遍历还没有结束。上面的两个遍历都说了，但是还没说完——因为这两个遍历都是以打印为例，而我们的目的是为了生成一棵DOM树。生成DOM树与单纯打印信息的区别在于，我们不仅使用了节点信息，还根据节点信息生成DOM并返回。深度遍历生成节点这次先说深度遍历，因为递归比较容易实现。递归本身具有层次信息。每进入一个递归调用点，就往深一层，每离开一个递归终点，就减少一层。所以算法本身可以保留结构信息，相应的代码也更容易实现。而在本文开头，已经实现了。需要注意的是，代码使用了两个函数来完成递归过程：makeNode处理单个节点，调用makeNodeList处理子节点列表makeNodeList遍历节点列表，调用makeNode处理每个节点。makeNode和makeNodeList的相互调用形式除了递归之外，以上两个都是递归的调用点，还有两个递归的终点：当makeNode处理的节点没有子节点时，makeNodeList不会被调用。当makeNodeList中的循环结束后，就不会再调用makeNode遍历生成的节点了。广度遍历的过程就是把所有的节点压平成一个队列。这个过程是不可逆的。换句话说，我们在处理过程中丢失了树结构信息。那么我们要生成的DOM树就需要结构信息——因此，结构信息需要附加到每个节点上。这里我们将生成的DOM与数据节点进行绑定，DOM保存结构信息。为此，需要修改节点类型interfaceINode{name:string;nodes?:INode[];dom:JQuery;//额外生成DOM}functionmakeTreeWidely(roots:INode[]):JQuery{//generatedfrom一组节点
  ，为每个节点生成并附加
  • ，//同时将
  • 放入
    中保存结构信息functionmakeUl(nodes:INode[]){returnnodes.map(node=>{const$li=$("
    • ").append($("
      ").text(node.name||""));node.dom=$li;return$li;}).reduce(($ul,$li)=>$ul.append($li),$("

      "));}const$rootUl=makeUl(roots);constqueue:INode[]=[...roots];while(queue.length){constnode=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的一些函数。但是问题有点深，因为上面的代码改变了原始数据。而一般情况下，我们应该尽量避免这样的副作用Breadthtraversalwithoutsideeffectsgeneratenode//声明一个结合了INode和DOM的新结构。//这个结构将替换INode作为队列接口的元素类型IDomNode{node:INode;dom:JQuery;}functionmakeTreeWidely(roots:INode[]):JQuery{//将节点数组转换为IDomNode数组，//也同时干掉原来makeUl做了什么，返回一个$ulfunctionconvert(nodes:INode[]){constdomNodes=nodes.map(node=>{const$li=$("
      • ").append($("
        ").text(node.name||""));return{node,dom:$li};});const$ul=domNodes.reduce(($ul,dn)=>$ul.append(dn.dom),$("

        "));//将两个数组组成一个元组（对象）returnreturn{domNodes,$ul};}//解析元组，声明变量队列和$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);队列.push(...domNodes);}}return$rootUl;}见疗效：http://jsfiddle.net/y7bw4yj2/1/

      上一篇：厦门儿童医院与锐捷态势感知构筑“安全护城河”

      下一篇：Linux-Mac系统下使用命令行工具创建网站备份
      使用递归遍历和转换树型数据（以TypeScript为例）相关文章