Swift数据结构和算法(二)

第三部分:树

第十章:树

树在数据结构中相当重要。它用于解决软件开发中的许多反复出现的挑战:

  • 表示层次关系。

  • 管理排序的数据。

  • 促进快速查找操作。

相关术语

  • 节点(Node)
  • 父子(Parent and child)
  • 根(Root)
  • 叶子(Leaf)

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
public class TreeNode<T> {

public var value: T
public var children: [TreeNode] = []

public init(_ value: T) {
self.value = value
}

public func add(_ child: TreeNode) {
children.append(child)
}
}

遍历算法

遍历线性的集合(如:数组和链表)是非常直接的。因为有直接的首尾。

但是遍历树就复杂了。是左边优先,还是深度优先,要看具体解决的问题。

深度优先遍历(Depth-first traversal)
1
2
3
4
5
6
7
8
extension TreeNode {
public func forEachDepthFirst(visit: (TreeNode) -> Void) {
visit(self)
children.forEach {
$0.forEachDepthFirst(visit: visit)
}
}
}
层级优先遍历(Level-order traversal)
1
2
3
4
5
6
7
8
9
10
11
extension TreeNode {
public func forEachLevelOrder(visit: (TreeNode) -> Void) {
visit(self)
var queue = Queue<TreeNode>()
children.forEach { queue.enqueue($0) }
while let node = queue.dequeue() {
visit(node)
node.children.forEach { queue.enqueue($0) }
}
}
}
搜索
1
2
3
4
5
6
7
8
9
10
11
extension TreeNode where T: Equatable {
public func search(_ value: T) -> TreeNode? {
var result: TreeNode?
forEachDepthFirst { node in
if node.value == value {
result = node
}
}
return result
}
}

总结

  1. 树与链接列表具有一些相似之处,但是,链接列表节点只能链接到另一个节点,而树节点可以链接到无限多个节点。
  2. 熟悉树的术语,例如父,子,叶子和根。 这些术语中有许多是其他程序员常用的语言,将用于帮助解释其他树形结构。
  3. 遍历(例如深度优先遍历和层级遍历)不是特定于常规树的。 它们也可以在其他树上工作,尽管根据树的结构,它们的实现会略有不同。

第十一章:树挑战

打印所有的值,按照他们层级的顺序。同意层级应该打印在一行

例如:

1
2
3
15 
1 17 20
1 5 0 2 5 7

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func printEachLevel<T>(for tree: TreeNode<T>) {
var queue = Queue<TreeNode<T>>()

/// 加入每层的节点计数,当打印完时,换行
var nodesLeftInCurrentLevel = 0

queue.enqueue(tree)
while !queue.isEmpty {
nodesLeftInCurrentLevel = queue.count
while nodesLeftInCurrentLevel > 0 {
guard let node = queue.dequeue() else { break }
print("\(node.value) ", terminator: "")
node.children.forEach { queue.enqueue($0) }
nodesLeftInCurrentLevel -= 1
}
print()
}
}