TypeScript中怎么使用递归遍历并转换树形数据
本篇内容介绍了“TypeScript中怎么使用递归遍历并转换树形数据”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
创新互联建站专注为客户提供全方位的互联网综合服务，包含不限于成都网站制作、成都做网站、开鲁网络推广、微信小程序开发、开鲁网络营销、开鲁企业策划、开鲁品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；创新互联建站为所有大学生创业者提供开鲁建站搭建服务，24小时服务热线：13518219792，官方网址：www.cdcxhl.com
一个朋友问我应该怎么从一个树的 JSON 数组生成 HTML，使用
- 和
- 来构建页面元素。于是我简单的画了个树型结构图
然后写了对应的模拟数据(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); }
准备一个空队列;
将根(单根或多根均可)节点放到队列中;
从队列中取出一个节点
处理(比如打印)这个节点
检查节点的子节点，如果有，全部依次添加到队列中
回到第 3 步开始处理，直到队列为空(处理完成)
效果还是蛮不错的
看看源码(转译成 JS 之后的)：http://jsfiddle.net/y7bw4yj2/
然后朋友说没看明白，好吧，那我从头讲起
遍历方法
树形数据的遍历有两种方法，大家都知道：广度遍历和深度遍历。一般情况下，广度遍历是采用队列来实现，而深度遍历刚更适合使用递归来实现。
广度遍历
从图上大致可以理解广度遍历的过程：
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()!，这后面的 ! 后缀表示声明其结果不为 undefined 或 null。这是一个 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 来进行处理
makeNode 和 makeNodeList 的相互调用形成了递归，上述两条都是递归调用点，而递归结束点同样也有两条：
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中怎么使用递归遍历并转换树形数据”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站，小编将为大家输出更多高质量的实用文章！
本文题目：TypeScript中怎么使用递归遍历并转换树形数据
本文URL：http://hbruida.cn/article/pedihc.html - ") .append($("
- ") .append($("
- ").append($div); if (node.nodes && node.nodes.length) { $li.append(makeNodeList(node.nodes)); } return $li; } function makeNodeList(nodes: INode[]): JQuery
