【数据结构与算法 - Swift实现】05 - 树 (Tree)
虽然我们在iOS开发中，很少接触树结构，但他是一种极其重要的数据结构。树也分很多种类：1）二叉树；2）二叉搜索树；3）平衡搜索树等。
在这篇文章里，我们先实现一个简单的树。
专业术语
在写代码之前，先学习一些树结构中的专业术语。
节点
树，是由节点组成的，每个节点存储了一些数据和他的子节点。图中的每个圆圈都是节点。
父节点和子节点
在观察树的时候，我们是从上往下看的。除了最顶部的节点以外，其他节点的上面都连接着一个节点，这个节点就叫父节点，而且每一个节点只有一个父节点；下面的节点就叫子节点。
根
树中最顶部的节点称为根，唯一一个没有父节点的节点。
叶节点
没有子节点的节点。
实现
TreeNode
根据刚刚的学习的知识点，我们可以写一个简单的TreeNode：
final class TreeNode<T> {
var value: T
private(set) var children: [TreeNode] = []
init(_ value: T) {
self.value = value
}
func addChild(_ child: TreeNode) {
children.append(child)
}
}
-
value：存储当前节点的值 -
children：存储所有子节点 -
addChild(_:)：添加子节点的方法
我们来尝试使用一下：
let products = TreeNode("Products")
let phone = TreeNode("Phone")
let computer = TreeNode("Computer")
products.addChild(phone)
products.addChild(computer)
上面的代码创建了这样一个树结构：
遍历算法
不同于遍历数组，遍历树结构会比较复杂一些：数组从头到尾遍历，但是树结构没有头和尾之说。在树结构中，我们可以使用深度优先遍历和层次顺序遍历。
深度优先遍历
从根开始，从最左边的树枝一直往下遍历，遍历完之后再遍历右边的树枝，直到所有树枝便利完为止。实现的代码如下：
func traverseDepthFirst(_ closure: (TreeNode) -> Void) {
closure(self)
children.forEach {
$0.traverseDepthFirst(closure)
}
}
我们来看一个例子：
let products = TreeNode("Products")
let phone = TreeNode("Phone")
let computer = TreeNode("Computer")
products.addChild(phone)
products.addChild(computer)
let iPhone8 = TreeNode("iPhone 8")
let iPhone8Plus = TreeNode("iPhone 8 Plus")
let iPhoneX = TreeNode("iPhone X")
let macBookPro = TreeNode("MacBook Pro")
let iMac = TreeNode("iMac")
let iMacPro = TreeNode("iMacPro")
phone.addChild(iPhone8)
phone.addChild(iPhone8Plus)
phone.addChild(iPhoneX)
computer.addChild(macBookPro)
computer.addChild(iMac)
computer.addChild(iMacPro)
上面的代码创建了这样一个树结构：
遍历：
products.traverseDepthFirst { print($0.value) }
// 结果
Products
Phone
iPhone 8
iPhone 8 Plus
iPhone X
Computer
MacBook Pro
iMac
iMacPro
层次顺序遍历
下图演示了如何区分层次：
代码实现如下：
func traverseLevelOrder(_ closure: (TreeNode) -> Void) {
closure(self)
var queue = Queue<TreeNode>()
children.forEach { queue.enqueue($0) }
while let node = queue.dequeue() {
closure(node)
node.children.forEach { queue.enqueue($0) }
}
}
把每一层的元素添加到队列中，保证树中的节点按层次顺序遍历。Queue的实现代码在上一篇文章: 【数据结构与算法 - Swift实现】04 - 队列 (Queue)，或者查看我在 GitHub 的 demo。
遍历：
products.traverseLevelOrder { print($0.value) }
// 结果
Products
Phone
Computer
iPhone 8
iPhone 8 Plus
iPhone X
MacBook Pro
iMac
iMacPro
总结
这篇文章介绍了树结构的一些专业术语；演示了用代码如何创建树结构；用两种方式实现对树的遍历。但是文章中介绍的树包含的范围非常广，对树的结构没有要求，接下来的文章我们将一起看看一些特别的、有实际用途的树。
完整代码 >>
参考资料
Data Structures and Algorithms in Swift --- raywenderlich.com，如果想看原版书籍，请点击链接购买。
完
欢迎加入我管理的Swift开发群：536353151。
