原文鏈接：Swift Algorithm Club: Swift Tree Data Structure
翻譯： coderJoey

Swift Algorithm Club是關(guān)于常用數(shù)據(jù)結(jié)構(gòu)及算法的Swift實(shí)現(xiàn)的一套開源教程概说。
這是該系列教程的第一課，我們將學(xué)習(xí)如何實(shí)現(xiàn)Swift 樹數(shù)據(jù)結(jié)構(gòu)究抓。 樹是最常用且非常有用的數(shù)據(jù)結(jié)構(gòu)之一闺阱！

樹

通過下面的圖片你可以很容易理解樹的概念：

樹能夠幫你解決很多問題列林，包括：

• 表示對(duì)象的層級(jí)關(guān)系
• 使查詢快速高效
• 能提供有序的數(shù)據(jù)鏈
• 文本的前綴匹配搜索

術(shù)語

首先，我們來介紹你應(yīng)該了解的關(guān)于樹的一些重要術(shù)語酪惭。

Root

root表示樹第0層的節(jié)點(diǎn)希痴。你可以把它當(dāng)做樹結(jié)構(gòu)的入口。

root

Node

node（節(jié)點(diǎn)）是樹結(jié)構(gòu)中的數(shù)據(jù)塊春感，節(jié)點(diǎn)所包含的數(shù)據(jù)類型取決于你對(duì)樹存儲(chǔ)類型的定義砌创。root也是節(jié)點(diǎn)，被稱為根節(jié)點(diǎn)甥厦。

node

Leaf

節(jié)點(diǎn)的層次關(guān)系就像父子關(guān)系一樣纺铭，當(dāng)節(jié)點(diǎn)沒有父節(jié)點(diǎn)的時(shí)候我們稱之為root根節(jié)點(diǎn)，而沒有孩子的節(jié)點(diǎn)我們就稱之為leaf（樹葉）刀疙。

leaf

Swift樹實(shí)現(xiàn)

目前我們只實(shí)現(xiàn)一種通用的樹結(jié)構(gòu)舶赔。我們實(shí)現(xiàn)的樹將沒有任何限制（例如孩子節(jié)點(diǎn)的個(gè)數(shù)的限制、節(jié)點(diǎn)的大小順序的限制等）谦秧。

樹是由節(jié)點(diǎn)組成的竟纳。首先，我們創(chuàng)建一個(gè)基本的節(jié)點(diǎn)類疚鲤。創(chuàng)建一個(gè)新的Swift playground 項(xiàng)目锥累，并添加下面的空類：

class Node {
  
}

Value

當(dāng)然，節(jié)點(diǎn)需要有與之關(guān)聯(lián)的數(shù)據(jù)才能被很好的使用集歇。
為了簡單桶略，先用樹來處理字符串類型的數(shù)據(jù)。像下面一樣更新剛剛創(chuàng)建的Node類：

class Node {
  var value: String
  
  init(value: String) {
    self.value = value
  }
}

這樣诲宇，你定義了一個(gè)String類型的value屬性际歼。同時(shí)，也聲明了一個(gè)構(gòu)造函數(shù)：此函數(shù)里面需要初始化所有類的非可選類型（non-optional）的屬性姑蓝。

Children

除了value之外鹅心，每個(gè)節(jié)點(diǎn)都需要有一個(gè)children列表。
像下面一樣更新你的Node類：

class Node {
  var value: String
  var children: [Node] = [] // 添加children屬性
  
  init(value: String) {
    self.value = value
  }
}

你定義了一個(gè)節(jié)點(diǎn)數(shù)組children纺荧。數(shù)組當(dāng)中的每一個(gè)元素（子節(jié)點(diǎn)）都比當(dāng)前節(jié)點(diǎn)多一個(gè)層次旭愧。

Parent

在樹的結(jié)構(gòu)中颅筋，父節(jié)點(diǎn)在節(jié)點(diǎn)的上面，子節(jié)點(diǎn)在節(jié)點(diǎn)的下面输枯。一個(gè)節(jié)點(diǎn)最多只有一個(gè)父節(jié)點(diǎn)（根節(jié)點(diǎn)沒有）议泵，但是可以有多個(gè)子節(jié)點(diǎn)。

