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);
}
效果还是蛮不错的
看看源码(转译成 JS 之后的):http://jsfiddle.net/y7bw4yj2/ 点击预览
然后朋友说没看明白,好吧,那我从头讲起
遍历方法
树形数据的遍历有两种方法,大家都知道:广度遍历和深度遍历。一般情况下,广度遍历是采用队列来实现,而深度遍历刚更适合使用递归来实现。
广度遍历
从图上大致可以理解广度遍历的过程:
准备一个空队列;
将根(单根或多根均可)节点放到队列中;
从队列中取出一个节点
处理(比如打印)这个节点
检查节点的子节点,如果有,全部依次添加到队列中
回到第 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)
。那么它的
递归调用点:如果该节点有子节点,依次对子节点调用 printNode(children[i])
递归结束点:处理完所有子节点(子节点数量是有限的,所以一定会结束)
用一段伪代码描述这一过程
function printNode (node: INode ) {
console .log(node.name);
node.nodes!.forEach(child => printNode(child));
}
上面两句代码就完成了递归过程,但实际上情况还要复杂些,因为要处理入口和容错。
function travelDeeply (roots: INode | INode[] ) {
function printNode (node: INode ) {
console .log(`${node.name} ${node.nodes && node.nodes.length || ""} ` );
if (node.nodes && node.nodes.length) {
node.nodes.forEach(child => printNode(child));
}
}
(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;
}
function makeTreeWidely (roots: INode[] ): JQuery {
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
的函数。
但问题还是再深入一点,因为上面的代码改变了原数据。而一般情况下,我们应该尽量避免这样的副作用
没有副作用的广度遍历生成节点
interface IDomNode {
node: INode;
dom: JQuery;
}
function makeTreeWidely (roots: INode[] ): JQuery {
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
};
}
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 为例) 所遇到的问题。
如果觉得脚本宝典 网站内容还不错,欢迎将脚本宝典 推荐好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。 如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。