作者：Kelvin Lau ， 原文链接，原文日期：2016-07-11
译者：Darin4lin
Swift算法俱乐部是GitHub上的一个开源项目，旨在用Swift实现一些主流的算法和数据结构。
每个月我和Chris Pilcher将会根据这个开源项目编写一些教程，向你们展示如何编写一个cool的算法或数据结构。
第一篇教程会教你如何用Swift实现一个树型数据结构。这几乎是最常见也是最有用的数据结构，也是开始我们学习最好的方式。
树
看个图就明白树是什么了：
上图展示了个5层的树。root是第0层，往下数，层数递增1。
树可以帮你解决很多重要的问题，例如：
- 表示对象之间的层级关系
- 高效的搜索
- 数据排序
- 有效的文字前缀匹配
相关术语
我们先来看一些需要掌握的术语。
根节点（Root）
根节点也就是第0层的节点。你也可以把它当做你这个树型数据结构的入口。
节点（Node）
节点是树里的一块数据。节点里数据的数据类型取决于你构造的这个树的数据类型。根也是一个节点。
叶节点（Leaf）
叶节点就是一个没有子节点的节点，有时候可以把它看做一个终止节点。例如，有一个节点的左孩子（leftChild）和右孩子（rightChild）都是nil，那它就是一个叶节点。
用Swift来实现树
这一节里，你将会实现一个通用的树。声明一个没有任何限制条件（例如一个节点只能最多有几个子节点，或者节点的顺序）的树想来是极好的。
记住，树是由节点组成的。所以我们先从创建一个基本的节点类开始。新建一个Swift PlayGround然后添加如下代码：
class Node {
}
节点值
当然，一个节点需要存储一些数据才能显得有意义。
先让这个树简单的管理一些字符串吧。使用下面的代码更新你的Node类。
class Node {
var value: String
init(value: String) {
self.value = value
}
}
你已经声明了一个String类型的Name属性，还有一个init方法，用来初始化你的类中所有的非可选的存储属性。
子节点（Children）
除了一个节点值外，每个节点有需要有一个子节点的列表。
使用下面的代码更新你的类。
class Node {
var value: String
var children: [Node] = [] // add the children property
init(value: String) {
self.value = value
}
}
简单的使用一个Node类型的数组来表示子节点列表。每个子节点表示一个比当前节点更深一层的节点。
父节点（Parent）
有时候有必要让每个节点保存一个到他父节点的引用。一个节点只能有一个父节点，但却可以有很多子节点。
更新代码：
class Node {
var value: String
var children: [Node] = []
weak var parent: Node? // add the parent property
init(value: String) {
self.value = value
}
}
可以注意到父节点是一个可选值。这是因为不是所有节点都有父节点 - 例如一个树的根节点。
插入节点
为了向树中插入节点，你需要在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个不同的节点并且将他们进行逻辑分层，就如下图所示：
试炼：Beverage City
准备来一个知识的快速检测了吗？
尝试写一些代码来把你的树扩展成下图所示：
先自己试试如何实现吧~
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)
打印出你的树
在控制台把树打印出来可以更好的检验你的树是否正确。在定义完你的树后，尝试直接在控制台打印出来：
print(beverages) // <- try to print it!
你可以按下Command-Shift-Y组合键打开控制台，而控制台只打印出了你的类名。
Node
蠢的哟！不幸的是编译器并不知道该如何打印你自定义的Swift类，除非你告诉了它。
为了帮助编译器，你需要让Node类实现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
}
}
代码比较直白：
- 扩展你的Node类并且实现
CustomStringConvertible协议。这个协议需要你实现一个String类型的description计算属性。 -
description计算属性是一个只读属性，他返回一个String。 -
text变量用于保存整个字符串。现在我们把当前节点的值赋值给它。 - 除了打印当前节点的值，你还需要打印所有子节点以及子节点的子节点的值。所以，你需要递归得添加所有子节点的description，同时添加一些花括号来增强一些结构感。
现在，当你使用Print打印你的Node类时，你将会得到一个漂亮的打印结果：
"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是一个数据容器的方法，就比如Array。在所有实现了Sequence协议的数据容器中，你可以使用map来对容器中的每一个元素进行操作。在这里，你遍历每一个子节点并且执行一个字符串相加的操作。
想要学习更多有关map的知识，你可以查看这篇教程：Introduction to Functional Programming in Swift.
搜索
这个多功能的树很适合描述分层次的数据，但他需要什么其他的功能就要看你的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
}
}
代码相当直白：
- 这个函数的目的是在树中搜索一个值。如果成功，将包含这个值的节点返回。如果没有，返回nil。
- 在这一行找到了目标值，并且将
self，也就是当前节点返回。 - 在这里循环遍历
children数组。通过调用子节点的Search函数，递归得搜索所有子节点。如果有一个节点的值匹配，if let语句将会返回这个非可选的节点。 - 返回nil表示你找不到匹配的节点。
测试一下我们的Search函数吧！在PlayGround的最下面添加如下代码：
beverages.search(value: "cocoa") // returns the "cocoa" node
beverages.search(value: "chai") // returns the "chai" node
beverages.search(value: "bubbly") // returns nil
如果是不同的数据类型呢？
666，你已经看我扯了这么久了！你已经知道如何去实现一个存储String类型数据的通用的树了，并且定义了一个很棒的方式来在控制台中打印你的树，还提供了一个搜索的方法。
树可以很好的组织你的分层结构的String数据，但如果你是想存储整型数据呢？
你可以将Node类修改为Int类型的：
class Node {
var value: Int
// ...
}
但是你用来接收String类型的那个类又不见了。理想状态下，你的Node类应该可以用来接收所有类型的数据，而不论他是Int，Double还是Float，甚至是你自定义的类。为了使你的Node类更加通用，你需要进入泛型的世界！
泛型
泛型可以在算法与数据结构中去除对数据类型的考虑。这可以让你保持算法的通用性与可重用性。当一个对象能存在一个树中（或者其他数据结构）那就不应该考虑他是Int还是String，而应该考虑其他更重要的问题。任何适用于分层结构的数据都可以用在树型数据结构中。
是时候做一些革命性改变了！更新你的代码：
// 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后清除所有的错误。这是你这段代码所做到的：
- 你已经将你的Node改为接受泛型参数T。<>告诉编译器你正在使用泛型。
- 你的目标将Node改为允许接受任何类型，所以你最好将value属性改为T泛型而不是确定的
Int或者String。 - 同时将children也改为T泛型。
- 更改init方法。
-
add(child:)方法目前已经可以接收当前Node已经定义的类型。
看上去还不错。接下来，找到包含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
}
}
这里改了两个地方：
- 你已经将这个扩展限制为只有实现了
Equatable协议的类型才能使用Search函数。 - 将value参数更新为泛型。
你的代码现在应该可以编译了，测试一下！在Playground的底部添加如下代码类检测你的泛型树是否在正确工作：
let number = Node(value: 5)
恭喜！你实现了一个通用的树，并且兼容所有类型的数据！
