如何遍历树并计算非叶子节点根路径的乘积值

现有一棵以kdb+表定义的树，每行代表一条父节点 --> 子节点的路径，data字段为该路径的数值：

tree:([]parent:`A`A`A`B`B`E`E;child:`B`C`D`E`F`G`H;data:(1;2;3;4;5;6;7));

需求：针对每个非叶子节点，以其为根构建子树，获取从该根到每个叶子节点的完整路径，并计算每条路径的数值（路径上所有data的乘积）。

目前已通过以下代码获取所有路径，但无法完成路径数值的计算：

map: exec child by parent from tree;
pl:exec distinct parent from tree; / 非叶子节点列表
(map\)pl / 获取每个非叶子节点出发的所有路径

我们可以通过递归遍历的方式，同时记录路径和累积乘积，实现需求：

1. 先构建两个映射，方便后续快速查询：

   map: exec child by parent from tree; / 父节点到子节点的映射
   edgeData: exec data by parent,child from tree; / 每条边的数值映射
   

2. 编写递归函数，用于获取单个根节点到所有叶子节点的路径及对应乘积：

   getPathsWithProduct:{[node]
       recurse:{[currentNode;pathSoFar;productSoFar]
           // 叶子节点：返回完整路径和乘积
           if[not currentNode in key map;
               enlist (pathSoFar,currentNode; productSoFar)
           ];
           // 非叶子节点：遍历所有子节点，递归计算
           raze {[child]
               newPath: pathSoFar,currentNode;
               newProduct: productSoFar * edgeData[(currentNode;child)];
               recurse[child;newPath;newProduct]
           } each map[currentNode]
       };
       recurse[node;();1] // 初始路径为空，初始乘积为1（乘法单位元）
   }
   

3. 对所有非叶子节点批量执行该函数，得到最终结果：

   pl: exec distinct parent from tree;
   result: {x: getPathsWithProduct[x]; x!x} each pl;
   

结果示例 #

执行后，result中每个非叶子节点对应的结果如下：

• 节点A：(ABEG;24),(ABEH;28),(ABF;5),(AC;2),(AD;3)
• 节点B：(BEG;24),(BEH;28),(B`F;5)
• 节点E：(EG;6),(E`H;7)

内容的提问来源于stack exchange，提问作者seizetheday