企业官网建设流程全解析

用 Swift 的indirect enum实现通用二叉树：定义、遍历与表达式求值

【免费下载链接】swift-algorithm-clubAlgorithms and data structures in Swift, with explanations!项目地址: https://gitcode.com/gh_mirrors/sw/swift-algorithm-club

二叉树是计算机科学中最基础也最常用的数据结构之一。本指南以 Swift Algorithm Club 仓库中的 Binary Tree/README.markdown 为主体，配合仓库内的 BinaryTree.swift 源码与 BinaryTree.playground 可运行示例，系统讲解如何用 Swift 的递归枚举（indirect enum）实现一个通用二叉树，并给出节点计数、三种遍历方式以及"后序遍历 + 栈机器"求值算术表达式树的完整方案。读完本文，你将掌握二叉树的概念术语、Swift 中的函数式建模方式，并能直接复用仓库代码构建自己的树形结构应用。

二叉树是什么

二叉树（Binary Tree）是一种特殊的树结构，其中每个节点最多拥有 0、1 或 2 个子节点。下面这张图就是一个典型的二叉树（图片位于 Binary Tree/Images/BinaryTree.png）：


二叉树的节点通常被区分为左子节点（left child）和右子节点（right child）。围绕节点位置，有几个约定俗成的术语：

• 根节点（root）：位于树的最顶端。程序员习惯把树"倒过来画"，根在上、叶子在下。
• 叶节点（leaf）：没有任何子节点的节点。
• 除了根节点外，每个节点都有且仅有一个父节点；但节点通常不保存指向父节点的引用——这不是严格必需的。仓库源码 BinaryTree.swift 的头部注释也明确写道"Nodes don't have a reference to their parent"，与这一设计完全一致。

二叉树的典型应用场景

二叉树最常见的用途是作为二叉搜索树（Binary Search Tree, BST）：此时节点必须满足有序约束——较小的值在左子树、较大的值在右子树。但有序并不是所有二叉树的硬性要求，本篇文章实现的通用二叉树不附加任何排序约束。

一个绝佳的反例是表达式树：用二叉树表示算术表达式，操作符存放在内部节点，操作数存放在叶子节点。例如表达式(5 * (a - 10)) + (-4 * (3 / b))可以表示为下面这棵树（图片位于 Binary Tree/Images/Operations.png）：


用 Swift 的indirect enum定义二叉树

在 Swift 中，最优雅的实现方式是利用递归枚举（recursive enum）。由于枚举在递归引用自身时需要编译器处理间接存储，因此必须用indirect关键字修饰。仓库 BinaryTree.swift 中的完整定义如下：

public indirect enum BinaryTree<T> { case node(BinaryTree<T>, T, BinaryTree<T>) case empty }

这个定义非常简洁，只有两种情况：

• case node(BinaryTree<T>, T, BinaryTree<T>)：一个内部节点，依次携带左子树、节点值、右子树三个关联值；
• case empty：空树（对应"没有子节点"的情况，也是叶子节点左右两侧的占位）。

与基于 class 的"引用 + 指针"实现相比，indirect enum是 Swift 中典型的值语义函数式建模：树的全部内容都内嵌在枚举值本身，天然支持模式匹配（switch/if case），代码表达力强、不易产生循环引用问题。若想了解对比实现，可以阅读仓库中不限子节点数量的通用树实现 Tree/README.markdown，以及带有序约束的 Binary Search Tree 文档。

实战：自底向上构造表达式树

利用上面的枚举构造(5 * (a - 10)) + (-4 * (3 / b))这棵表达式树。核心技巧是从叶子节点开始，自底向上逐层拼接，最后汇合到根节点（完整可运行代码见 BinaryTree.playground/Contents.swift）：

// 叶子节点：数字和变量 let node5 = BinaryTree.node(.empty, "5", .empty) let nodeA = BinaryTree.node(.empty, "a", .empty) let node10 = BinaryTree.node(.empty, "10", .empty) let node4 = BinaryTree.node(.empty, "4", .empty) let node3 = BinaryTree.node(.empty, "3", .empty) let nodeB = BinaryTree.node(.empty, "b", .empty) // 左子树的中间节点：(a - 10) 和 (5 * (a - 10)) let Aminus10 = BinaryTree.node(nodeA, "-", node10) let timesLeft = BinaryTree.node(node5, "*", Aminus10) // 右子树的中间节点：(-4)、 (3 / b) 和 ((-4) * (3 / b)) let minus4 = BinaryTree.node(.empty, "-", node4) let divide3andB = BinaryTree.node(node3, "/", nodeB) let timesRight = BinaryTree.node(minus4, "*", divide3andB) // 根节点：左右两棵子树通过 "+" 合并 let tree = BinaryTree.node(timesLeft, "+", timesRight)

注意一个细节：表达式中的-4被建模为minus4 = BinaryTree.node(.empty, "-", node4)，即"左子树为空、右子树为 4"的一元负号节点，说明二叉树并不要求所有内部节点都恰好有两个非空子节点——这正是通用二叉树比满二叉树（full binary tree）更灵活的地方。

打印二叉树：实现CustomStringConvertible

直接print(tree)无法看到结构，因此需要遵循CustomStringConvertible协议提供description。源码中的实现通过递归拼接子树的描述文本：

extension BinaryTree: CustomStringConvertible { public var description: String { switch self { case let .node(left, value, right): return "value: \(value), left = [\(left.description)], right = [\(right.description)]" case .empty: return "" } } }

执行print(tree)会得到一整行冗长的描述；把它按缩进重新排版后，树形结构一目了然：

