Erlang 中实现树遍历的并发与同步方案详解

本文介绍如何将 go 语言中的树遍历函数 `walk` 转译为 erlang，重点对比并发（`spawn`）与同步（递归）两种实现方式，并指出其行为差异、适用场景及潜在问题。

在 Erlang 中实现类似 go 的 Walk 函数时，关键在于理解“遍历”的语义目标：按中序（左-根-右）访问每个节点值并输出。原提问者使用 spawn/3 启动子进程遍历左右子树，从语法上看确实实现了并发，但该设计存在一个根本性偏差——它不是真正的中序遍历，而是一种竞态驱动的乱序输出。

❗ 并发版 walk/1 的问题分析

walk({Left, Value, Right}) ->     spawn(tree, walk, [Left]),   % ← 异步启动，不等待完成     erlang:display(Value),       % ← 立即打印根节点     spawn(tree, walk, [Right]), % ← 异步启动，不等待完成     ok; walk({}) -> continue.

上述代码虽“并发”，但完全丧失执行顺序保证：左子树进程可能在根节点之后、右子树之前、之中或之后打印；甚至因调度延迟，alina 可能晚于 tea 输出。这违背了 Walk 的原始契约（确定性中序序列），也使结果不可预测、不可测试。

✅ 正确结论：它是并发的，但不是正确的并发遍历——并发 ≠ 无序，而是需配合同步机制（如 receive、join 或消息传递）来协调顺序。

✅ 推荐方案：同步中序遍历（默认首选）

若目标是忠实复现 Go 的 Walk 行为（即严格中序输出），应采用纯递归、无进程创建的方式：

walk_sync({Left, Value, Right}) ->     walk_sync(Left),     erlang:display(Value),     walk_sync(Right); walk_sync({}) -> ok.  % 统一返回 ok，语义清晰

✅ 优势：

• 输出顺序严格符合中序（如 alina → maria → vlad → tea）；
• 无进程开销，资源可控；
• 易于调试、组合（例如收集值为列表：walk_collect(Tree) -> walk_collect(Tree, [])）。

⚙️ 若真需并发遍历：必须显式同步

假设场景是大规模树的 I/O 密集型处理（如每个节点触发 http 请求），且允许最终聚合结果，可设计带同步的并发版本：

walk_concurrent(Tree) ->     Self = self(),     spawn(fun() -> walk_worker(Self, Tree) end),     receive         done -> ok     end.  walk_worker(Parent, {Left, Value, Right}) ->     spawn(fun() -> walk_worker(Parent, Left) end),     erlang:display(Value),     spawn(fun() -> walk_worker(Parent, Right) end),     Parent ! done; walk_worker(Parent, {}) ->     Parent ! done.

⚠️ 注意：此例仅为示意，实际中更推荐使用 proc_lib、gen_server 或现代工具如 tasks（OTP 26+）来管理并发生命周期，避免裸 spawn + 手动 ! 导致的死锁或消息丢失。

? 总结建议

最后提醒：Erlang 的哲学是“让并发服务于可靠性”，而非“为并发而并发”。先确保逻辑正确，再根据性能瓶颈谨慎引入并发——这才是地道的 Erlang 实践。