原文链接：Swift Algorithm Club: Swift Tree Data Structure
翻译： coderJoey

Swift Algorithm Club是关于常用数据结构及算法的Swift实现的一套开源教程。
这是该系列教程的第一课，我们将学习如何实现Swift 树数据结构。 树是最常用且非常有用的数据结构之一！

树

通过下面的图片你可以很容易理解树的概念：

树能够帮你解决很多问题，包括：

• 表示对象的层级关系
• 使查询快速高效
• 能提供有序的数据链
• 文本的前缀匹配搜索

术语

首先，我们来介绍你应该了解的关于树的一些重要术语。

Root

root表示树第0层的节点。你可以把它当做树结构的入口。

root

Node

node（节点）是树结构中的数据块，节点所包含的数据类型取决于你对树存储类型的定义。root也是节点，被称为根节点。

node

Leaf

节点的层次关系就像父子关系一样，当节点没有父节点的时候我们称之为root根节点，而没有孩子的节点我们就称之为leaf（树叶）。

leaf

Swift树实现

目前我们只实现一种通用的树结构。我们实现的树将没有任何限制（例如孩子节点的个数的限制、节点的大小顺序的限制等）。

树是由节点组成的。首先，我们创建一个基本的节点类。创建一个新的Swift playground 项目，并添加下面的空类：

class Node {
  
}

Value

当然，节点需要有与之关联的数据才能被很好的使用。
为了简单，先用树来处理字符串类型的数据。像下面一样更新刚刚创建的Node类：

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

这样，你定义了一个String类型的value属性。同时，也声明了一个构造函数：此函数里面需要初始化所有类的非可选类型（non-optional）的属性。

Children

除了value之外，每个节点都需要有一个children列表。
像下面一样更新你的Node类：

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

你定义了一个节点数组children。数组当中的每一个元素（子节点）都比当前节点多一个层次。

Parent

在树的结构中，父节点在节点的上面，子节点在节点的下面。一个节点最多只有一个父节点（根节点没有），但是可以有多个子节点。

再次更新Node类的实现：

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

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

注意：这里的parent是可选类型，因为不是所有的节点都有父节点-例如根节点。

插入

你将在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
  }
}

理解** add(child: Node)**方法的最好方式是在playground上看看它的实时打印的结果。将下面的代码写到playground（写在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

傻哔了！不幸的是编译器根本不知道怎么样打印出你所希望的对象描述，除非你告诉它该怎么打印。

如何告诉编译器？你需要让Node遵守CustomStringConvertable协议。我们将下面的代码添加到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类的扩展，而且遵守了CustomStringConvertable协议。这个协议希望你实现String类型的description，这里的description为计算型属性（computed property）。

2. 定义description属性，它的返回类型是String，而且是只读的。

3. 定义一个将输出所有内容的text变量，目前只包含节点本身的值。

4. 除了打印节点的当前值之外，还需要打印子节点，子节点的子节点等，一直到打印完所有节点。所以，你需要用递归地方式拼接所有子节点描述，同时为区分层次结构，我们将同一层次的子节点用花括号括起来。

现在打印Node的内容，你将看到不错的树结构：

"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作用于像数组这样的集合对象。通过遵守SequenceType协议，map允许您对数组的每个元素执行操作。对你而言，刚刚做的事情就是遍历子节点并用自定义的字符串将其拼接起来。

你可以点击这里来了解更多关于map的知识。

查询

这里实现的通用树非常适合描述层次分明的数据类型，但如果需要让其更好的服务你的应用程序，那就需要添加一些额外功能方法。例如你想通过Node类判断树中是否包含一个指定的值。

为实现树的查询算法，将下面的代码添加到你的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. 该方法的目的是查找一个指定的值是否在树中存在。存在的话返回与之关联的节点对象，不存在的话就返回空（nil）。

2. 这是找到该值的情况。你将返回当前节点self。

3. 在这个循环中，你将循环访问children数组，递归遍历所有的子节点并调用子节点的查询方法。如果有任何一个节点的值与指定值相同，if let语句将捕获该节点并返回它。

4. 你将返回nil（这表示没有查询到相应的值）。

来测试一下我们的查询方法！在playground底部，我们添加如下代码：

beverages.search(value: "cocoa") // 返回 "cocoa" 节点
beverages.search(value: "chai") // 返回 "chai" 节点
beverages.search(value: "bubbly") // 返回 nil

其他类型

到目前为止，你已经实现了一个存储String值的通用树结构。你提供了一个将树打印到控制台的优雅的方式。而且为Node类添增加了搜索的能力。

树能够展示字符串的层级结构，但如果存储的不是字符串而是整数呢？

你可能会将Node的类型改成Int:

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

但是这样的话，之前能接收String类型的实现就没有了。理想的情况是，不管是Int、Double、Float还是自定义的类型，Node都能接收。为了让Node类通用，你就得使用泛型！

泛型

泛型的思路源于算法和数据结构需要抽象的需求。思路的核心是通用和复用。不管是Int、String还是其他类型都应该很容易的应用到树结构。

是时候进行一次大的改变了！将Node实现改成下面代码：

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

现在你可能发现一些编译的错误。别急！等我们将Node类中多有实现的类型改为通用类型后错误就会消除。我们先看看上面的代码：

1. 你将Node类定义为泛型。T外面的标识符<>的作用是告诉编译器这里使用泛型。

2. 你的目的是要让Node类存储任何类型，所以要将value属性改写成泛型T而不是Int或者String

3. 同理将子节点的类型改写成泛型T

4. 更新构造器，使其接收任何类型。

下一步是将我们的实现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. 为使得search方法能继续使用，你应该保证value是任意类型时都是可以能判断是否相等的，这样就需要遵守Equatable协议。

2. 将value属性改写成泛型T

至此你的代码应该可以编译了，现在我们测试一下。在你的playground底部添加如下代码来验证泛型树是否能用：

let number = Node(value: 5)

恭喜！你已经完成一个适用于任何数据类型的通用树。

其他树

你在这里创建了一个非常基本的树结构，除此之外还有很多种不同的构建树的方式，例如：

• 有些树结构根本不需要parent这个属性。
• 有时候可能需要给节点赋一个比它的两个子节点都大的值，就像二叉树一样。
• 二叉搜索树（BST）是另一种非常常见的树结构，它是节点排序规则更加严格的二叉树，它是查询速度更快的二叉树结构。

了解更多关于树数据结构的相关知识，请点击下面由Swift Algorithm Club开源的树列表:

• 平衡二叉树
• 多路搜索树
• 二叉搜索树
• 二叉树
• 最小生成树(unweighted)
• 基数树
• 红黑树
• 线段树
• 二叉线索树
• 单词查找树
• 并查树

何去何从

更多Swift算法和数据结构实现及讨论，Swift Algorithm Club