树转列表的实现思路与代码

denson 发布于2019-08-22 18:04 / 2772人阅读

摘要：背景之前写了一篇列表转树的文章，有列表转树的需求自然就会有树转列表的需求，这里我把树转列表的思路与代码再整理一下。总结树转列表过程中，我这里的深度优先采用了递归方式，可能会对内存占用较多，使用时请自行权衡。

背景

之前写了一篇列表转树的文章，有列表转树的需求自然就会有树转列表的需求，这里我把树转列表的思路与代码再整理一下。

思路分析

需求是什么？
老规矩，上图

先说一下整体思路，就是遍历树中的每一个节点，在遍历过程中要把节点的父节点id记录下来，并作为该节点的parentId属性值（保留层级关系，后续根据这个parentId和节点的id可以转回树结构），然后把该节点存入一个列表中。遍历过程完成，也就实现了把树结构转换成了列表结构。

树的遍历方式有两种，一种是深度优先遍历，一种是广度优先遍历，这两种方式思路如下图所示：

广度优先：

深度优先

思路看这两个图应该理得清楚了
我这里深度优先遍历采用了递归的方式，然后广度优先遍历采用了循环的方式。

执行步骤

先说深度优先吧：

从第一层开始遍历，遍历该层中所有节点，为每一个遍历到的节点添加上parentId属性，存入结果列表。

每一个遍历节点存入结果列表后，检测该节点是否存在子节点，如果存在，则将子节点作为数据源重复第一步

当所有的节点都处理完成后，整个树结构也就完成了转化

再说说广度优先：

从第一层开始遍历，遍历该层中所有节点，为每一个遍历到的节点添加上parentId属性，存入结果列表。

每一个遍历节点存入结果列表后，检测该节点是否存在子节点，如果存在，则将子节点数据项push到第一层遍历的列表中（这里相当于在for循环的过程中，修改了被遍历的数组的内容，在循环过程中把它变长了）

当所有的节点都处理完成后，整个树结构也就完成了转化

代码

深度优先

/*
* 深度优先遍历树
* 一个递归方法
* @params tree:要转换的树结构数据
* @params list:保存结果的列表结构数据，初始传[]
* @params parentId:当前遍历节点的父级节点id，初始为null(因为根节点无parentId)
* */
function toListDF (tree, list, parentId = null) {
    for (let node of tree) {
        list.push({
            id: node.id,
            name: node.name,
            children: [],
            parentId
        })
        if (node.children.length !== 0) {
            toList(node.children, list, node.id)
        }
    }
}

广度优先：

/*
* 广度优先遍历树
* 一层循环
* @params tree:要转换的树结构数据
* @output list:返回转换好的列表结构数据
* */
function toListBF (tree) {
    const tempList = tree.slice(0)
    const res = []
    for (let node of tempList) {
        // 向结果中push每一个节点的数据
        res.push({
            id: node.id,
            name: node.name,
            children: [],
            parentId: node.parentId === undefined ? null : node.parentId
        })
        // 如果该节点还有子节点，那么将子节点追加到待循环列表的后面
        if (node.children.length !== 0) {
            // 这里注意，push的是children里面的项
            tempList.push(...node.children.map((item) => {
                // 这里给每一项加上parentId
                item.parentId = node.id
                return item
            }))
        }
    }
    return res
}

这里给一个简单的树结构数据用来测试

const tree = [
    {
        id: 0,
        name: "root",
        children: [
            {
                id: 1,
                name: "child1",
                children: [
                    {
                        id: 4,
                        name: "child1-1",
                        children: []
                    },
                    {
                        id: 5,
                        name: "child1-2",
                        children: []
                    }
                ]
            },
            {
                id: 2,
                name: "child2",
                children: [
                    {
                        id: 6,
                        name: "child2-1",
                        children: [
                            {
                                id: 8,
                                name: "child2-1-1",
                                children: []
                            }
                        ]
                    }
                ]
            },
            {
                id: 3,
                name: "child3",
                children: [
                    {
                        id: 7,
                        name: "child3-1",
                        children: []
                    }
                ]
            }
        ]
    }
]

上面代码直接扔到浏览器中即可运行，可自行看看结果。

总结

树转列表过程中，我这里的深度优先采用了递归方式，可能会对内存占用较多，使用时请自行权衡。
在广度优先的方式中，只用了一层循环，这里有一个核心的点，就是js在循环列表过程中，被循环的列表是可以修改的，比如push一个数据项，这样会让for循环多运行一次，这个点理解之后，我这里的广度优先遍历树的方法就好理解了。

私有云 idc机房托管实现思路防ddos攻击软件思路实现 java代码优化思路栈的实现与应用

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

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

angular权限管理模块实现思路

摘要：菜单显示根据当前用户的菜单数据显示相应菜单权限埋点通过实现只支持控制显示隐藏操作，报错等需要自己实现管理模块参考界面：http://demo.jeesite.com/js/a/... 菜单管理列表页只实现增、删、改 showImg(https://segmentfault.com/img/bVbjeKu?w=1700&h=512); 新增菜单：去除归属模块字段，其他不变 showI...

galaxy_robot 2019-08-23 12:54 评论0 收藏0
Vue源码解析：AST语法树转render函数

摘要：源码解析这边解析的是从树转换成函数部分的源码，由于第一次提交的源码这部分不全，故做了部分更新，代码全在文件夹中。入口整个语法树转函数的起点是文件中的函数明显看到，函数传入参数为语法树，内部调用函数开始解析根节点容器节点。通过对 Vue2.0 源码阅读，想写一写自己的理解，能力有限故从尤大佬2016.4.11第一次提交开始读，准备陆续写：模版字符串转AST语法树 AST语法树转r...

trilever 2019-08-02 13:58 评论0 收藏0
Vue源码解析：AST语法树转render函数

摘要：源码解析这边解析的是从树转换成函数部分的源码，由于第一次提交的源码这部分不全，故做了部分更新，代码全在文件夹中。入口整个语法树转函数的起点是文件中的函数明显看到，函数传入参数为语法树，内部调用函数开始解析根节点容器节点。通过对 Vue2.0 源码阅读，想写一写自己的理解，能力有限故从尤大佬2016.4.11第一次提交开始读，准备陆续写：模版字符串转AST语法树 AST语法树转r...

Karuru 2019-08-23 14:21 评论0 收藏0
Vue源码解析：AST语法树转render函数

摘要：源码解析这边解析的是从树转换成函数部分的源码，由于第一次提交的源码这部分不全，故做了部分更新，代码全在文件夹中。入口整个语法树转函数的起点是文件中的函数明显看到，函数传入参数为语法树，内部调用函数开始解析根节点容器节点。通过对 Vue2.0 源码阅读，想写一写自己的理解，能力有限故从尤大佬2016.4.11第一次提交开始读，准备陆续写：模版字符串转AST语法树 AST语法树转r...

chanjarster 2019-08-05 15:51 评论0 收藏0
优化项目中树结构数据的操作

摘要：最近在优化一段代码，前端使用的是，页面中有一个树形菜单。我想的方法比较直接，一次性查出所有数据，减少查库的频率，毕竟数据量也就那么多条。最近在优化一段代码，前端使用的是Ext3，页面中有一个树形菜单。把项目放在本地跑，加载这个树形菜单的速度似乎还凑合，但是在正式环境中点开这个页面，这个树形菜单加载的就很慢了，很明显的感觉到卡壳了一下，于是去查看项目代码，大致思路是这样的，如下：通过...

cppowboy 2019-08-15 13:53 评论0 收藏0