欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

树结构使用实例---实现数组和树结构的转换

程序员文章站 2022-06-24 12:10:06
树是一种非散列数据结构,和非散列表一样,它对于存储需要快速查找的数据非常有用。树是一种分层数据的抽象模型。现实生活中最常见的树的例子是家谱,或是公司的组织架构本文将讲述一个实例,构造一棵树来实现数组和tree的相互转换,这在前端树结构中是经常遇到的。需求场景:将数组转化树结构,并将树结构转化为数组数组const list= [ { id: 1001, parentId: 0, name: 'AA' }, { id: 1002, parentId: 1001, ......

 

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

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

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

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

本文地址:https://blog.csdn.net/qdmoment/article/details/107438747