用 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 dont 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 BinaryTreeT { case node(BinaryTreeT, T, BinaryTreeT) case empty }这个定义非常简洁只有两种情况case node(BinaryTreeT, T, BinaryTreeT)一个内部节点依次携带左子树、节点值、右子树三个关联值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结果为126 个叶节点 6 个内部节点Playground 中的注释也标注了这一预期值。三种遍历方式In-order、Pre-order、Post-order遍历traverse即按照某种顺序访问树中的所有节点。二叉树有三种经典遍历顺序BinaryTree.swift 中的实现中序遍历In-order先访问左子节点再访问节点自身最后访问右子节点前序遍历Pre-order先访问节点自身再访问左、右子节点后序遍历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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
