作者：Kelvin Lau 性湿， 原文鏈接，原文日期：2016-07-11
譯者：Darin4lin

Swift算法俱樂部是GitHub上的一個開源項目模她，旨在用Swift實現(xiàn)一些主流的算法和數(shù)據(jù)結(jié)構(gòu)。

每個月我和Chris Pilcher將會根據(jù)這個開源項目編寫一些教程，向你們展示如何編寫一個cool的算法或數(shù)據(jù)結(jié)構(gòu)特姐。

第一篇教程會教你如何用Swift實現(xiàn)一個樹型數(shù)據(jù)結(jié)構(gòu)。這幾乎是最常見也是最有用的數(shù)據(jù)結(jié)構(gòu)黍氮，也是開始我們學(xué)習(xí)最好的方式唐含。

樹

看個圖就明白樹是什么了：

樹

上圖展示了個5層的樹。root是第0層沫浆，往下數(shù)捷枯，層數(shù)遞增1。

樹可以幫你解決很多重要的問題专执，例如：

• 表示對象之間的層級關(guān)系
• 高效的搜索
• 數(shù)據(jù)排序
• 有效的文字前綴匹配

相關(guān)術(shù)語

我們先來看一些需要掌握的術(shù)語淮捆。

根節(jié)點（Root）

根節(jié)點也就是第0層的節(jié)點。你也可以把它當(dāng)做你這個樹型數(shù)據(jù)結(jié)構(gòu)的入口本股。

根節(jié)點

節(jié)點（Node）

節(jié)點是樹里的一塊數(shù)據(jù)攀痊。節(jié)點里數(shù)據(jù)的數(shù)據(jù)類型取決于你構(gòu)造的這個樹的數(shù)據(jù)類型。根也是一個節(jié)點拄显。

節(jié)點

葉節(jié)點（Leaf）

葉節(jié)點就是一個沒有子節(jié)點的節(jié)點苟径，有時候可以把它看做一個終止節(jié)點。例如躬审，有一個節(jié)點的左孩子（leftChild）和右孩子（rightChild）都是nil棘街，那它就是一個葉節(jié)點。

葉

用Swift來實現(xiàn)樹

這一節(jié)里承边，你將會實現(xiàn)一個通用的樹遭殉。聲明一個沒有任何限制條件（例如一個節(jié)點只能最多有幾個子節(jié)點，或者節(jié)點的順序）的樹想來是極好的炒刁。

記住恩沽，樹是由節(jié)點組成的。所以我們先從創(chuàng)建一個基本的節(jié)點類開始翔始。新建一個Swift PlayGround然后添加如下代碼：

class Node {
 
}

節(jié)點值

當(dāng)然罗心，一個節(jié)點需要存儲一些數(shù)據(jù)才能顯得有意義。

先讓這個樹簡單的管理一些字符串吧城瞎。使用下面的代碼更新你的Node類渤闷。

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

你已經(jīng)聲明了一個String類型的Name屬性，還有一個init方法脖镀，用來初始化你的類中所有的非可選的存儲屬性飒箭。

子節(jié)點（Children）

除了一個節(jié)點值外，每個節(jié)點有需要有一個子節(jié)點的列表。

使用下面的代碼更新你的類弦蹂。

class Node {
  var value: String
  var children: [Node] = [] // add the children property
 
  init(value: String) {
    self.value = value
  }
}

簡單的使用一個Node類型的數(shù)組來表示子節(jié)點列表肩碟。每個子節(jié)點表示一個比當(dāng)前節(jié)點更深一層的節(jié)點。

父節(jié)點（Parent）

有時候有必要讓每個節(jié)點保存一個到他父節(jié)點的引用凸椿。一個節(jié)點只能有一個父節(jié)點削祈，但卻可以有很多子節(jié)點。

更新代碼：

class Node {
  var value: String
  var children: [Node] = []
  weak var parent: Node? // add the parent property
 
  init(value: String) {
    self.value = value
  }
}

可以注意到父節(jié)點是一個可選值。這是因為不是所有節(jié)點都有父節(jié)點 - 例如一個樹的根節(jié)點。

插入節(jié)點

為了向樹中插入節(jié)點胜榔，你需要在Node中定義一個add(child:)方法。更新如下：

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

通過PlayGround可以很好得來了解add(child:)是如何工作的吨拍。在你的Node類 外面 添加如下代碼：

let beverages = Node(value: "beverages")
 
let hotBeverages = Node(value: "hot")
let coldBeverages = Node(value: "cold")
 
beverages.add(child: hotBeverages)
beverages.add(child: coldBeverages)

這里我們定義了3個不同的節(jié)點并且將他們進行邏輯分層，就如下圖所示：

層次結(jié)構(gòu)

試煉：Beverage City

準(zhǔn)備來一個知識的快速檢測了嗎网杆？

嘗試寫一些代碼來把你的樹擴展成下圖所示：

Beverage City

先自己試試如何實現(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)

打印出你的樹

在控制臺把樹打印出來可以更好的檢驗?zāi)愕臉涫欠裾_羹饰。在定義完你的樹后，嘗試直接在控制臺打印出來：

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

你可以按下Command-Shift-Y組合鍵打開控制臺跛璧，而控制臺只打印出了你的類名严里。

Node

蠢的喲！不幸的是編譯器并不知道該如何打印你自定義的Swift類追城，除非你告訴了它。

