博客 / 詳情

返回

樹，計算父節點的值

前段時間回答了一個類似的問題，產生了寫一篇博客的想法。這個問題確實存在一些常見的的應用場景，比如一個多層組織結構中，已知每個員工的績效分，希望計算各級部門的績效分以便對部門評優。

準備

根據這個描述，準備一個試驗數據如下：

{
    "name": "某某公司",
    "children": [
        {
            "name": "生產序列",
            "children": [
                { "name": "研發部", "children": [{ "name": "軟件部" }, { "name": "測試部" }] },
                { "name": "工程部", "children": [{ "name": "預算部" }, { "name": "項目管理部" }] }
            ]
        },
        { "name": "行財序列", "children": [{ "name": "財務部" }, { "name": "辦公室" }] }
    ]
}

直觀的樹形表示如下

某某公司
├── 生產序列
│   ├── 研發部
│   │   ├── 軟件組
│   │   └── 測試組
│   └── 工程部
│       ├── 預算組
│       └── 項目管理組
└── 行財序列
    ├── 財務部
    └── 辦公室

每個部門又有若干員工。假設拿到的數據是用元組（數組）來表示，分別是 [姓名, 部門, 崗位, 個人績效]，下面是隨機生成的一個用例數據。

[
    ["蘇研暢", "生產序列", "總監", 81],
    ["陶耀重", "研發部", "部長", 80],
    ["吉溢孟", "軟件組", "總工程師", 87], ["強航棟", "軟件組", "分析師", 84], ["褚臣璋", "軟件組", "架構師", 96],
    ["武好妙", "軟件組", "工程師", 95], ["湯勁景", "軟件組", "工程師", 87], ["蓬麗梓", "軟件組", "工程師", 91],
    ["牧潛霞", "軟件組", "工程師", 84], ["呂承同", "軟件組", "工程師", 86],
    ["花寧璇", "測試組", "測試組長", 93], ["苗葵惟", "測試組", "測試工程師", 95], ["鄒蓮娟", "測試組", "測試工程師", 89],
    ["秦薈淑", "測試組", "助理", 85],
    ["顧諾腸", "工程部", " 部長", 86],
    ["喻蒙珣", "預算組", "預算師", 91], ["甄林日", "預算組", "預算師", 81], ["劉朦櫻", "預算組", "預算師", 92],
    ["嚴寧瑩", "項目管理組", "項目經理", 84], ["晏陵添", "項目管理組", "項目經理", 81], ["石飆隆", "項目管理組", "項目經理", 95],
    ["龔通品", "行財序列", "總監", 95],
    ["魏曉豔", "財務部", "部長", 85],
    ["程璇彤", "財務部", "會計", 88], ["支予詩", "財務部", "出納", 92],
    ["羿鴻權", "辦公室", "主任", 83], ["丁雁煉", "辦公室", "助理", 82]
]

計算各部門績效分

假設取到的部門數組存放在 depts 變量中，員工績效數組在 staffs 變量中

計算各部門績效分的規則採用最簡單的算法：部門所有員工績效分的平均值。但在處理方式上還是有幾種方法。

  1. 組合大樹，把 depts 和 staffs 組合成一個 orgTree，然後再來遞歸計算；
  2. 直接在 depts 上遞歸計算，算到部門的時候再去 staffs 裏找部門的員工，結合子部門分值來計算部分績效分。

方法一，組合大樹

就算是用組合大樹，也是有很多方法的。

  1. 遍歷 staffs，根據每個員工的部門去找正確的樹節點，加進去。由於查詢樹節點算法較為複雜，這種方法查找起來比較慢；
  2. 先從 depts 生成部門名稱到部門對象的映射，然後再遍歷 staffs 去找部門節點。這種方法使用了映射表，查找起來快，會多消耗一點內存。

現在內存並不貴，而且這點部門數組能消耗的內存極其有限，所以選用第二種方法。生產映射表需要遍歷樹，我曾經在使用遞歸遍歷並轉換樹形數據 一文中介紹了幾種遍歷樹的方法，這裏再寫一種，使用 Generator（本質上是深度遞歸），熟悉一下 yield 和 yield * 的用法。

function flatTree(nodes) {
    // 兼容單節點和節點數組（單根/多根）的情況
    if (!Array.isArray(nodes)) { nodes = [nodes]; }

    // 一切從這裏開始
    return [...iterate(nodes)];

    // 內部 iterate generator 遞歸實現
    function* iterate(nodes) {
        for (const node of nodes) {
            yield node;
            if (node.children?.length) {
                yield* iterate(node.children);
            }
        }
    }
}

