【算法框架套路】找出给定数据中所有的树

• 2021 年 9 月 22 日
• 笔记
• 算法

需求

给定一维勾选的数据，导出多棵树结构，并给出每个节点的层级
例如，用户在下面的界面勾选了

这里包含了4棵树

问题来了，我们只有下面的一维列表数据，得根据这样的数据判断出所有的节点关系，构造出这4棵树

[
    {"id":481412, "name":"重庆","parent_id":438556},
    {"id":483065, "name":"税务局","parent_id":483060},
    {"id":483070, "name":"OAO税务局创新答评超越班","parent_id":483065},
    {"id":483072, "name":"OAO税务局创新答评综训班","parent_id":483065},
    {"id":486913, "name":"直播陪学-02期","parent_id":483072},
    {"id":490097, "name":"测试","parent_id":481412},
    {"id":490687, "name":"互动点拨班-特价","parent_id":481412},
    {"id":526061, "name":"贵州","parent_id":438556},
    {"id":526062, "name":"21年贵州省国考8晚督学课","parent_id":526061},
    {"id":492801, "name":"重大合作课","parent_id":481412}
]

之前写过一篇套路【算法框架套路】构造无限级树型结构，附上python/golang/php/js实现，但是，那个只适合于构造一棵树，这次是多棵。

实现

因为这个需求是PHP的，这次用PHP实现一下

/**
 * 根据列表计算出所有的树
 *
 * @param $list
 * @return array
 */
function getTreeList($list)
{
    //1.构造树节点的链Map
    $map = getTreeLinklistMap($list);

    //2.筛选出所有顶层父节点
    $treeList = [];
    foreach ($map as $v) {
        //如果有父亲不追加，只追加父节点
        if (isset($v['id']) && !empty($map[$v['parent_id']])) {
            continue;
        }
        //如果没有id，说明没有父节点，children数组元素各为一棵独立的树
        if (!isset($v['id'])) {
            foreach ($v['children'] as $node) {
                $treeList[] = $node;
            }
            continue;
        }
        //有id有children，为一棵独立的树
        $treeList[] = $v;
    }
    //3.计算每个节点的层级
    addLevel($treeList);;
    return $treeList;
}

/**
 * 根据列表，计算出所有的节点之间的串联关系
 *
 * @param $list
 * @return array
 */
function getTreeLinklistMap($list)
{
    $map = [];
    foreach ($list as &$v) {
        $id = $v['id'];
        $itemParentId = $v['parent_id'];
        if (isset($map[$id])) {
            $v['children'] = &$map[$id]['children'];
            $map[$id] = $v;
        } else {
            $v['children'] = [];
            $map[$id] = $v;
        }
        if (isset($map[$itemParentId])) {
            $map[$itemParentId]['children'][] = &$map[$id];
        } else {
            $map[$itemParentId] = ['children' => [&$map[$id]]];
        }
    }
    return $map;
}


/**
 * 给每个节点增加层级
 *
 * @param $treeList
 * @param int $level
 */
function addLevel(&$treeList, $level = 0)
{
    foreach ($treeList as &$v) {
        $v['level'] = $level;
        if (!empty($v['children'])) {
            addLevel($v['children'], $level + 1);
        }
    }
}

getTreeList是我们要调用的方法，其中用了两个辅助方法

• getTreeLinklistMap。迭代构造出[ id => children: [ ] ]这样的每个节点ID的关联链结构
• addLevel。递归计算出每个节点在当前树所在的层级

测试

$json = <<<JSON
[
    {"id":481412, "name":"重庆","parent_id":438556},
    {"id":483070, "name":"OAO税务局创新答评超越班","parent_id":483065},
    {"id":483072, "name":"OAO税务局创新答评综训班","parent_id":483065},
    {"id":486913, "name":"直播陪学-02期","parent_id":483072},
    {"id":486013, "name":"01期","parent_id":483070},
    {"id":490097, "name":"测试","parent_id":481412},
    {"id":490687, "name":"互动点拨班-特价","parent_id":481412},
    {"id":526061, "name":"贵州","parent_id":438556},
    {"id":526062, "name":"21年贵州省国考8晚督学课","parent_id":526061},
    {"id":492801, "name":"重大合作课","parent_id":481412}
]
JSON;
$list = json_decode($json, true);
$treeList = getTreeList($list);
echo json_encode($treeList, JSON_PRETTY_PRINT | JSON_UNESCAPED_UNICODE);

运行输出如下

和我们从界面上看到的一致，还给出了每个节点所在的层级level，非常给力~