聲明：算法和數(shù)據(jù)結(jié)構(gòu)的文章均是作者從github上翻譯過來串结，為方便大家閱讀。如果英語閱讀能力強(qiáng)的朋友跪妥，可以直接到swift算法俱樂部查看所有原文鞋喇，以便快速學(xué)習(xí)。作者同時(shí)也在學(xué)習(xí)中骗奖，歡迎交流
樹Trees
樹可以用來表示不同對(duì)象之間的分層關(guān)系确徙。如圖：
一個(gè)樹可以包含多個(gè)節(jié)點(diǎn)node醒串，一個(gè)節(jié)點(diǎn)通常有包含父節(jié)點(diǎn)和子節(jié)點(diǎn)执桌，不同的是，節(jié)點(diǎn)的父節(jié)點(diǎn)只能有一個(gè)芜赌，而子節(jié)點(diǎn)可以包含多個(gè)仰挣。需要注意的是，沒有父節(jié)點(diǎn)的節(jié)點(diǎn)缠沈，我們稱之為根root膘壶，而沒有子節(jié)點(diǎn)，我們稱之為葉leaf洲愤。
樹永遠(yuǎn)不會(huì)產(chǎn)生閉環(huán)颓芭，如下圖，這樣的結(jié)構(gòu)柬赐，我們稱之為圖像亡问，而不是樹。
目前我們現(xiàn)在描述的樹肛宋，是最簡(jiǎn)單的樹州藕，對(duì)節(jié)點(diǎn)以及葉的數(shù)量沒有任何限制，對(duì)節(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
}
}
以上為對(duì)樹的節(jié)點(diǎn)進(jìn)行描述床玻，這里的數(shù)據(jù)類型為T，可指向父節(jié)點(diǎn)parent沉帮，同時(shí)又含子節(jié)點(diǎn)數(shù)組children
我們可以對(duì)上述代碼進(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)
此時(shí)tree的value值為：
beverages {hot {tea {black, green, chai}, coffee, cocoa}, cold {soda {ginger ale, bitter lemon}, milk}}
其對(duì)應(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)严嗜。
對(duì)于每個(gè)節(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)可以多種多樣汗盘。比如，有時(shí)候你只需要每個(gè)節(jié)點(diǎn)只有2個(gè)子節(jié)點(diǎn)询一，而這樣的樹又稱之為二叉樹隐孽。樹的核心意義在于展示數(shù)據(jù)的邏輯層次，并且可以根據(jù)個(gè)人的需要而進(jìn)行調(diào)整健蕊，具有多樣性菱阵。
下面我們會(huì)描述一下如何用TreeNode來決定一個(gè)樹里面是否含有某個(gè)特定值。首先它會(huì)檢查節(jié)點(diǎn)或者根本身的值缩功，如果不匹配晴及，則檢查節(jié)點(diǎn)的子節(jié)點(diǎn)，如果不匹配嫡锌，同時(shí)節(jié)點(diǎn)的子節(jié)點(diǎn)仍然是節(jié)點(diǎn)而不是葉虑稼，則繼續(xù)檢索下去，一直到檢索完整個(gè)樹势木。
代碼如下：
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個(gè)子節(jié)點(diǎn)的樹蛛倦。二叉樹可以在許多種場(chǎng)景下使用，比如在使用二叉搜索樹的時(shí)候啦桌，我們要求節(jié)點(diǎn)是有順序的溯壶，左邊的數(shù)值要大于右邊，這部分知識(shí)我們會(huì)在下一個(gè)文章中講到震蒋。當(dāng)然茸塞，不是所有的二叉樹都有這樣的要求丰捷。
比如歧寺，我們可以用二叉樹來表示算術(shù)運(yùn)算操作(5 * (a - 10)) + (-4 * (3 / b))
代碼
在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)建梢杭，即從葉到根另凌。同時(shí)也可以添加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 = []]]]
另一個(gè)有用的拓展則是計(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.
在平時(shí)使用中菌仁，我們會(huì)需要遍歷整個(gè)樹結(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)算鲫寄，我們會(huì)得到以下順序的結(jié)果：
5
a
10
-
*
4
-
3
b
/
*
+
最先出現(xiàn)的是左邊的葉吉执，最晚出現(xiàn)的是頂部的根。
