二叉树的编码与解码Swift 算法俱乐部中的序列化与反序列化实战【免费下载链接】swift-algorithm-clubAlgorithms and data structures in Swift, with explanations!项目地址: https://gitcode.com/gh_mirrors/sw/swift-algorithm-club本文是 Swift Algorithm Club 中 Encode and Decode Tree 专题的深度解读。二叉树是非线性结构节点之间携带父子关系等位置信息无法像数组那样直接传输。本文围绕该项目提供的BinaryNode与BinaryNodeCoder实现完整讲解如何用pre-order前序遍历 分隔符 空节点哨兵将一棵树序列化为字符串编码再将该字符串还原为结构完全一致的树解码。读完本文你将掌握一套可直接复用的二叉树序列化方案并理解其背后的数据结构与算法取舍。为什么树需要编码与数组、链表这类线性集合不同树是非线性结构每个元素不仅承载数据还隐含了与其他元素之间的位置关系例如父子关系、左右子树的划分。当我们需要把一棵树发送给后端、存入数据库或跨进程传递时单靠节点值本身是不够的——接收方必须能从中恢复出树的形状。因此我们需要一套规则把树这种结构化的对象转换成可以传输的扁平形式如String这个过程称为编码Encoding也叫序列化Serializing反过来把扁平的编码数据还原成树则称为解码Decoding也叫反序列化Deserializing。项目中 readme 原文给出了一句关键结论Encoding and decoding strategies are closely related. The way you choose to encode a tree directly affects how you might decode a tree.也就是说编码与解码策略必须配套设计编码时丢失的信息解码时永远无法找回编码时额外保留的信息则决定了树能否被唯一地重建。前置知识本项目中的二叉树节点模型在深入编码之前需要先了解二叉树的底层概念。项目中提供了独立的 Binary Tree 专题其中定义了二叉树的经典递归结构每个节点最多有 0、1、2 个子节点分别称为左孩子与右孩子没有子节点的节点称为叶子节点最顶端的节点称为根节点。本文的编码专题使用了基于类的节点实现。完整定义位于 EncodeAndDecodeTree.swiftpublic class BinaryNodeElement: Comparable { public var val: Element public var left: BinaryNode? public var right: BinaryNode? public init(_ val: Element, left: BinaryNode? nil, right: BinaryNode? nil) { self.val val self.left left self.right right } }值得注意的细节Element: Comparable泛型约束表示节点值必须可比较。从源码结构看这更多是沿用了二叉搜索树场景的约束习惯编码算法本身只依赖值的字符串描述能力left与right都是可选类型Optional空孩子节点在模型上就是nil这一点是后续编码中用空哨兵标记的前提初始化器提供了默认参数可以便捷地构造叶子节点BinaryNode(a)。编码策略的设计三条核心规则本项目采用的编码策略在 readme 中明确列出编码结果是一个String对象使用 pre-order前序遍历访问节点节点值之间用分隔符,区分空的孩子节点用哨兵字符X标记。为什么选择前序遍历因为配合空节点也占位的规则前序序列可以唯一确定一棵二叉树前序的第一个元素永远是根节点之后每遇到一个值就建立节点每遇到一个X就说明该分支到此为止。这种边读边回溯的性质使得解码可以只靠一个线性序列完成不需要额外记录节点数量或层级信息。两个关键约定分隔符与空哨兵编码实现中定义了两个私有常量见 EncodeAndDecodeTree.swiftprivate let separator: Character , private let nilNode X分隔符separator用于区分序列中相邻的节点值。readme 用一个非常形象的例子说明了它的必要性——如果某棵树的编码结果是字符串banana在没有分隔符的情况下我们无法判断它原本是b和anana两个节点还是ban和ana还是其他任何切分方式。分隔符的存在让节点边界变得明确、无歧义。空哨兵nilNode用于标识缺失的孩子节点。因为解码时需要重建完整的树结构某个节点没有左孩子和左孩子还没处理到这两种状态必须能区分开来。X就是此处没有节点的显式标记。前序遍历的实现节点类型扩展了preOrderTraversal方法EncodeAndDecodeTree.swiftpublic func preOrderTraversal(visit: (Element?) throws - ()) rethrows { try visit(val) if let left left { try left.preOrderTraversal(visit: visit) } else { try visit(nil) } if let right right { try right.preOrderTraversal(visit: visit) } else { try visit(nil) } }这段代码有两个容易被忽略的设计点遍历顺序是根 → 左子树 → 右子树即经典前序当左或右孩子为nil时依然调用一次visit(nil)把空作为一个普通元素写入访问序列。这正是编码算法得以重建结构的关键——序列中每个真实节点都恰好对应两个空位标记左、右孩子位置信息因此被完整保留。编码实现剖析编码器BinaryNodeCoder类同时遵守两个协议EncodeAndDecodeTree.swiftprotocol BinaryNodeEncoder { func encodeT(_ node: BinaryNodeT?) throws - String } protocol BinaryNodeDecoder { func decodeT(from string: String) - BinaryNodeT? } public class BinaryNodeCoderT: Comparable: BinaryNodeEncoder, BinaryNodeDecoder { // ... }encode方法EncodeAndDecodeTree.swiftpublic func encodeT(_ node: BinaryNodeT?) throws - String { var str node?.preOrderTraversal { data in if let data data { let string String(describing: data) str.append(string) } else { str.append(nilNode) } str.append(separator) } return str }逐步拆解对根节点调用preOrderTraversal用闭包消费每一次访问访问到真实节点时通过String(describing: data)把任意Comparable值转换成字符串访问到空节点时追加X无论值还是空标记每次访问后都追加一个分隔符,保证相邻 token 互不粘连。例如一棵只有两个节点ba根和nana左孩子的树编码结果大致为ba,nana,X,X,X,。注意编码结果是带尾部分隔符的decode侧的split会自然忽略空尾元素。值得补充的是readme 中最初设计的接口是func encodeT(_ node: BinaryNodeT) throws - String where T: Encodable即计划借助 Swift 标准库的Codable体系而仓库最终落地实现见 EncodeAndDecodeTree.swift选择用String(describing:)完成值到字符串的转换使算法不依赖节点类型实现Encodable协议通用性更强同时保留了throws签名以兼容未来的错误处理。解码实现剖析解码是编码的精确逆操作。编码规则已经隐含了解码所需的全部信息用,切分序列得到一个个 tokentoken 为X表示空节点其余表示真实节点值按照前序顺序递归重建先建根再建左子树最后建右子树。利用数组即栈的优化公有decode方法EncodeAndDecodeTree.swiftpublic func decodeT(from string: String) - BinaryNodeT? { var components string.split(separator: separator).reversed().map(String.init) return decode(from: components) }这里有一个精心设计的性能优化split(separator:)按,切分自动过滤空 token切分结果先reversed()再交给递归函数递归函数内部使用removeLast()而非removeFirst()取元素。为什么要反转因为 Swift 数组的removeFirst()是O(n)操作需要整体前移元素而removeLast()是O(1)。先把数组反转就能用数组当作栈的方式从尾部弹出元素把解码的取元素成本从 O(n²) 降为 O(n)。readme 明确指出Thereversestep is an optimization for the next function, allowing us to usearray.removeLast()instead ofarray.removeFirst().递归重建的核心逻辑私有递归方法EncodeAndDecodeTree.swiftprivate func decodeT(from array: inout [String]) - BinaryNodeT? { guard !array.isEmpty else { return nil } let value array.removeLast() guard value ! nilNode, let val value as? T else { return nil } let node BinaryNodeT(val) node.left decode(from: array) node.right decode(from: array) return node }递归逻辑拆解数组为空序列耗尽返回nil对应编码时空哨兵之后不再有节点的情况弹出栈顶 token如果是X说明这里是空节点直接返回nil否则尝试用value as? T把字符串转回泛型类型转换失败同样视为空节点先建根、再递归左右left decode(...)会消耗掉左子树对应的全部 token之后right decode(...)继续消耗右子树的 token。由于前序序列中值—左子树—右子树天然有序递归顺序与编码顺序完全对称树结构得以忠实还原。完整可运行示例项目在 EncodeAndDecodeTree.playground/Contents.swift 中提供了可直接运行的演示代码。构造一棵五节点二叉树let coder BinaryNodeCoderString() let node1 BinaryNode(a) let node2 BinaryNode(b) let node3 BinaryNode(c) let node4 BinaryNode(d) let node5 BinaryNode(e) node1.left node2 node1.right node3 node3.left node4 node3.right node5 let encodeStr try coder.encode(node1) print(encodeStr)这棵树的形状是a / \ b c / \ d e编码结果为a,b,X,X,c,d,X,X,e,X,X,——逐段解读根ab的左孩子、右孩子都是空两个Xc的左孩子d和右孩子e它们各自的左右孩子又都是空各两个X。接着解码并打印还原后的树let root: BinaryNodeString coder.decode(from: encodeStr)! printTree(root)Playground 中的printTree以值 左右孩子的缩进形式输出运行结果确认了解码后的树与原始树完全一致val: a left: b right: c val: b left: nil right: nil val: c left: d right: e val: d left: nil right: nil val: e left: nil right: nilreadme 中还用一棵 8 节点树展示了更完整的过程原始树、编码字符串830,202,169,X,X,701,X,X,7838,3924,2506,X,X,4936,X,X,8391,X,8423,X,X,与解码后的树三者一一对应验证了方案的往返一致性round-trip 完整性。边界情况与使用约束基于对 EncodeAndDecodeTree.swift 实现的逐行分析实际使用中需要留意以下边界1. 节点值不能包含分隔符,。编码时直接用,连接所有 token解码时也按,切分。若节点值本身含有逗号如字符串a,b会被错误拆成两个 token导致解码结果错乱。这是该类简单序列化方案的固有局限可以通过对值做转义或改用长度前缀等方案规避但会显著增加复杂度。2. 节点值不能与空哨兵X冲突。若真实节点值恰好就是字符串X解码时会把它误判为空节点。选择X正是因为它极少出现在真实业务数据中但并非绝对安全。3. 空树nil根节点的编码。encode中对node?使用了可选链调用根节点为nil时不会触发任何访问返回空字符串而decode对空字符串执行split得到空数组递归入口直接返回nil。因此空树可以正确往返。4. 类型转换的静默失败。解码时value as? T失败会返回nil而不是抛出错误。若调用方用错误的泛型类型解码例如把数值树当成字符串树解码得到的结果可能不完整且没有显式报错生产环境中建议对解码结果做非空校验。5. 非平衡树的递归深度。解码依赖递归调用递归深度等于树高。对于极端退化的链状树如只有右孩子的树深递归可能造成栈溢出风险可推断这是本实现针对普通二叉树场景的设计取舍。复杂度分析阶段时间复杂度空间复杂度编码O(n)前序遍历每个节点恰好访问一次O(n)字符串存储 递归调用栈栈深为树高解码O(n)split线性切分、反转 O(n)、removeLast()每次 O(1)O(n)token 数组 重建出的树 递归栈这里的 n 是树的节点总数。编码与解码的复杂度都控制在O(n)且得益于removeLast()的栈式取元素技巧避免了数组头部移除带来的二次方开销——这正是前文反转步骤的意义所在。相关资源编码与解码的完整实现EncodeAndDecodeTree.swift可直接运行的 Playground 示例EncodeAndDecodeTree.playground/Contents.swift二叉树基础概念与递归结构Binary Tree/README.markdown若要深入学习节点有序的二叉搜索树可参考仓库中的 Binary Search Tree 与 AVL Tree 专题小结通过本文我们从为什么树需要编码出发完整走通了 Swift Algorithm Club 中二叉树序列化的全链路前序遍历保证顺序可重建分隔符消除节点边界歧义空哨兵显式记录缺失孩子三者共同构成一套自洽的编码规则解码侧则利用数组作栈 反转 removeLast的技巧以 O(n) 复杂度精确逆操作。这套方案同时是该主题在经典算法题库LeetCode 上的 Serialize and Deserialize Binary Tree中的标准解法思路理解了它也就掌握了绝大多数树结构序列化问题的方法论。本文基于 Swift Algorithm Club 的 Encode and Decode Tree 专题整理原文由 Kai Chen 与 Kelvin Lau 编写。【免费下载链接】swift-algorithm-clubAlgorithms and data structures in Swift, with explanations!项目地址: https://gitcode.com/gh_mirrors/sw/swift-algorithm-club创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考