如何实现可灵活支持前/中/后序遍历的左结合二叉树fold函数

实现思路 #

你现有的treeFoldl把遍历顺序硬编码为「处理当前节点→递归左子树→递归右子树」，所以仅支持前序遍历。要实现三种遍历的灵活切换，只需要把左右子树的递归执行权交给传入的处理函数f，让f自行决定累加器更新、左递归、右递归三者的执行顺序即可。

通用左折叠treeFoldl实现 #

const treeFoldl = f => init => t => function go(acc, u) {
  if (u[TAG] === "Leaf") return acc;
  // 把三个执行单元都传给f：当前累加器、当前节点值、左子树折叠入口、右子树折叠入口
  return f(acc)(u.v)(
    (newAcc) => go(newAcc, u.l),
    (newAcc) => go(newAcc, u.r)
  );
}(init, t);

三种遍历的调用示例 #

和treeFoldr的逻辑对应，只需要调整f内的执行顺序即可：

// 数组拼接辅助函数：把x追加到acc末尾
const append = acc => x => [...acc, x];

// 前序：先追加当前值 → 递归左子树 → 递归右子树
const r1 = treeFoldl(
  acc => x => goLeft => goRight => 
    goRight(goLeft(append(acc)(x)))
)([])(foo);

// 中序：先递归左子树 → 追加当前值 → 递归右子树
const r2 = treeFoldl(
  acc => x => goLeft => goRight => 
    goRight(append(goLeft(acc))(x))
)([])(foo);

// 后序：先递归左子树 → 递归右子树 → 追加当前值
const r3 = treeFoldl(
  acc => x => goLeft => goRight => 
    append(goRight(goLeft(acc)))(x)
)([])(foo);

// 验证结果和右折叠实现完全一致
console.log(r2); // 中序输出 [4,1,5,0,2,3]

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