树是一种非散列数据结构，和非散列表一样，它对于存储需要快速查找的数据非常有用。

树是一种分层数据的抽象模型。现实生活中最常见的树的例子是家谱，或是公司的组织架构

本文将讲述一个实例，构造一棵树来实现数组和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"
  }
]

总结：树结构的形式有很多，不过还是会归结到树节点，树方法上。