value: +, left = [value: *, left = [value: 5, left = [], right = []], right = [value: -, left = [value: a, left = [], right = []], right = [value: 10, left = [], right = []]]], right = [value: *, left = [value: -, left = [], right = [value: 4, left = [], right = []]], right = [value: /, left = [value: 3, left = [], right = []], right = [value: b, left = [], right = []]]]

[]即空树.empty的打印结果，value: 5, left = [], right = []则是一个典型的叶节点。

统计节点数：递归的count

二叉树结构的许多操作天然适合递归。节点计数count的公式为：节点总数 = 左子树节点数 + 1（自身）+ 右子树节点数，空树计为 0。仓库 BinaryTree.swift 的实现：

public var count: Int { switch self { case let .node(left, _, right): return left.count + 1 + right.count case .empty: return 0 } }

对前面构造的表达式树调用tree.count，结果为12（6 个叶节点 + 6 个内部节点），Playground 中的注释也标注了这一预期值。

三种遍历方式：In-order、Pre-order、Post-order

遍历（traverse）即按照某种顺序访问树中的所有节点。二叉树有三种经典遍历顺序（BinaryTree.swift 中的实现）：

1. 中序遍历（In-order）：先访问左子节点，再访问节点自身，最后访问右子节点；
2. 前序遍历（Pre-order）：先访问节点自身，再访问左、右子节点；
3. 后序遍历（Post-order）：先访问左、右子节点，最后处理节点自身。

三种方法都接收一个(T) -> Void闭包process作为回调，用于处理访问到的节点值：

public func traverseInOrder(process: (T) -> Void) { if case let .node(left, value, right) = self { left.traverseInOrder(process: process) process(value) right.traverseInOrder(process: process) } } public func traversePreOrder(process: (T) -> Void) { if case let .node(left, value, right) = self { process(value) left.traversePreOrder(process: process) right.traversePreOrder(process: process) } } public func traversePostOrder(process: (T) -> Void) { if case let .node(left, value, right) = self { left.traversePostOrder(process: process) right.traversePostOrder(process: process) process(value) } }

这三种实现都通过if case let .node(...) = self进行模式匹配，并在匹配成功时递归调用自身——这与树形结构递归定义的本质高度一致。Playground 中分别对tree调用了三种遍历并print每个值。

以表达式树为例，后序遍历输出的顺序是：

5 a 10 - * 4 - 3 b / * +

可以看到：所有叶子节点（操作数）先出现，而根节点（最外层的+）最后出现——这正是后序遍历"先孩子、后自身"的直接体现。

进阶应用：后序遍历 + 栈机器求值表达式

后序遍历的顺序天然适合用**栈机器（stack machine）**求值算术表达式。思路是维护一个栈，依次处理后序遍历输出的每个值，伪代码如下：

tree.traversePostOrder { s in switch s { case this is a numeric literal, such as 5: push it onto the stack case this is a variable name, such as a: look up the value of a and push it onto the stack case this is an operator, such as *: pop the two top-most items off the stack, multiply them, and push the result back onto the stack } the result is in the top-most item on the stack }

求值过程可以这样理解：遇到操作数（字面量或变量查值）就压栈；遇到操作符就从栈顶弹出两个操作数执行运算，再把结果压回栈中。当遍历结束时，栈顶的剩余元素就是整个表达式的最终结果。这也就是编译器与解释器广泛采用的"逆波兰表达式（RPN）求值"思路——二叉树的后序遍历序列本质上就是该表达式的中缀形式转换后的后缀形式。

源码中的隐藏彩蛋：镜像翻转invert()

仓库源码 BinaryTree.swift 中还额外提供了一个 README 未展开说明的方法invert()：递归交换每个节点的左右子树，生成原树的水平镜像：

func invert() -> BinaryTree { if case let .node(left, value, right) = self { return .node(right.invert(), value, left.invert()) } else { return .empty } }

从实现可以看出，invert()遵循与遍历相同的递归骨架：先分别对左右子树递归调用invert()，再以"右子树、原值、左子树"的顺序重新组装节点，从而完成整棵树的镜像翻转。这也是面试中常见的二叉树考题，可以作为练习验证你对递归建模的理解。

扩展阅读与可运行环境

• 阅读 Binary Tree/README.markdown 查看本篇指南的原始文档；
• 在 Xcode 中打开 BinaryTree.playground 即可直接运行构造、打印、计数与遍历的完整示例代码；
• 若想了解不限制子节点数量的通用树，参见 Tree 文档；需要有序约束的二叉搜索树，参见 Binary Search Tree 文档；
• 二叉树的近亲还包括 AVL Tree、Red-Black Tree 等自平衡变体，它们都以本文的节点/子树递归结构为基础。

小结

本文以indirect enum为核心，完整走通了通用二叉树的建模、构造、打印、计数、遍历与表达式求值全流程。要点回顾：

• 二叉树每个节点最多两个孩子，分为左/右子节点，无子节点者称为叶节点；
• Swift 中可用indirect enum以值语义优雅建模递归结构，case .node与case .empty两种情形即可覆盖一切二叉树；
• count、description与三种遍历均遵循"空树为递归出口、非空节点递归分解"的统一模式；
• 后序遍历天然适配栈机器求值，是实现表达式计算与编译原理中语法树求值的基础。

掌握这些能力后，你不仅能读懂 Swift Algorithm Club 中几乎所有树形算法（从二叉搜索树到各种自平衡树）的源码，也能在自己的 Swift 项目中直接复用这套递归枚举模式处理层次化数据。

【免费下载链接】swift-algorithm-clubAlgorithms and data structures in Swift, with explanations!项目地址: https://gitcode.com/gh_mirrors/sw/swift-algorithm-club