再次更新Node類的實(shí)現(xiàn)：

class Node {
  var value: String
  var children: [Node] = []
  weak var parent: Node? // 添加parent屬性

  init(value: String) {
    self.value = value
  }
}

注意：這里的parent是可選類型用押，因?yàn)椴皇撬械墓?jié)點(diǎn)都有父節(jié)點(diǎn)-例如根節(jié)點(diǎn)肢簿。

插入

你將在Node類里面定義一個(gè)add(child:)方法來將新的節(jié)點(diǎn)插入到樹中。像這樣更新你的類：

class Node {
  var value: String
  var children: [Node] = []
  weak var parent: Node?

  init(value: String) {
    self.value = value
  }

  func add(child: Node) {
    children.append(child)
    child.parent = self
  }
}

理解** add(child: Node)**方法的最好方式是在playground上看看它的實(shí)時(shí)打印的結(jié)果蜻拨。將下面的代碼寫到playground（寫在Node類實(shí)現(xiàn)的外面）：

let beverages = Node(value: "beverages")

let hotBeverages = Node(value: "hot")
let coldBeverages = Node(value: "cold")

beverages.add(child: hotBeverages)
beverages.add(child: coldBeverages)

上面的代碼將3個(gè)不同的節(jié)點(diǎn)組織成下面的樹結(jié)構(gòu)：

挑戰(zhàn)：Beverage City

敢測試一下嗎池充？
嘗試用代碼拓展你的樹，使其結(jié)構(gòu)符合下面的圖片：

下面是解決方案缎讼，但是你可以自己先嘗試實(shí)現(xiàn)：

let beverages = Node(value: "beverages")

let hotBeverage = Node(value: "hot")
let coldBeverage = Node(value: "cold")

let tea = Node(value: "tea")
let coffee = Node(value: "coffee")
let cocoa = Node(value: "cocoa")

let blackTea = Node(value: "black")
let greenTea = Node(value: "green")
let chaiTea = Node(value: "chai")

let soda = Node(value: "soda")
let milk = Node(value: "milk")

let gingerAle = Node(value: "ginger ale")
let bitterLemon = Node(value: "bitter lemon")

beverages.add(child: hotBeverage)
beverages.add(child: coldBeverage)

hotBeverage.add(child: tea)
hotBeverage.add(child: coffee)
hotBeverage.add(child: cocoa)

coldBeverage.add(child: soda)
coldBeverage.add(child: milk)

tea.add(child: blackTea)
tea.add(child: greenTea)
tea.add(child: chaiTea)

soda.add(child: gingerAle)
soda.add(child: bitterLemon)

打印樹

如果不通過控制臺(tái)把書的層級(jí)結(jié)構(gòu)打印出來的話收夸，驗(yàn)證一個(gè)體積龐大的樹結(jié)構(gòu)是相當(dāng)困難的。現(xiàn)在我們嘗試將上面的樹打印出來：

print(beverages) // <- try to print it!

你可以使用組合鍵 Command-Shift-Y喚起控制臺(tái)血崭。然而你看到的打印結(jié)果是：

Node

傻嗶了卧惜！不幸的是編譯器根本不知道怎么樣打印出你所希望的對(duì)象描述，除非你告訴它該怎么打印夹纫。

如何告訴編譯器咽瓷？你需要讓Node遵守CustomStringConvertable協(xié)議。我們將下面的代碼添加到Node 類的下面舰讹。

// 1
extension Node: CustomStringConvertible {
  // 2
  var description: String {
    // 3
    var text = "\(value)"
    
   // 4
    if !children.isEmpty {
      text += " {" + children.map { $0.description }.joinWithSeparator(", ") + "} "
    }
    return text
  }
}

上面代碼做了什么：

