Javascript 树结构数据转换，用循环代替递归防止栈溢出

PrototypeZ 发布于2019-08-22 18:23 / 2124人阅读

摘要：用循环代替递归防止栈溢出有些场景可能需要我们把平级的数据转换成树结构，例如这样的数据我们一般想到的就是一个递归就搞定，但是递归嵌套太多会出现性能问题。

用循环代替递归防止栈溢出

有些场景可能需要我们把平级的数据转换成树结构，例如：

let data = [
    { id: 1, pid: 0 },
    { id: 2, pid: 1 },
    { id: 3, pid: 2 },
    { id: 4, pid: 3 },
    { id: 5, pid: 3 },
    { id: 6, pid: 3 },
    { id: 4, pid: 10 },
    { id: 7, pid: 10 },
    { id: 10, pid: 20 }
]

这样的数据我们一般想到的就是一个递归就搞定，但是递归嵌套太多会出现性能问题。所有可以用循环来代替递归例如：

  function computedTree(treeData, id, pid) {
    let arr = []
    treeData.forEach((item, index) => {
        let isParent = false
        treeData.forEach(item2 => {
            if (item[pid] === item2[id]) {
                isParent = true
                !Array.isArray(item2.children) && (item2.children = [])
                item2.children.push(item)
            }
        })
        !isParent && arr.push(index)
    })
    return treeData.filter((item, index) => arr.indexOf(index) > -1)
}
let result = computedTree(data, "id", "pid")

console.log(JSON.stringify(result))

//result
[{"id": 1,"pid": 0,
    "children": [
        {"id": 2,"pid": 1,"children": [
            {"id": 3,"pid": 2,"children": [
                {"id": 4,"pid": 3}, 
                {"id": 5,"pid": 3}, 
                {"id": 6,"pid": 3}
            ]}
        ]}
    ]}, 
    {"id": 10,"pid": 20,"children": [{"id": 4,"pid": 10}, {"id": 7,"pid": 10}]
}]

这里的原理很简单，就是利用对象的浅拷贝，把所有子父关系做一个转换就得到结果。然后把没有父级的做为顶级返回就得到想要的数据，若不想污染数据源可先cloneDeep后再做计算，

GPU云服务器云服务器 js递归栈溢出 php递归获取树结构优化递归数据栈 python 栈溢出

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95803.html

数据结构和算法类面试题javascript代码实现

摘要：正文面试题重建二叉树题目输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。前序遍历序列为，中序遍历序列，。确定了左右子树后递归处理。方法方法面试题在时间删除链表结点。写在前面本文的题目均来自于剑指offer中的题目，题目序号保持了书中的题目序号，由于某些题目并不适合于javascript这种语言，所以这些题目就没有写在本篇博客中，因此会出现题目序号的中断。正文面试题6：...

Dean 2019-08-22 10:39 评论0 收藏0
Javascript执行机制--单线程，同异步任务，事件循环

摘要：如果过程中遇到引擎执行会被挂起线程，更新保存在一个队列中等待引擎空闲才执行引擎线程负责解析运行执行时间过程会导致页面渲染加载阻塞事件触发线程，浏览器用以控制事件循环。序总所周知，javascript是一门依赖宿主环境的单线程的弱脚本语言，这意味着什么？ javascript的运行环境一般都由宿主环境（如浏览器、Node、Ringo等）和执行环境（Javascript引擎V8，Ja...

gaomysion 2019-08-26 10:28 评论0 收藏0
【数据科学系统学习】Python # 编程基础[一]

摘要：在定义函数时给定的名称称作形参，在调用函数时你所提供给函数的值称作实参。调用函数要调用一个函数，需要知道函数的名称和参数。默认参数值可以有效帮助解决这一情况。是默认参数定义默认参数要牢记一点默认参数必须指向不变对象。关于数据科学在做什么，我们已经在前两篇文章中进行了总结，即专题概述和描述性统计分析。要进行数据科学的探索，需要一个好工具，就是Python。从本篇开始，将总结学习Pyth...

luckyyulin 2019-07-30 17:21 评论0 收藏0
[翻译] JS的递归与TCO尾调用优化

这两天搜了下JS递归的相关文章，觉得这篇文章很不错，就顺手翻译了下，也算给自己做个笔记，题目是我自己加的。原文很长，写得也很详尽，这里并非逐字翻译，而是作者所讲的主要概念加上我自己的一些理解，本文中解决方案的实际意义并不是特别大，但算法的逻辑挺有意思，不过也略抽象，理解需要花点时间（囧，估计我太闲了）文中的用例?全部来自原文：原文链接：（原题为：理解JS函数式编程中的递归）Underst...

pekonchan 2019-08-21 10:49 评论0 收藏0
小李飞刀：python你慢点飞，我的脑子还在后面追

摘要：默认参数设置默认参数时，有几点要注意一是必选参数在前，默认参数在后，否则的解释器会报错二是如何设置默认参数。注意此处，获得的其实是的拷贝，函数内对的改变不会影响到。使用递归函数需要注意防止栈溢出。总是在最前面的叨逼叨最近总是在想成长这两个很常常被提起的事情，这对于一个已经25岁的半中年而言，已经是一个不太能高频提起的词。但是，最近一些事情吧，总让我觉得我的生长期似乎比正常人来的晚了...

kevin 2019-07-30 18:40 评论0 收藏0