Swift数据结构和算法（二）

Posted on Edited on

第三部分：树

第十章：树

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

  • 表示层次关系。

  • 管理排序的数据。

  • 促进快速查找操作。

相关术语

  • 节点（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()
    }
}