1. 聲明了一個(gè)Node類的擴(kuò)展茅姜，而且遵守了CustomStringConvertable協(xié)議。這個(gè)協(xié)議希望你實(shí)現(xiàn)String類型的description月匣，這里的description為計(jì)算型屬性（computed property）钻洒。

2. 定義description屬性，它的返回類型是String锄开，而且是只讀的素标。

3. 定義一個(gè)將輸出所有內(nèi)容的text變量，目前只包含節(jié)點(diǎn)本身的值萍悴。

4. 除了打印節(jié)點(diǎn)的當(dāng)前值之外头遭，還需要打印子節(jié)點(diǎn)，子節(jié)點(diǎn)的子節(jié)點(diǎn)等癣诱，一直到打印完所有節(jié)點(diǎn)任岸。所以，你需要用遞歸地方式拼接所有子節(jié)點(diǎn)描述狡刘，同時(shí)為區(qū)分層次結(jié)構(gòu)，我們將同一層次的子節(jié)點(diǎn)用花括號(hào)括起來困鸥。

現(xiàn)在打印Node的內(nèi)容嗅蔬，你將看到不錯(cuò)的樹結(jié)構(gòu)：

"beverages {hot {tea {black, green, chai} , coffee, cocoa} , cold {soda {ginger ale, bitter lemon} , milk} } \n"

注意：如果上面的map語法讓你困惑的話剑按，你可以替換成下面的寫法：

if !children.isEmpty {
  text += " {"
  for child in children {
    text += child.description + ", "
  }
  text += "} "
}

map作用于像數(shù)組這樣的集合對(duì)象。通過遵守SequenceType協(xié)議澜术，map允許您對(duì)數(shù)組的每個(gè)元素執(zhí)行操作艺蝴。對(duì)你而言，剛剛做的事情就是遍歷子節(jié)點(diǎn)并用自定義的字符串將其拼接起來鸟废。

你可以點(diǎn)擊這里來了解更多關(guān)于map的知識(shí)猜敢。

查詢

這里實(shí)現(xiàn)的通用樹非常適合描述層次分明的數(shù)據(jù)類型，但如果需要讓其更好的服務(wù)你的應(yīng)用程序盒延，那就需要添加一些額外功能方法缩擂。例如你想通過Node類判斷樹中是否包含一個(gè)指定的值。

為實(shí)現(xiàn)樹的查詢算法添寺，將下面的代碼添加到你的playground：

extension Node {
  // 1
  func search(value: String) -> Node? {
    // 2
    if value == self.value {
      return self
    }
    // 3
    for child in children {
      if let found = child.search(value: value) {
        return found
      }
    }
    // 4
    return nil
  }
}

代碼很簡單：

1. 該方法的目的是查找一個(gè)指定的值是否在樹中存在胯盯。存在的話返回與之關(guān)聯(lián)的節(jié)點(diǎn)對(duì)象，不存在的話就返回空（nil）计露。

2. 這是找到該值的情況博脑。你將返回當(dāng)前節(jié)點(diǎn)self。

3. 在這個(gè)循環(huán)中票罐，你將循環(huán)訪問children數(shù)組叉趣，遞歸遍歷所有的子節(jié)點(diǎn)并調(diào)用子節(jié)點(diǎn)的查詢方法。如果有任何一個(gè)節(jié)點(diǎn)的值與指定值相同该押，if let語句將捕獲該節(jié)點(diǎn)并返回它疗杉。

4. 你將返回nil（這表示沒有查詢到相應(yīng)的值）。

來測試一下我們的查詢方法沈善！在playground底部乡数，我們添加如下代碼：

beverages.search(value: "cocoa") // 返回 "cocoa" 節(jié)點(diǎn)
beverages.search(value: "chai") // 返回 "chai" 節(jié)點(diǎn)
beverages.search(value: "bubbly") // 返回 nil

其他類型

到目前為止，你已經(jīng)實(shí)現(xiàn)了一個(gè)存儲(chǔ)String值的通用樹結(jié)構(gòu)闻牡。你提供了一個(gè)將樹打印到控制臺(tái)的優(yōu)雅的方式净赴。而且為Node類添增加了搜索的能力。

