关于javascript:树根据节点的值计算父节点的值

前段时间答复了一个相似的问题，产生了写一篇博客的想法。这个问题的确存在一些常见的的利用场景，比方一个多层组织构造中，已知每个员工的绩效分，心愿计算各级部门的绩效分以便对部门评优。

筹备

依据这个形容，筹备一个试验数据如下：

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