聲明：算法和數(shù)據(jù)結(jié)構(gòu)的文章均是作者從github上翻譯過來，為方便大家閱讀。如果英語閱讀能力強(qiáng)的朋友，可以直接到swift算法俱樂部查看所有原文，以便快速學(xué)習(xí)。作者同時也在學(xué)習(xí)中，歡迎交流

樹Trees

樹可以用來表示不同對象之間的分層關(guān)系。如圖：

樹

一個樹可以包含多個節(jié)點(diǎn)node，一個節(jié)點(diǎn)通常有包含父節(jié)點(diǎn)和子節(jié)點(diǎn)，不同的是，節(jié)點(diǎn)的父節(jié)點(diǎn)只能有一個，而子節(jié)點(diǎn)可以包含多個。需要注意的是，沒有父節(jié)點(diǎn)的節(jié)點(diǎn)，我們稱之為根root，而沒有子節(jié)點(diǎn)，我們稱之為葉leaf。

節(jié)點(diǎn)

樹永遠(yuǎn)不會產(chǎn)生閉環(huán)，如下圖，這樣的結(jié)構(gòu)，我們稱之為圖像，而不是樹。

圖表

目前我們現(xiàn)在描述的樹，是最簡單的樹，對節(jié)點(diǎn)以及葉的數(shù)量沒有任何限制，對節(jié)點(diǎn)的順序等也沒有特殊要求。

以下為樹的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
  }
}

以上為對樹的節(jié)點(diǎn)進(jìn)行描述，這里的數(shù)據(jù)類型為T，可指向父節(jié)點(diǎn)parent，同時又含子節(jié)點(diǎn)數(shù)組children

我們可以對上述代碼進(jìn)行拓展，添加description函數(shù)方便我們打印出完整的樹結(jié)構(gòu)：

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

其對應(yīng)的結(jié)構(gòu)為：

示例

這里的根是beverages，因?yàn)樗鼪]有父節(jié)點(diǎn)，而葉是black,green,chai,ginger ale,bitter lemon,coffee,cocoa,milk，因?yàn)樗鼈儧]有子節(jié)點(diǎn)。

對于每個節(jié)點(diǎn)來說，你可以通過以下方法去獲取它們的父節(jié)點(diǎn)
teaNode.parent // "hot" 節(jié)點(diǎn) teaNode.parent!.parent // 根

通常情況下，我們用以下兩種定義來說明樹：
1.樹高：樹高指樹的根到最底下的葉的距離，在我們的例子中，樹高為3，因?yàn)閺?code>black到beverages需要跳三次。
2.節(jié)點(diǎn)深度：指任意節(jié)點(diǎn)到根的距離，例如tea到beverages的深度為2，而cold到beverages的深度為1.

樹的結(jié)構(gòu)可以多種多樣。比如，有時候你只需要每個節(jié)點(diǎn)只有2個子節(jié)點(diǎn)，而這樣的樹又稱之為二叉樹。樹的核心意義在于展示數(shù)據(jù)的邏輯層次，并且可以根據(jù)個人的需要而進(jìn)行調(diào)整，具有多樣性。

下面我們會描述一下如何用TreeNode來決定一個樹里面是否含有某個特定值。首先它會檢查節(jié)點(diǎn)或者根本身的值，如果不匹配，則檢查節(jié)點(diǎn)的子節(jié)點(diǎn)，如果不匹配，同時節(jié)點(diǎn)的子節(jié)點(diǎn)仍然是節(jié)點(diǎn)而不是葉，則繼續(xù)檢索下去，一直到檢索完整個樹。

代碼如下：

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" 節(jié)點(diǎn)
tree.search("chai")     // 返回 "chai" 節(jié)點(diǎn)
tree.search("bubbly")   //返回 nil

二叉樹Binary Trees

二叉樹是節(jié)點(diǎn)只能有0～2個子節(jié)點(diǎn)的樹。二叉樹可以在許多種場景下使用，比如在使用二叉搜索樹的時候，我們要求節(jié)點(diǎn)是有順序的，左邊的數(shù)值要大于右邊，這部分知識我們會在下一個文章中講到。當(dāng)然，不是所有的二叉樹都有這樣的要求。

比如，我們可以用二叉樹來表示算術(shù)運(yùn)算操作(5 * (a - 10)) + (-4 * (3 / b))

算術(shù)運(yùn)算

代碼

在swift中，我們可以用以下代碼來表示二叉樹：

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

實(shí)現(xiàn)上述算數(shù)運(yùn)算：

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

在創(chuàng)建過程中，我們必須從下向上開始創(chuàng)建，即從葉到根。同時也可以添加description函數(shù)，方便輸出。

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

另一個有用的拓展則是計(jì)算樹中的節(jié)點(diǎn)數(shù)：

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

在上述示例中，tree.count得到的結(jié)果為12.

在平時使用中，我們會需要遍歷整個樹結(jié)構(gòu)從而達(dá)到某些目的。比如上述示例的運(yùn)算過程，我們可以在樹中按照一定順序遍歷而讀取出它的方程式。通常情況下，遍歷的方式有三種：
1.中序遍歷：先看節(jié)點(diǎn)的左子節(jié)點(diǎn)，再看節(jié)點(diǎn)本身，然后它的右子節(jié)點(diǎn)。
2.先序遍歷：先看節(jié)點(diǎn)，再看節(jié)點(diǎn)的左右子節(jié)點(diǎn)。
3.后序遍歷：先看左右子節(jié)點(diǎn)，再看節(jié)點(diǎn)本身。

這三種遍歷方法實(shí)現(xiàn)代碼如下：

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

如果我們用后序遍歷來遍歷示例的運(yùn)算，我們會得到以下順序的結(jié)果：

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

最先出現(xiàn)的是左邊的葉，最晚出現(xiàn)的是頂部的根。