结构化的树形结构转换为扁平的分支数组如何实现？不限语言，如 PHP JavaScript

问题描述

问 题

1. 最近需要实现一个功能，需要把一个树形结构的数据打散成包含最小分支数目的数组结构。描述起来别扭，还是举栗子吧：

以 JavaScript 为例：其中，id 为主键，parent 为该对象对应的父级元素ID

let tree = [
    {
        id:1,
        parent:0,
        name:'hello',
        children:[
            {
                id:5,
                parent:1,
                name:'bill gate',
                children:[]
            },
            {
                id:6,
                parent:1,
                name:'jack ma',
                children:[]
            }
        ]
    },
    {
        id:2,
        parent:0,
        name:'world',
        children:[
            {
                id:3,
                parent:2,
                name:'foo',
                children:[]
            },
            {
                id:4,
                parent:2,
                name:'bar',
                children:[]
            }
        ]
    }
];

上面的数组比较简单，因为每个元素的子元素个数和深度是一样的，但实际上的需求是变动是非常大的，最明显的使用场景是权限树，权限树涉及到的数据层级是不确定的，相邻的两个元素的子元素层级都可能会不同，这样的场景会比上面的例子复杂得多，其实这里可以考虑递归，复杂的数据结构如下：

let tree = [
    {
        id: 1,
        parent: 0,
        name: 'hello',
        children: [
            {
                id: 5,
                parent: 1,
                name: 'bill gate',
                children: []
            },
            {
                id: 6,
                parent: 1,
                name: 'jack ma',
                children: []
            }
        ]
    },
    {
        id: 2,
        parent: 0,
        name: 'world',
        children: [
            {
                id: 3,
                parent: 2,
                name: 'foo',
                children: [
                    {
                        id: 7,
                        parent: 3,
                        name: 'tom',
                        children: []
                    },
                    {
                        id: 8,
                        parent: 3,
                        name: 'jerry',
                        children: [
                            {
                                id: 9,
                                name: 'peter'
                            }
                        ]
                    }
                ]
            },
            {
                id: 4,
                parent: 2,
                name: 'bar',
                children: []
            }
        ]
    }
];

上面的两个样本数组，对其进行处理后我们期望得到的结果应该分别如下：可以理解为对一个族谱进行拆分，每一个分支一个数组，这样，一个族谱有多少个分支，最终生成的数组就有多少个元素。

例子一：
[
    ['hello','bill gate'],
    ['hello','jack ma'],
    ['world','foo'],
    ['world','bar']
]

例子二：
[
    ['hello','bill gate'],
    ['hello','jack ma'],
    ['world','foo'，'tom'],
    ['world','foo','jerry','peter'],
    ['world','bar']
]

1. 要实现这样的需求有什么比较好的算法呢？

解决方案

递归遍历

let tree = [
    {
        id: 1,
        parent: 0,
        name: 'hello',
        children: [
            {
                id: 5,
                parent: 1,
                name: 'bill gate',
                children: []
            },
            {
                id: 6,
                parent: 1,
                name: 'jack ma',
                children: []
            }
        ]
    },
    {
        id: 2,
        parent: 0,
        name: 'world',
        children: [
            {
                id: 3,
                parent: 2,
                name: 'foo',
                children: [
                    {
                        id: 7,
                        parent: 3,
                        name: 'tom',
                        children: []
                    },
                    {
                        id: 8,
                        parent: 3,
                        name: 'jerry',
                        children: [
                            {
                                id: 9,
                                parent: 8,
                                name: 'peter',
                                children: []
                            }
                        ]
                    }
                ]
            },
            {
                id: 4,
                parent: 2,
                name: 'bar',
                children: []
            }
        ]
    }
];

function treeToPath(tree, path, currentPath) {
    var currentPath = currentPath || [];
    var path = path || [];

    for(let i = 0; i < tree.length; i++) {
        if(i !== 0) {
            currentPath.pop();
        }

        currentPath.push(tree[i].name);

        if(tree[i].children.length) {
            treeToPath(tree[i].children, path, currentPath);
        }else {
            path.push(currentPath.slice(0));
        }
    }

    currentPath.pop();

    return path;
}

console.log(treeToPath(tree));

这篇关于结构化的树形结构转换为扁平的分支数组如何实现？不限语言，如 PHP JavaScript的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！