Swift数据结构－树Trees 和二叉树Binary Tree

声明：算法和数据结构的文章均是作者从github上翻译过来，为方便大家阅读。如果英语阅读能力强的朋友，可以直接到swift算法俱乐部查看所有原文，以便快速学习。作者同时也在学习中，欢迎交流

树Trees

树可以用来表示不同对象之间的分层关系。如图：

树

一个树可以包含多个节点node，一个节点通常有包含父节点和子节点，不同的是，节点的父节点只能有一个，而子节点可以包含多个。需要注意的是，没有父节点的节点，我们称之为根root，而没有子节点，我们称之为叶leaf。

节点

树永远不会产生闭环，如下图，这样的结构，我们称之为图像，而不是树。

图表

目前我们现在描述的树，是最简单的树，对节点以及叶的数量没有任何限制，对节点的顺序等也没有特殊要求。

以下为树的swift代码：

public class TreeNode<T> {
  public var value: T

  public weak var parent: TreeNode?
  public var children = [TreeNode<T>]()

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

  public func addChild(_ node: TreeNode<T>) {
    children.append(node)
    node.parent = self
  }
}

以上为对树的节点进行描述，这里的数据类型为T，可指向父节点parent，同时又含子节点数组children

我们可以对上述代码进行拓展，添加description函数方便我们打印出完整的树结构：

extension TreeNode: CustomStringConvertible {
  public var description: String {
    var s = "\(value)"
    if !children.isEmpty {
      s += " {" + children.map { $0.description }.joined(separator: ", ") + "}"
    }
    return s
  }
}

在playground里输入以下代码:

let tree = TreeNode<String>(value: "beverages")

let hotNode = TreeNode<String>(value: "hot")
let coldNode = TreeNode<String>(value: "cold")

let teaNode = TreeNode<String>(value: "tea")
let coffeeNode = TreeNode<String>(value: "coffee")
let chocolateNode = TreeNode<String>(value: "cocoa")

let blackTeaNode = TreeNode<String>(value: "black")
let greenTeaNode = TreeNode<String>(value: "green")
let chaiTeaNode = TreeNode<String>(value: "chai")

let sodaNode = TreeNode<String>(value: "soda")
let milkNode = TreeNode<String>(value: "milk")

let gingerAleNode = TreeNode<String>(value: "ginger ale")
let bitterLemonNode = TreeNode<String>(value: "bitter lemon")

tree.addChild(hotNode)
tree.addChild(coldNode)

hotNode.addChild(teaNode)
hotNode.addChild(coffeeNode)
hotNode.addChild(chocolateNode)

coldNode.addChild(sodaNode)
coldNode.addChild(milkNode)

teaNode.addChild(blackTeaNode)
teaNode.addChild(greenTeaNode)
teaNode.addChild(chaiTeaNode)

sodaNode.addChild(gingerAleNode)
sodaNode.addChild(bitterLemonNode)

此时tree的value值为：
beverages {hot {tea {black, green, chai}, coffee, cocoa}, cold {soda {ginger ale, bitter lemon}, milk}}

其对应的结构为：

示例

这里的根是beverages，因为它没有父节点，而叶是black,green,chai,ginger ale,bitter lemon,coffee,cocoa,milk，因为它们没有子节点。

对于每个节点来说，你可以通过以下方法去获取它们的父节点
teaNode.parent // "hot" 节点 teaNode.parent!.parent // 根

通常情况下，我们用以下两种定义来说明树：
1.树高：树高指树的根到最底下的叶的距离，在我们的例子中，树高为3，因为从black到beverages需要跳三次。
2.节点深度：指任意节点到根的距离，例如tea到beverages的深度为2，而cold到beverages的深度为1.

树的结构可以多种多样。比如，有时候你只需要每个节点只有2个子节点，而这样的树又称之为二叉树。树的核心意义在于展示数据的逻辑层次，并且可以根据个人的需要而进行调整，具有多样性。

下面我们会描述一下如何用TreeNode来决定一个树里面是否含有某个特定值。首先它会检查节点或者根本身的值，如果不匹配，则检查节点的子节点，如果不匹配，同时节点的子节点仍然是节点而不是叶，则继续检索下去，一直到检索完整个树。

代码如下：

extension TreeNode where T: Equatable {
  func search(_ value: T) -> TreeNode? {
    if value == self.value {
      return self
    }
    for child in children {
      if let found = child.search(value) {
        return found
      }
    }
    return nil
  }
}

输入：

tree.search("cocoa")    // 返回 "cocoa" 节点
tree.search("chai")     // 返回 "chai" 节点
tree.search("bubbly")   //返回 nil

二叉树Binary Trees

二叉树是节点只能有0～2个子节点的树。二叉树可以在许多种场景下使用，比如在使用二叉搜索树的时候，我们要求节点是有顺序的，左边的数值要大于右边，这部分知识我们会在下一个文章中讲到。当然，不是所有的二叉树都有这样的要求。

比如，我们可以用二叉树来表示算术运算操作(5 * (a - 10)) + (-4 * (3 / b))

算术运算

代码

在swift中，我们可以用以下代码来表示二叉树：

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

实现上述算数运算：

// leaf nodes
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)

// intermediate nodes on the left
let Aminus10 = BinaryTree.node(nodeA, "-", node10)
let timesLeft = BinaryTree.node(node5, "*", Aminus10)

// intermediate nodes on the right
let minus4 = BinaryTree.node(.empty, "-", node4)
let divide3andB = BinaryTree.node(node3, "/", nodeB)
let timesRight = BinaryTree.node(minus4, "*", divide3andB)

// root node
let tree = BinaryTree.node(timesLeft, "+", timesRight)

在创建过程中，我们必须从下向上开始创建，即从叶到根。同时也可以添加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 ""
    }
  }
}

我们能得到

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 = []]]]

另一个有用的拓展则是计算树中的节点数：

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

在上述示例中，tree.count得到的结果为12.

在平时使用中，我们会需要遍历整个树结构从而达到某些目的。比如上述示例的运算过程，我们可以在树中按照一定顺序遍历而读取出它的方程式。通常情况下，遍历的方式有三种：
1.中序遍历：先看节点的左子节点，再看节点本身，然后它的右子节点。
2.先序遍历：先看节点，再看节点的左右子节点。
3.后序遍历：先看左右子节点，再看节点本身。

这三种遍历方法实现代码如下：

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)
    }
  }

如果我们用后序遍历来遍历示例的运算，我们会得到以下顺序的结果：

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

最先出现的是左边的叶，最晚出现的是顶部的根。