映射表可以用 Map，不過既然鍵（部門名稱）就是文本，那就直接用 JS 對象來作映射表吧，Object.fromEntries() 安排上：

const deptMap = Object.fromEntries(
    flatTree(depts).map(node => [node.name, node])
);
注意：能做這個映射表的前提是每個部門的名稱都不一樣。如果存在同名的部門，需要另找唯一識別屬性，通常會是 ID。

在合併員工數據的時候，需要給每個節點加 staffs 屬性。為了不污染源 depts 數據，使用 JSON 來做一個簡單地深拷貝

const orgTree = JSON.parse(JSON.stringify(depts));
const deptMap = Object.fromEntries(
    flatTree(orgTree).map(node => [node.name, node])
//           ^^^^^^^
);

合併員工：遍歷員工列表，一個個加到樹節點上去。注意到這裏每個員工是個元組（數組），所以用解構的辦法快速得到各屬性，也方便後面直接組成對象。

staffs.forEach(([name, dept, title, value]) => {
    const deptNode = deptMap[dept];
    // 沒找到部門則忽略。雖然示例數據中不存在這種情況，但寫業務時應該適當容錯
    if (!deptNode) { return; }
    (deptNode.staffs ??= []).push({ name, dept, title, value });
});

總算到了算績效了。按規則，部門績效是其下所有員工績效的平均值。那就需要計算其下所有員工的總分值和員工數。注意，在遞歸計算的時候，上級部門需要使用下級部門的總分和總人數，而不是平均分 —— 為什麼？不要問我，去問數學老師！

下面的 calcValue 仍然是一個入口，裏面的 calcNode 和 calcNodeList 才是遞歸函數。注意這裏拆分了處理單個部門和處理部門數組的邏輯（每個部門的子部門是一個部門數組，每個部門數組裏是若干個單部門），calcNode 和 calcNodeList 是存在相互調用關係的雙遞歸實現。

function calcValue(deptNodes) {
    Array.isArray(deptNodes) ? calcNodeList(deptNodes) : calcNode(deptNodes);

    /**
     * @returns 返回 [總人數, 總分]（因為計算過程中只需要這兩個值）
     */
    function calcNodeList(depts) {
        return depts.reduce(([sum, count], dept) => {
            const [deptCount, deptSum] = calcNode(dept);    // 遞歸
            sum += deptSum;
            count += deptCount;
            return [sum, count];
        }, [0, 0]);
    }

    /**
     * @returns 返回 [總人數, 總分]（因為計算過程中只需要這兩個值）
     */
    function calcNode(dept) {
        let [count, sum] = [0, 0];
        // 有子部門先算子部門的
        if (dept.children?.length) {
            // 計算過程中不在乎下級部分的平均分
            const [deptSum, deptCount] = calcNodeList(dept.children);   // 遞歸
            sum += deptSum;
            count += deptCount;
        }

        // 還得加本部門員工的
        if (dept.staffs?.length) {
            sum += dept.staffs.reduce((sum, { value }) => sum + value, 0);
            count += dept.staffs.length;
        }

        // 別忘了 0 是不能作除數的
        Object.assign(dept, { sum, count, value: count && (sum / count) });
        return [dept.count, dept.sum];
    }
}

不要懼怕雙遞歸、多遞歸……把一個遞歸拆成多個函數仍然是為了把一個大邏輯拆成若干小邏輯而已，自然拆分就行，不需要特別在意它是不是遞歸調用。

方法二，保持部門和員工數據分離

在方法一中，遞歸計算的 calcNode 函數裏有一段是計算員工的，就是這一段：

if (dept.staffs?.length) {
    sum += dept.staffs.reduce((sum, { value }) => sum + value, 0);
    count += dept.staffs.length;
}

考慮把它封裝成函數調用：

// IIFE 調用，為了一句話處理兩個結果數據
(([c, s]) => [count, sum] = [count + c, sum + s])(calcStaffs(dept));
//^^^^^^ 解構傳入的參數元組                          ^^^^^^^^^^^^^^^^ 結果是個元組，作為參數
//           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 利用解構表達式計算並重新賦值

// 計算部門當級員工的總分和總人數
function calcStaffs(dept) {
    if (!dept.staffs?.length) { return [0, 0]; }
    return [
        dept.staffs.length,
        dept.staffs.reduce((sum, { value }) => sum + value, 0),
    ];
}

上面那句 IIFE 調用把臨時變量 c 和 s 封在了一個小局部作用域中，用完即拋，後面利用解構把兩個賦值語句寫成了一句，如果看不慣，像 count += c 這樣分開來肯定不會錯。

