树结构使用实例---实现数组和树结构的转换
- 作者: 亖呉?盀
- 来源: 51数据库
- 2021-11-06
?
树是一种非散列数据结构，和非散列表一样，它对于存储需要快速查找的数据非常有用。
树是一种分层数据的抽象模型。现实生活中最常见的树的例子是家谱，或是公司的组织架构
本文将讲述一个实例，构造一棵树来实现数组和tree的相互转换，这在前端树结构中是经常遇到的。
需求场景：
将数组转化树结构，并将树结构转化为数组
数组
const list= [
{ id: 1001, parentId: 0, name: 'AA' },
{ id: 1002, parentId: 1001, name: 'BB' },
{ id: 1009, parentId: 1005, name: 'II' },
{ id: 1003, parentId: 1001, name: 'CC' },
{ id: 1004, parentId: 1003, name: 'DD' },
{ id: 1005, parentId: 1003, name: 'EE' },
{ id: 1006, parentId: 1002, name: 'FF' },
{ id: 1007, parentId: 1002, name: 'GG' },
{ id: 1008, parentId: 1004, name: 'HH' },
];
分析：
数组list是无规则排序的，不过分析过后，可以看到是一个通过parentId关联的树，那么如何实现呢？
树结构是一个对象，有一个root节点，并且有一系列的方法，比如插入节点，删除节点，获取节点，获取深度等等。
节点也是一个对象，有一定的属性，而且节点的属性也可能是其他的树。
那么我们可以先构造一个节点对象Node，每个Node有id, parentId, name, childNodes属性
构造一棵树listTree，先在数组中找到根节点（parentId === 0）
再给listTree添加list数组中的元素，知道添加完毕，就得到了树结构
实现步骤：
1，构造Node
class Node {
constructor(options){
let { id, parentId, name } = options
this.id = id || null;
this.parentId = parentId;
this.name = name || null;
this.childNodes = []
}
getId(){
return this.id;
}
...
}
2，构造树listTree
创建listTree时，初始化this.root，生成this.root（generateRoot）
由于在root上添加节点，所以增加了insertNode方法，插入时要找到root中对用的parentId
代码如下：
class listTree{
constructor(arr){
this.root = new Node(arr.find(item => item.parentId === 0))
this.generateRoot(arr)
}
generateRoot(arr){
// ...
}
getNodeById(id){
// ...
}
insertNode(node, id){
let targetNode = this.getNodeById(id)
// ...
}
// ...
}
3，完善listTree
getNodeById(id)：遍历this.root，找到对应元素，这里采取横向遍历，减少计算量
insertNode实现：根据要插入节点的parentId，找到父节点，然后把要插入的节点加入到父节点数组中
?generateRoot：每次向listTree树加入节点后，在目标数组中删除该元素，直到目标数组为空
代码如下：
class listTree{
constructor(arr){
this.root = new Node(arr.find(item => item.parentId === 0))
this.generateRoot(arr)
}
generateRoot(arr){
let arrRest = arr;
let self = this;
let rootIndex = arr.findIndex(item => item.parentId === 0)
arrRest.splice(rootIndex,1)
reduceArrRest()
function reduceArrRest(){
arrRest.forEach((node,index) => {
let result = self.insertNode(new Node(node),node.parentId)
if(result){
arrRest.splice(index,1)
}
})
// 有剩余的元素没有插入到树结构， 继续循环插入
if(arrRest.length > 0){
reduceArrRest()
}
}
}
getNodeById(id){
if(this.root && this.root.id === id){
return this.root
}
let targetNode = null;
compareNodeId(id,this.root.childNodes)
return targetNode;
function compareNodeId(id, NodeList){
// 在遍历下一个节点时，先判断是否已经找到targetNode
if(targetNode){
return targetNode
}
// 先遍历NodeList数组（采取的广度遍历）
for ( let node of NodeList){
if(node.id === id){
targetNode = node
break
}
}
// NodeList数组中没找到，再到NodeList每个node的child中查找
if(!targetNode){
for ( let node of NodeList){
if(node.childNodes.length>0){
compareNodeId(id,node.childNodes)
}
}
}
return targetNode
}
}
insertNode(node, id){
let targetNode = this.getNodeById(id)
if(targetNode){
targetNode.childNodes.push(node)
return true
} else {
return false
}
}
}
4, 实现树结构转化为数组
递归遍历树结构
class listTree{
constructor(arr){
this.root = new Node(arr.find(item => item.parentId === 0))
}
// ...
toArray(){
let list = [];
pushNode(this.root)
function pushNode(node){
let { id, parentId, name } = node;
list.push({id, parentId, name})
if(node.childNodes.length>0){
for ( let nodeItem of node.childNodes){
pushNode(nodeItem)
}
}
}
return list
}
}
以上就实现了基本的功能
demo
function listToTree(arr){
let ListTree = new listTree(arr)
console.log(JSON.stringify(ListTree.root,null, 2))
console.log(JSON.stringify(ListTree.toArray(),null,2))
}
listToTree(list)
运行结果：
树结构：
{
"id": 1001,
"parentId": 0,
"name": "AA",
"childNodes": [
{
"id": 1002,
"parentId": 1001,
"name": "BB",
"childNodes": [
{
"id": 1007,
"parentId": 1002,
"name": "GG",
"childNodes": []
},
{
"id": 1006,
"parentId": 1002,
"name": "FF",
"childNodes": []
}
]
},
{
"id": 1003,
"parentId": 1001,
"name": "CC",
"childNodes": [
{
"id": 1005,
"parentId": 1003,
"name": "EE",
"childNodes": [
{
"id": 1009,
"parentId": 1005,
"name": "II",
"childNodes": []
}
]
},
{
"id": 1004,
"parentId": 1003,
"name": "DD",
"childNodes": [
{
"id": 1008,
"parentId": 1004,
"name": "HH",
"childNodes": []
}
]
}
]
}
]
}
数组：
[
{
"id": 1001,
"parentId": 0,
"name": "AA"
},
{
"id": 1002,
"parentId": 1001,
"name": "BB"
},
{
"id": 1007,
"parentId": 1002,
"name": "GG"
},
{
"id": 1006,
"parentId": 1002,
"name": "FF"
},
{
"id": 1003,
"parentId": 1001,
"name": "CC"
},
{
"id": 1005,
"parentId": 1003,
"name": "EE"
},
{
"id": 1009,
"parentId": 1005,
"name": "II"
},
{
"id": 1004,
"parentId": 1003,
"name": "DD"
},
{
"id": 1008,
"parentId": 1004,
"name": "HH"
}
]
总结：树结构的形式有很多，不过还是会归结到树节点，树方法上。
推荐阅读
