JavaScript中树型结构的那些事

一、介绍

树是一种重要的非线性数据结构，直观地看，它的数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。相信大家在平时的开发中用过ztree或者其他的一些插件，去解决一写，人员部门树，文件树等一些平时业务，下边我们就来聊一下这些树，以及其中的操作。

树的展现形式：树有两种展现形式，一种是平行结构(简单结构)，pid和id的对应关系来组成树的，不容易看出包含关系，一种是树形结构,有children字段,可以看到明细显的包含关系。

var data = [
            { "id": 2, "name": "第一级1", "parent_id": 0 },
            { "id": 3, "name": "第一级1-1", "parent_id": 2 },
            { "id": 5, "name": "第一级1-1-1", "parent_id": 3},
            { "id": 100, "name": "第一级2", "parent_id":0 },
            { "id": 6, "name": "第一级2-1", "parent_id":100},
            { "id": 90, "name": "第一级2-1-1", "parent_id":6},
        ]

var data = [
            {
                "id": 2, "name": "第一级1", "parent_id": 0,
                children: [
                    {
                        "id": 3, "name": "第一级1", "parent_id": 2,
                        children:[
                            {"id": 5, "name": "第一级2", "parent_id": 3}
                        ]
                    }
                ]
            },
            { 
                "id": 100, "name": "第一级2", "parent_id": 0, 
                children: [
                    {
                        "id": 6, "name": "第一级2-1", "parent_id": 100,
                        children:[
                            {"id": 90, "name": "第一级2-1-1", "parent_id": 3}
                        ]
                    }
                ] 
            }
        ]

一、树形结构转化

1.平行结构转树形结构，比如elementUI tree是需要这种树形结构的。

function formatTree(data) {
            let parents = data.filter(value => value.parent_id == null || value.parent_id == 0);
            let children = data.filter(value => value.parent_id !== 'undefined' && value.parent_id !== null);
            //递归函数
            let translator = (parents, children) => {
                parents.forEach(parent => {
                    children.forEach((current, index) => {
                        if (current.parent_id === parent.id) {
                            let temp = JSON.parse(JSON.stringify(children));
                            temp.splice(index, 1)
                            translator([current], temp);
                            typeof parent.children != 'undefined' parent.children.push(current) :
                                parent.children = [current]
                        }
                    })
                });
            }
            translator(parents, children)
            return parents
        }

2.平行结构找某一父节点下的所有子节点

function sonsTree(arr, id) {
            var temp = [],
                lev = 0;
            var forFn = function (arr, id, lev) {
                for (var i = 0; i < arr.length; i++) {
                    var item = arr[i];
                    if (item.pid == id) {
                        item.lev = lev;
                        temp.push(item);
                        forFn(arr, item.id, lev + 1);
                    }
                }
            }
            forFn(arr, id, lev);
            return temp;
        }

3.寻找子节点的所有父节点(子节点的路径)

const data = [
            {
                id: 1,
                pid: 'a',
                text: 1,
                children: [{
                    id: 2,
                    pid: 'b',
                    text: 2,
                    children: [{
                        id: 3,
                        pid: 'c',
                        text: 3,
                        children: [{
                            id: 4,
                            pid: 'd',
                            text: 3,
                            children: []
                        },
                        {
                            id: 5,
                            pid: 'd2',
                            text: 3,
                            children: []
                        }]
                    }]
                }]
            }
        ]

        function findIndexArray(data, id, indexArray) {
            let arr = Array.from(indexArray)
            for (let i = 0, len = data.length; i < len; i++) {
                arr.push(data[i].pid)
                if (data[i].id === id) {
                    return arr
                }
                let children = data[i].children
                if (children && children.length) {
                    let result = findIndexArray(children, id, arr)
                    if (result) return result
                }
                arr.pop()
            }
            return false
        }

        console.log(findIndexArray(data, 5, [])) // [0, 0, 0]