python 树结构 转换 list

python 树结构 转换 list

背景

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

思路分析

需求是什么？

老规矩，上图

先说一下整体思路，就是遍历树中的每一个节点，在遍历过程中要把节点的父节点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循环多运行一次，这个点理解之后，我这里的广度优先遍历树的方法就好理解了。