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

Question

最近需要实现一个功能，需要把一个树形结构的数据打散成包含最小分支数目的数组结构。描述起来别扭，还是举栗子吧： 以 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'] ] 要实现这样的需求有什么比较好的算法呢？

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