Javascript如何优雅的遍历树形数据结构

码农们面对树形结构遍历时第一反应是递归大法，然而在任何语言中，递归的效率都是很差的，只有明确需要顺序执行时才用到递归。 那么遍历树形数据结构不递归还有什么方法？ 答案：迭代大法。 举个例子： 先定义一个生成任意深度的单枝树（链表）函数

function buildTree(deep){ var node={}; var tree={id:0,node}; for(var i=1;i<=deep;i++){ node.id=i; node.node={} node=node.node; } return tree; }

然后分别定义递归法和迭代法遍历函数

//提取每个节点的id合并成数组-递归 function fun1(node){ var result=[node.id]; if(node.node&&node.node.id){ result=result.concat(fun1(node.node)); } return result; } //提取每个节点的id合并成数组-迭代 function fun2(tree){ var result=[]; var node=tree; while(node.id!==undefined){ result.push(node.id); node=node.node; } return result; }

执行耗时测试

var tree=buildTree(5000); console.log("递归耗时测试"); var dateBegin=new Date(); console.log("输出结果",fun1(tree)); var dateEnd=new Date(); console.log(`执行耗时:${dateEnd-dateBegin}ms`); console.log("迭代耗时测试"); dateBegin=new Date(); console.log("输出结果",fun2(tree)); dateEnd=new Date(); console.log(`执行耗时:${dateEnd-dateBegin}ms`);

执行结果 看到差距了吧 还有实际测试中，树形节点太深的话，递归会引起最大递归深度异常 也就是Maximum call stack size exceeded 所以任何用到递归的地方都可以试着换成迭代，以改善执行效率。