第12章：二叉树
在上一章中，你看了一棵基本的树，其中每个节点都可以有很多孩子。二叉树是一棵树，其中每个节点最多有两个孩子，通常被称为左和右孩子。
二叉树是许多树结构和算法的基础。在本章中，你将建立一棵二叉树，并了解三种最重要的树形遍历算法。
实现
打开本章的启动项目。创建一个新文件，命名为BinaryNode.swift。在这个文件中加入以下内容。
在主playground页面，添加以下内容。
这段代码通过执行闭包定义了以下的树。
构建图表
建立一个数据结构的心理模型对学习它的工作原理有相当大的帮助。为此，你将实现一个可重复使用的算法，帮助在控制台中可视化一个二叉树。
注意：这个算法是基于Károly Lőrentey在他的《优化集合》一书中的实现，可从https://www.objc.io/books/ optimizing-collections/。
在BinaryNode.swift的底部添加以下内容。
diagram将递归地创建一个代表二叉树的字符串。要尝试一下，请回到playground，写下以下内容。
example(of: "tree diagram") {
print(tree)
}
你应该看到以下控制台输出。
在本书中，你将对其他二叉树使用此图。
遍历算法
之前，你看了树的级序遍历。通过一些调整，你也可以使这种算法适用于二叉树。然而，与其重新实现级序遍历，你不如看看二叉树的三种遍历算法：内序、前序和后序遍历。
按序遍历
按序遍历是按照以下顺序访问二叉树的节点，从根节点开始。
-
如果当前节点有一个左边的子节点，则首先递归地访问这个子节点。
-
然后，访问该节点本身。
-
如果当前节点有一个右边的子节点，就递归地访问这个子节点。下面是你的例子树的按序遍历的样子。
你可能已经注意到，这是按升序打印的例子树。如果树的节点是以某种方式结构化的，那么内序遍历就会以升序访问它们 你将在下一章中学习更多关于二进制搜索树的知识。
打开BinaryNode.swift，在文件的底部添加以下代码。
按照上面的规则，在访问值之前，你首先遍历到最左边的节点。然后你再遍历到最右边的节点。回到playground页面来测试一下。在页面的底部添加以下内容。
example(of: "in-order traversal") { tree.traverseInOrder { print($0) } }
你应该在控制台中看到以下内容。
前序遍历
前序遍历总是先访问当前节点，然后递归地访问左边和右边的子节点。
在你的顺序内遍历方法下面写上以下内容。
用下面的代码进行测试。
example(of: "pre-order traversal") {
tree.traversePreOrder { print($0) }
}
你应该在控制台看到以下输出。
后序遍历
后序遍历只在左和右的子节点被递归访问之后访问当前节点。
换句话说，给定任何一个节点，你都会在访问其自身之前访问其子节点。这样做的一个有趣的结果是，根节点总是被最后访问。
回到BinaryNode.swift里面，写下下面的traversePreOrder。
导航回playground页面进行尝试。
example(of: "post-order traversal") {
tree.traversePostOrder { print($0) }
}
你应该在控制台看到以下内容。
这些遍历算法的时间和空间复杂性都是O(n)。你看到内序遍历是以升序访问节点的。二叉树可以通过在插入时遵守一些规则来保证这一点。在下一章中，你将看到一个具有这些更严格语义的二叉树：二叉搜索树。
关键点
-
二叉树是一些最重要的树结构的基础。 二进制搜索树和AVL树是对插入/删除行为施加限制的二进制树。
-
顺序，前序和后序的遍历不只是对二叉树很重要，如果你在任何树中处理数据，你会经常使用这些遍历。
| 上一章 | 目录 | 下一章 |
|---|