TypeScript中怎么使用递归遍历并转换树形数据

发布时间:2021-11-15 15:11:11 作者:iii
来源:亿速云 阅读:215

本篇内容介绍了“TypeScript中怎么使用递归遍历并转换树形数据”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

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

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<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); }

效果还是蛮不错的

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

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

深度遍历

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

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

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

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

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);

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

遍历还没讲完

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

深度遍历生成节点

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

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

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

广度遍历生成节点

广度遍历的过程是把所有节点扁平化到一个队列中了,这个过程是不可逆 的,换句话说,我们在处理过程中丢掉了树形结构信息。然后我们要生成的 DOM  树,是需要结构信息的&mdash;&mdash;因此,需要将结构信息附加在每个节点上。这里我们把生成的 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/

“TypeScript中怎么使用递归遍历并转换树形数据”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站,小编将为大家输出更多高质量的实用文章!

推荐阅读:
  1. 使用递归遍历并转换树形数据(以 TypeScript 为例)
  2. 在TypeScript中如何使用RxJS

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

typescript

上一篇:Linux中比较好玩的命令有哪些

下一篇:基于Etcd和Raft的协调服务如何进行Golang实现

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》