本篇文章重点是介绍怎么用Swift语言来写树这种数据结构，并没有对树做过多的讲解。
通过一张图片来理解什么是树这种数据结构
Tree.png
上图展示了一个有5层的树。root根节点是第0层，每往下移动一个深度，层级加1。
用Swift来写树
编码是在Swift playground中完成的。
树这种数据结构是有节点组成的，所以先创建节点
class Node {
}
值
当然，一个节点得有值。简单来说，值value先定义为String类型，它不是可选类型，必须在init中初始化。完善Node如下
class Node {
var value: String
init(value: String) {
self.value = value
}
}
孩子节点
每一个节点都应该有一个可以添加节点的子节点的集合。完善Node如下
class Node {
var value: String
var children: [Node] = []
init(value: String) {
self.value = value
}
}
父节点
每个节点应该有一个指针指向它的父节点。子节点在下边，父节点在上边，每个节点最多有一个父节点，而父节点可以有多个子节点。完善Node如下
class Node {
var value: String
var children: [Node] = []
weak var parent: Node?
init(value: String) {
self.value = value
}
}
插入
不是所有的节点都有父节点，比如根节点，所有父节点属性是可选类型。用weak类型来避免循环引用。
插入父节点，完善Node如下
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
}
}
为了编译程序，需要添加一个继承CustomStringConvertible协议的一个扩展，完善Node如下
/ 1
extension Node: CustomStringConvertible {
// 2
var description: String {
// 3
var text = "\(value)"
// 4
if !children.isEmpty {
text += " {" + children.map { $0.description }.joined(separator: ", ") + "} "
}
return text
}
}
添加节点数据：
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)
打印树
打印结果如下：
beverages {hot {tea {black, green, chai} , coffee, cocoa} , cold {soda {ginger ale, bitter lemon} , milk} }
查找
添加查找方法,查找到，就返回该节点，否则返回nil
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
}
}
怎么换成其他类型的值呢？
节点值如果换成其他属性呢，比如是Int类型，可能就会是下边的修改了。
class Node {
var value: Int
// ...
}
通用
那要是换成Int, Double, Float类型或者自定义类型呢？接下来就要探究通用的方式了。
// 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
}
}
扩展的查找方法也要换成通用的啦
// 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
}
}
