简单的遍历一个树形结构数据的几种方法、非递归方法效率最好。
(function (window, undefined) { var treeNodes = [ { id: 1, name: "1", children: [ { id: 11, name: "11", children: [ { id: 111, name: "111", children:[] }, { id: 112, name: "112" } ] }, { id: 12, name: "12", children: [] } ], users: [] }, { id: 2, name: "2", children: [ { id: 22, name: "22", children: [] } ] } ]; //递归实现 var parseTreeJson = function(treeNodes){ if (!treeNodes || !treeNodes.length) return; for (var i = 0, len = treeNodes.length; i < len; i++) { var childs = treeNodes[i].children; console.log(treeNodes[i].id); if(childs && childs.length > 0){ parseTreeJson(childs); } } }; console.log("------------- 递归实现 ------------------"); parseTreeJson(treeNodes); //非递归广度优先实现 var iterator1 = function (treeNodes) { if (!treeNodes || !treeNodes.length) return; var stack = []; //先将第一层节点放入栈 for (var i = 0, len = treeNodes.length; i < len; i++) { stack.push(treeNodes[i]); } var item; while (stack.length) { item = stack.shift(); console.log(item.id); //如果该节点有子节点,继续添加进入栈底 if (item.children && item.children.length) { //len = item.children.length; // for (i = 0; i < len; i++) { // stack.push(item.children[i]); // } stack = stack.concat(item.children); } } }; console.log("------------- 非递归广度优先实现 ------------------"); iterator1(treeNodes); //非递归深度优先实现 var iterator2 = function (treeNodes) { if (!treeNodes || !treeNodes.length) return; var stack = []; //先将第一层节点放入栈 for (var i = 0, len = treeNodes.length; i < len; i++) { stack.push(treeNodes[i]); } var item; while (stack.length) { item = stack.shift(); console.log(item.id); //如果该节点有子节点,继续添加进入栈顶 if (item.children && item.children.length) { // len = item.children.length; // for (; len; len--) { // stack.unshift(item.children[len - 1]); // } stack = item.children.concat(stack); } } }; console.log("------------- 非递归深度优先实现 ------------------"); iterator2(treeNodes); })(window);
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/91521.html
前天面试遇到一个多叉树面试的题目,在这里分享记录一下。 题目:一个树形的数据(如下数据),面试官给你一个id,然后拿到对应的name? 数据结构大概是这个样子 var cityData = [ { id: 1, name: 广东省, children: [ { id: 11, ...
摘要:树中结点的最大层次称为树的深度或高度。二叉树有深度遍历和广度遍历,深度遍历有前序中序和后序三种遍历方法。二叉树的前序遍历可以用来显示目录结构等中序遍历可以实现表达式树,在编译器底层很有用后序遍历可以用来实现计算目录内的文件及其信息等。 树的简介 栈、队列、链表等数据结构,都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地,树型结构是以分支关系定义的层次结...
阅读 2906·2021-11-24 09:39
阅读 2831·2021-09-29 09:34
阅读 3513·2021-09-24 10:23
阅读 1695·2021-09-22 15:41
阅读 1670·2019-08-30 15:55
阅读 3479·2019-08-30 13:58
阅读 2575·2019-08-30 13:11
阅读 1632·2019-08-29 12:31