【演算法框架套路】找出給定數據中所有的樹

• 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，非常給力~