樹能夠展示字符串的層級(jí)結(jié)構(gòu)罩润，但如果存儲(chǔ)的不是字符串而是整數(shù)呢玖翅？

你可能會(huì)將Node的類型改成Int:

class Node {
  var value: Int
  
  // ...
}

但是這樣的話，之前能接收String類型的實(shí)現(xiàn)就沒有了割以。理想的情況是金度，不管是Int、Double严沥、Float還是自定義的類型猜极，Node都能接收。為了讓Node類通用消玄，你就得使用泛型跟伏！

泛型

泛型的思路源于算法和數(shù)據(jù)結(jié)構(gòu)需要抽象的需求丢胚。思路的核心是通用和復(fù)用。不管是Int受扳、String還是其他類型都應(yīng)該很容易的應(yīng)用到樹結(jié)構(gòu)携龟。

是時(shí)候進(jìn)行一次大的改變了！將Node實(shí)現(xiàn)改成下面代碼：

// 1. 
class Node<T>{
  // 2. 
  var value: T
  weak var parent: Node?
  // 3.
  var children: [Node] = []
  
  // 4.
  init(value: T) {
    self.value = value
  }
  
  func add(child: Node) {
    children.append(child)
    child.parent = self
  }
}

現(xiàn)在你可能發(fā)現(xiàn)一些編譯的錯(cuò)誤勘高。別急峡蟋！等我們將Node類中多有實(shí)現(xiàn)的類型改為通用類型后錯(cuò)誤就會(huì)消除。我們先看看上面的代碼：

1. 你將Node類定義為泛型华望。T外面的標(biāo)識(shí)符<>的作用是告訴編譯器這里使用泛型蕊蝗。

2. 你的目的是要讓Node類存儲(chǔ)任何類型，所以要將value屬性改寫成泛型T而不是Int或者String

3. 同理將子節(jié)點(diǎn)的類型改寫成泛型T

4. 更新構(gòu)造器立美，使其接收任何類型匿又。

下一步是將我們的實(shí)現(xiàn)search方法的類擴(kuò)展也更新為泛型：

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

這里的兩處改變：

1. 為使得search方法能繼續(xù)使用，你應(yīng)該保證value是任意類型時(shí)都是可以能判斷是否相等的建蹄，這樣就需要遵守Equatable協(xié)議碌更。

2. 將value屬性改寫成泛型T

至此你的代碼應(yīng)該可以編譯了，現(xiàn)在我們測試一下洞慎。在你的playground底部添加如下代碼來驗(yàn)證泛型樹是否能用：

let number = Node(value: 5)

恭喜痛单！你已經(jīng)完成一個(gè)適用于任何數(shù)據(jù)類型的通用樹。

其他樹

你在這里創(chuàng)建了一個(gè)非尘⑼龋基本的樹結(jié)構(gòu)旭绒，除此之外還有很多種不同的構(gòu)建樹的方式，例如：

• 有些樹結(jié)構(gòu)根本不需要parent這個(gè)屬性焦人。
• 有時(shí)候可能需要給節(jié)點(diǎn)賦一個(gè)比它的兩個(gè)子節(jié)點(diǎn)都大的值挥吵，就像二叉樹一樣。
• 二叉搜索樹（BST）是另一種非常常見的樹結(jié)構(gòu)花椭，它是節(jié)點(diǎn)排序規(guī)則更加嚴(yán)格的二叉樹忽匈，它是查詢速度更快的二叉樹結(jié)構(gòu)。

了解更多關(guān)于樹數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí)矿辽，請(qǐng)點(diǎn)擊下面由Swift Algorithm Club開源的樹列表:

• 平衡二叉樹
• 多路搜索樹
• 二叉搜索樹
• 二叉樹
• 最小生成樹(unweighted)
• 基數(shù)樹
• 紅黑樹
• 線段樹
• 二叉線索樹
• 單詞查找樹
• 并查樹

何去何從

更多Swift算法和數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)及討論丹允，Swift Algorithm Club