Fork me on GitHub

【译】Swift算法俱乐部-二叉树

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Clubraywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下,大概有一百左右个的算法和数据结构,基本上常见的都包含了,是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club,边学习边翻译的项目。由于能力有限,如发现错误或翻译不妥,请指正,欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️,🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Binary Tree


二叉树是一种,其中每个节点具有0,1或2个子节点。 这是一个二叉树:

一个二叉树

子节点通常称为 子节点 和 子节点。 如果节点没有任何子节点,则称为 叶子节点。 是树顶部的节点(程序员习惯树颠倒了😀)。

节点通常会有一个返回其父节点的连接,但这不是绝对必要的。

二叉树通常用作二叉搜索树。 在这种情况下,节点必须按特定顺序排列(左侧是较小的值,右侧是较大的值)。 但这不是所有二叉树的要求。

例如,这是一个二叉树,表示一系列算术运算,(5 * (a - 10)) + (-4 * (3 / b))

一个二叉树

代码

以下是在Swift中实现通用二叉树的方法:

1
2
3
4
public indirect enum BinaryTree<T> {
case node(BinaryTree<T>, T, BinaryTree<T>)
case empty
}

如何使用它的一个例子,让我们构建上面算术运算树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// leaf nodes
let node5 = BinaryTree.node(.empty, "5", .empty)
let nodeA = BinaryTree.node(.empty, "a", .empty)
let node10 = BinaryTree.node(.empty, "10", .empty)
let node4 = BinaryTree.node(.empty, "4", .empty)
let node3 = BinaryTree.node(.empty, "3", .empty)
let nodeB = BinaryTree.node(.empty, "b", .empty)

// intermediate nodes on the left
let Aminus10 = BinaryTree.node(nodeA, "-", node10)
let timesLeft = BinaryTree.node(node5, "*", Aminus10)

// intermediate nodes on the right
let minus4 = BinaryTree.node(.empty, "-", node4)
let divide3andB = BinaryTree.node(node3, "/", nodeB)
let timesRight = BinaryTree.node(minus4, "*", divide3andB)

// root node
let tree = BinaryTree.node(timesLeft, "+", timesRight)

您需要反向构建树,从叶子节点开始,一直到顶部。

添加description属性以便打印树,这会很有用的:

1
2
3
4
5
6
7
8
9
10
extension BinaryTree: CustomStringConvertible {
public var description: String {
switch self {
case let .node(left, value, right):
return "value: \(value), left = [\(left.description)], right = [\(right.description)]"
case .empty:
return ""
}
}
}

如果你 print(tree) 你应该看到这样的东西:

value: +, left = [value: *, left = [value: 5, left = [], right = []], right = [value: -, left = [value: a, left = [], right = []], right = [value: 10, left = [], right = []]]], right = [value: *, left = [value: -, left = [], right = [value: 4, left = [], right = []]], right = [value: /, left = [value: 3, left = [], right = []], right = [value: b, left = [], right = []]]]

通过一点想象力,您可以看到树形结构。 ;-)如果你缩进它会清晰的看到:

value: +, 
    left = [value: *, 
        left = [value: 5, left = [], right = []], 
        right = [value: -, 
            left = [value: a, left = [], right = []], 
            right = [value: 10, left = [], right = []]]], 
    right = [value: *, 
        left = [value: -, 
            left = [], 
            right = [value: 4, left = [], right = []]], 
        right = [value: /, 
            left = [value: 3, left = [], right = []], 
            right = [value: b, left = [], right = []]]]

另一个有用的属性是计算树中的节点数:

1
2
3
4
5
6
7
8
public var count: Int {
switch self {
case let .node(left, _, right):
return left.count + 1 + right.count
case .empty:
return 0
}
}

对于示例的树,tree.count应该是12。

您经常需要对树进行的操作遍历它们,即以某种顺序查看所有节点。 遍历二叉树有三种方法:

  1. In-order(或深度优先): 首先查看节点的左子节点,然后查看节点本身,最后查看其右子节点。
  2. Pre-order: 首先查看节点,然后查看其左右子节点。
  3. Post-order: 首先查看左右子节点最后处理节点本身。

以下是您实现的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public func traverseInOrder(process: (T) -> Void) {
if case let .node(left, value, right) = self {
left.traverseInOrder(process: process)
process(value)
right.traverseInOrder(process: process)
}
}

public func traversePreOrder(process: (T) -> Void) {
if case let .node(left, value, right) = self {
process(value)
left.traversePreOrder(process: process)
right.traversePreOrder(process: process)
}
}

public func traversePostOrder(process: (T) -> Void) {
if case let .node(left, value, right) = self {
left.traversePostOrder(process: process)
right.traversePostOrder(process: process)
process(value)
}
}

这些函数会被递归调用,在使用树结构时很常见。

例如,如果您按 Post-order 遍历算术运算树,您将按以下顺序查看值:

1
2
3
4
5
6
7
8
9
10
11
12
5
a
10
-
*
4
-
3
b
/
*
+

叶子节点首先出现。 根节点最后出现。

您可以使用堆栈计算机来评估这些表达式,类似于以下伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
tree.traversePostOrder { s in 
switch s {
case this is a numeric literal, such as 5:
push it onto the stack
case this is a variable name, such as a:
look up the value of a and push it onto the stack
case this is an operator, such as *:
pop the two top-most items off the stack, multiply them,
and push the result back onto the stack
}
the result is in the top-most item on the stack
}

作者:Matthijs Hollemans
翻译:Andy Ron
校对:Andy Ron

坚持原创技术分享,您的支持将鼓励我继续创作!