注意到 calcStaffs 的參數是一個部門，函數內部通過 dept.staffs 來找到該部門的當級員工。如果我們直接根據 dept.name 去 staffs 原始數組裏面找數據，就不需要提前把員工掛到對應的部門上。比如像這樣找：

function calcStaffs(dept) {
    const deptStaffs = staffs.filter(([, deptName]) => dept.name === deptName);
//                     ^^^^^^^^^^^^^ 在所有員工中按部門名稱把員工過濾出來
    if (!deptStaffs.length) { return [0, 0]; }
//                 ^ 不再需要 ?. 因為過濾結果一定是個數組，但可能是空的
    return [
        deptStaffs.length,
        deptStaffs.reduce((sum, [, , , value]) => sum + value, 0),
//                              ^^^^^^^^^^^^^ 注意原始 staffs 中的每個員工是元組表示
    ];
}

這樣一來，員工是直接從 staffs 這個包含所有員工的數組裏去查找的，不再需要提前把員工掛上部門，所以之前那段 staffs.forEach() 就不再需要了……嗯，就是這段：

staffs.forEach(([name, dept, title, value]) => { ... });

在員工人員較多的時候，每次 filter 遍歷效率確實比較受影響，這種情況下可以先對 staffs 分組，得到一個 staffMap

const staffMap = staffs.reduce((all, staff) => {
    (all[staff[1]] ??= []).push(staff);
    return all;
}, {});

查找當然不需要再用 filter，而是直接查表。改動不難，代碼就省略了。

注意查找結果存在 undefined 的可能了哦！如果不知道我為什麼要這麼説，就再看看往上數的第 3 段代碼中的註釋。

動態計算

到目前為止，我們都是在所有數據已經準備好的情況下進行的靜態計算。如果分值是在 UI 上填寫，需要實時計算各部門績效分呢？那就需要動態計算 —— 當然某個分值發生變化的時候，對所有節點進行一次重算肯定不會有錯，就是比較浪費算力。

分析一下，如果某個員工的分支發生變化，可能會產生哪些影響？

  1. 肯定會影響到他所在部門的分值
  2. 連鎖反應，會影響到該部門的父級部門，以及祖先部門的分值
  3. 會影響到子級部門分值嗎？不會！
  4. 會影響到兄弟部門分值呈？也不會！

所以，在這種情況下，只需要找到分值變化這個員工所在部門，以及他的父級部門，自下而上逐級重算即可。在計算每個級部門分值時，其子級分值已經固定（完成計算），所以只需要使用直接子級和直接員工的分值計算即可，不需要遞歸。

不過，看上面的結構，每個樹節點沒有 parent 關聯，所以查找部門還是得從根開始，遞歸查找。關於遞歸查找的問題，在過濾/篩選樹節點中已經有説明，就不再詳述了。即於有 parent 關聯的情況比較簡單，也不講解了。計算過程由於不進行遞歸，也比較簡單

// path 是從根到員工所在部門節點的集合
function calcPath(path) {
    // 要從接近葉節點的節點開始計算，所以先反個向
    // 注意 reverse 會改變原數組
    path.reverse();
    for (const dept of path) {
        [dept.count, dept.sum] = dept.children
            ?.reduce(
                ([count, sum], it) => [count + it.count, sum + it.sum],
                [0, 0]
            ) ?? [0, 0];  // 沒有 children 的時候給個默認值

        // 有員工且不是空數組才進行處理
        dept.staffs?.length && (
            // reduce 處理過程跟上面類似，只是取值不同
            [dept.count, dept.sum] = dept.staffs.reduce(
                ([count, sum], it) => [count + 1, sum + it.value],
                // 只不過 count 和 sum 已經有值，要從現有值開始累計
                [dept.count, dept.sum]
            )
        );
    }
}

小結

根據子節點計算父節點值本質上還是基於遍歷樹節點這一知識點的運用，同時還需要掌握對集合數據的處理方法。至於語法，不要怕使用新語法，也不用太擔心兼容性的問題，對舊環境的兼容性可以交給編譯器去處理（比如 tsc、babel 等）。

最後推薦幾篇相關的博文：

  • 使用遞歸遍歷並轉換樹形數據
  • 過濾/篩選樹節點
  • 從列表生成樹 (JavaScript/TypeScript)
  • JavaScript 數據處理 - 映射表篇
  • JavaScript 數據處理 - 列表篇
統計 , 遍歷 , 樹形結構 , Javascript
user avatar
0 位用戶收藏了這個故事！

發佈 評論

Some HTML is okay.