12.二叉树

在上一章中，你看了一棵基本的树，其中每个节点可以有许多子节点。binary tree是一棵树，每个节点最多拥有两个子节点，通常被称为left和right子类：

二叉树是许多树结构和算法的基础。在本章中，你将建立一棵二叉树，并了解三种最重要的树形遍历算法。

实施

打开本章的启动项目。创建一个新文件并命名为BinaryNode.swift。在这个文件中加入以下内容：

public class BinaryNode<Element> {

  public var value: Element
  public var leftChild: BinaryNode?
  public var rightChild: BinaryNode?

  public init(value: Element) {
    self.value = value
  }
}

在主Playground页面，添加以下内容：

var tree: BinaryNode<Int> = {
  let zero = BinaryNode(value: 0)
  let one = BinaryNode(value: 1)
  let five = BinaryNode(value: 5)
  let seven = BinaryNode(value: 7)
  let eight = BinaryNode(value: 8)
  let nine = BinaryNode(value: 9)

  seven.leftChild = one
  one.leftChild = zero
  one.rightChild = five
  seven.rightChild = nine
  nine.leftChild = eight

  return seven
}()

这段代码通过执行闭包定义了以下的树：

建立一个图表

建立一个数据结构的心理模型对学习它的工作原理有很大的帮助。为此，你将实现一个可重复使用的算法，帮助在控制台中实现二进制树的可视化。

Note

这个算法是基于Károly Lőrentey在他的书Optimizing Collections中的一个实现，可以从https://www.objc.io/books/optimizing-collections/。

在BinaryNode.swift的底部添加以下内容：

extension BinaryNode: CustomStringConvertible {

  public var description: String {
    diagram(for: self)
  }

  private func diagram(for node: BinaryNode?,
                       _ top: String = "",
                       _ root: String = "",
                       _ bottom: String = "") -> String {
    guard let node = node else {
      return root + "nil\n"
    }
    if node.leftChild == nil && node.rightChild == nil {
      return root + "\(node.value)\n"
    }
    return diagram(for: node.rightChild,
                   top + " ", top + "┌──", top + "│ ")
         + root + "\(node.value)\n"
         + diagram(for: node.leftChild,
                   bottom + "│ ", bottom + "└──", bottom + " ")
  }
}

diagram将递归地创建一个代表二叉树的字符串。要尝试它，请回到Playground，写下以下内容：

example(of: "tree diagram") {
  print(tree)
}

你应该看到以下控制台输出：

---Example of tree diagram---
 ┌──nil
┌──9
│ └──8
7
│ ┌──5
└──1
 └──0

在本书中，你将对其他二叉树使用此图。

遍历算法

之前，你看了一个树的level-order遍历。经过一些调整，你也可以使这种算法适用于二叉树。然而，与其重新实现级序遍历，你不如看看二叉树的三种遍历算法：in-order、pre-order和post-order的遍历。

顺序内(in-order)遍历

顺序遍历是按照以下顺序访问二叉树的节点，从根节点开始：

• 如果当前节点有一个左边的子节点，则首先递归地访问这个子节点。
• 然后，访问该节点本身。
• 如果当前节点有一个右边的子节点，就递归地访问这个子节点。

下面是你的例子树的内序遍历的样子：

你可能已经注意到，这是以升序打印的例子树。如果树的节点是以某种方式结构化的，那么内序遍历就会以升序访问它们 你将在下一章学习更多关于二进制搜索树的知识。

打开BinaryNode.swift，在文件的底部添加以下代码：

extension BinaryNode {

  public func traverseInOrder(visit: (Element) -> Void) {
    leftChild?.traverseInOrder(visit: visit)
    visit(value)
    rightChild?.traverseInOrder(visit: visit)
  }
}

按照上面的规则，在访问值之前，你首先遍历到最左边的节点。然后你再遍历到最右边的节点。回到Playground页面来测试一下。在页面的底部添加以下内容：

example(of: "in-order traversal") {
  tree.traverseInOrder { print($0) }
}

你应该在控制台看到以下内容：

---Example of in-order traversal---
0
1
5
7
8
9

前序(Pre-order)遍历

前序遍历总是先访问当前节点，然后递归地访问左边和右边的子节点：

在你的内序遍历方法下面写上以下内容：

public func traversePreOrder(visit: (Element) -> Void) {
  visit(value)
  leftChild?.traversePreOrder(visit: visit)
  rightChild?.traversePreOrder(visit: visit)
}

用以下代码进行测试：

example(of: "pre-order traversal") {
  tree.traversePreOrder { print($0) }
}

你应该在控制台看到以下输出：

---Example of pre-order traversal---
7
1
0
5
9
8

后序遍历

后序遍历只在左和右的子节点被遍历后访问当前节点。

换句话说，给定任何一个节点，你都会先访问它的子节点，再访问它自己。这样做的一个有趣的结果是，根节点总是最后被访问。

回到BinaryNode.swift中，在traversePreOrder下面写上以下内容：

public func traversePostOrder(visit: (Element) -> Void) {
  leftChild?.traversePostOrder(visit: visit)
  rightChild?.traversePostOrder(visit: visit)
  visit(value)
}

导航回到Playground页面进行尝试：

example(of: "post-order traversal") {
  tree.traversePostOrder { print($0) }
}

你应该在控制台看到以下内容：

---Example of post-order traversal---
0
5
1
8
9
7

这些遍历算法的时间和空间复杂度都是O(n)。你看到的是，内序遍历是以升序访问节点的。二叉树可以通过在插入时遵守一些规则来保证这一点。在下一章中，你将看到一个具有这些更严格语义的二叉树：二叉搜索树。

关键点

• 二叉树是一些最重要的树结构的基础。二进制search树和AVL树是对插入/删除行为施加限制的二进制树。
• In-order、pre-order和post-order的遍历不只是对二叉树很重要，如果你在任何树中处理数据，你会经常使用这些遍历。