结构化的树形结构转换为扁平的分支数组如何实现？不限语言，如 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);

Answer 3

也就循环遍历。

let arr = [];
for(let parent of tree){    //便于理解用的parent，实际开发换个变量名
    for(let sub of parent.children){
        arr.push([parent.name, sub.name]);
    }
}

Answer 4

不就是遍历一遍么，如果列出所有的话 BFS 和 DFS 都可以搞定。列出部分点的话用 DFS

思路供参考

function dfs (tree) {
  var result = []
  _search(tree, [])
  return result

  function _search (nodes, path) {
    if (!nodes || nodes.length <= 0) {
      return result.push(path.slice())
    }

    for (let i = 0; i < nodes.length; i++) {
      let node = nodes[i]
      path.push(node.name)
      _search(node.children, path)
      path.pop()
    }
  }
}