為了幫助編譯器燥撞，你需要讓Node類實現(xiàn)CustomStringConvertible接口座柱。將下面的代碼添加在你的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. 擴展你的Node類并且實現(xiàn)CustomStringConvertible協(xié)議。這個協(xié)議需要你實現(xiàn)一個String類型的description計算屬性物舒。
2. description計算屬性是一個只讀屬性色洞，他返回一個String。
3. text變量用于保存整個字符串」诳瑁現(xiàn)在我們把當(dāng)前節(jié)點的值賦值給它火诸。
4. 除了打印當(dāng)前節(jié)點的值，你還需要打印所有子節(jié)點以及子節(jié)點的子節(jié)點的值荠察。所以置蜀，你需要遞歸得添加所有子節(jié)點的description，同時添加一些花括號來增強一些結(jié)構(gòu)感悉盆。

現(xiàn)在盯荤，當(dāng)你使用Print打印你的Node類時，你將會得到一個漂亮的打印結(jié)果：

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

提示：如果map語法使你感到迷惑焕盟，下面可能才是你寫過的代碼:

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

map是一個數(shù)據(jù)容器的方法秋秤，就比如Array。在所有實現(xiàn)了Sequence協(xié)議的數(shù)據(jù)容器中，你可以使用map來對容器中的每一個元素進行操作灼卢。在這里绍哎，你遍歷每一個子節(jié)點并且執(zhí)行一個字符串相加的操作。
想要學(xué)習(xí)更多有關(guān)map的知識鞋真，你可以查看這篇教程：Introduction to Functional Programming in Swift.

搜索

這個多功能的樹很適合描述分層次的數(shù)據(jù)蛇摸，但他需要什么其他的功能就要看你的App的需求了。例如灿巧，你可以使用這個類來在你的樹中查找某個確定的值赶袄。

為了方便對你的樹進行搜索，將以下的擴展添加到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
  }
}

代碼相當(dāng)直白：

1. 這個函數(shù)的目的是在樹中搜索一個值饿肺。如果成功，將包含這個值的節(jié)點返回盾似。如果沒有敬辣，返回nil。
2. 在這一行找到了目標(biāo)值零院，并且將self溉跃，也就是當(dāng)前節(jié)點返回。
3. 在這里循環(huán)遍歷children數(shù)組告抄。通過調(diào)用子節(jié)點的Search函數(shù)撰茎，遞歸得搜索所有子節(jié)點。如果有一個節(jié)點的值匹配打洼，if let語句將會返回這個非可選的節(jié)點龄糊。
4. 返回nil表示你找不到匹配的節(jié)點。

測試一下我們的Search函數(shù)吧募疮！在PlayGround的最下面添加如下代碼：

beverages.search(value: "cocoa") // returns the "cocoa" node
beverages.search(value: "chai") // returns the "chai" node
beverages.search(value: "bubbly") // returns nil

如果是不同的數(shù)據(jù)類型呢炫惩？

666，你已經(jīng)看我扯了這么久了阿浓！你已經(jīng)知道如何去實現(xiàn)一個存儲String類型數(shù)據(jù)的通用的樹了他嚷，并且定義了一個很棒的方式來在控制臺中打印你的樹，還提供了一個搜索的方法芭毙。

樹可以很好的組織你的分層結(jié)構(gòu)的String數(shù)據(jù)筋蓖，但如果你是想存儲整型數(shù)據(jù)呢？

你可以將Node類修改為Int類型的：

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

但是你用來接收String類型的那個類又不見了稿蹲。理想狀態(tài)下扭勉，你的Node類應(yīng)該可以用來接收所有類型的數(shù)據(jù)，而不論他是Int苛聘，Double還是Float涂炎，甚至是你自定義的類忠聚。為了使你的Node類更加通用，你需要進入泛型的世界唱捣！

泛型

泛型可以在算法與數(shù)據(jù)結(jié)構(gòu)中去除對數(shù)據(jù)類型的考慮两蟀。這可以讓你保持算法的通用性與可重用性。當(dāng)一個對象能存在一個樹中（或者其他數(shù)據(jù)結(jié)構(gòu)）那就不應(yīng)該考慮他是Int還是String震缭，而應(yīng)該考慮其他更重要的問題赂毯。任何適用于分層結(jié)構(gòu)的數(shù)據(jù)都可以用在樹型數(shù)據(jù)結(jié)構(gòu)中。

是時候做一些革命性改變了拣宰！更新你的代碼：

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

你會看到一些編譯錯誤党涕。別慌，你將會在適配完你的Node后清除所有的錯誤巡社。這是你這段代碼所做到的：

1. 你已經(jīng)將你的Node改為接受泛型參數(shù)T膛堤。<>告訴編譯器你正在使用泛型。
2. 你的目標(biāo)將Node改為允許接受任何類型晌该，所以你最好將value屬性改為T泛型而不是確定的Int或者String肥荔。
3. 同時將children也改為T泛型。
4. 更改init方法朝群。
5. add(child:)方法目前已經(jīng)可以接收當(dāng)前Node已經(jīng)定義的類型燕耿。

看上去還不錯。接下來姜胖，找到包含search方法的擴展并更新為使用泛型：

// 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. 你已經(jīng)將這個擴展限制為只有實現(xiàn)了Equatable協(xié)議的類型才能使用Search函數(shù)誉帅。
2. 將value參數(shù)更新為泛型。

你的代碼現(xiàn)在應(yīng)該可以編譯了谭期，測試一下堵第！在Playground的底部添加如下代碼類檢測你的泛型樹是否在正確工作：

let number = Node(value: 5)

恭喜！你實現(xiàn)了一個通用的樹隧出，并且兼容所有類型的數(shù)據(jù)！

更多鏈接

• AVL Tree
• B-Tree
• Binary Search Tree
• Binary Tree
• Minimum Spanning Tree (unweighted)
• Radix Tree
• Red-Black Tree
• Segment Tree
• Threaded Binary Tree
• Tries
• Union-Find