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

Question

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. 要实现这样的需求有什么比较好的算法呢？

Answer 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));

Answer 2

我理解为需要 依次 输出从 顶点 到 每一个 终点节点 的路径 $json = "[{\"id\":1,\"name\":\"hello\",\"children\":[{\"id\":5,\"name\":\"bill gate\"},{\"id\":6,\"name\":\"jack ma\"}]},{\"id\":2,\"name\":\"world\",\"children\":[{\"id\":3,\"name\":\"foor\"},{\"id\":4,\"name\":\"bar\"}]}]"; $arrays = json_decode($json, true); define("NAME", "name"); $result = []; //存放結果 function tree($array){ static $path = []; global $result; array_push($path, $array[NAME]); foreach ($array['children'] as $index => $item){ if(isset($item['children']) && count($item['children']) > 0){ //如果非终点就继续递归执行 tree($item); }else{ array_push($path, $item[NAME]); $result[] = $path; array_pop($path); } } array_pop($path); } foreach ($arrays as $index => $array){ tree($array); } var_dump($result);