树，根据节点的值计算父节点的值

前段时间回答了一个类似的问题，产生了写一篇博客的想法。这个问题确实存在一些常见的的应用场景，比如一个多层组织结构中，已知每个员工的绩效分，希望计算各级部门的绩效分以便对部门评优。

准备

根据这个描述，准备一个试验数据如下：

{
    "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 数据处理 - 列表篇​​