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，语义清晰

✅ 优势：

微信小程序公众号SaaS管理系统

微信小程序公众号SaaS管理系统是一款完全开源的微信第三方管理系统，为中小企业提供最佳的小程序集中管理解决方案。可实现小程序的快速免审核注册（免300元审核费），可批量发布小程序模板，同步升级版本等功能。基础版本提供商城和扫码点餐两种小程序模板。商户端可以实现小程序页面模块化设计和自动生成小程序源代码并直接发布。

下载

• 输出顺序严格符合中序（如 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 实践。