第11章：树进阶
挑战1：按级别顺序打印一棵树
按照级别顺序打印树中的所有数值。同一级别的节点应打印在同一行。例如，考虑下面这棵树。
你的算法应该打印以下内容。
15
1 17 20
1 5 0 2 5 7
提示：考虑使用启动程序的Sources文件夹中为你包含的队列。
挑战2：父母和所有权
考虑一下树节点的原始定义。
public class TreeNode<T> {
public var value: T
public var children: [TreeNode] = []
public init(_ value: T) {
self.value = value
}
}
你如何修改这个定义以包括一个父节点？关于所有权，你应该做哪些考虑？
解决方案
挑战1的解决方案
按等级顺序打印节点的直接方法是利用队列数据结构的等级顺序遍历。棘手的问题是确定何时应该出现换行。解决方案是这样的。
-
你首先初始化一个Queue数据结构，以便于进行级别顺序的遍历。你还创建了nodesLeftInCurrentLevel来跟踪你在打印新行之前需要处理的节点数量。
-
你的级别顺序遍历继续进行，直到你的队列是空的。
-
在第一个while循环中，你首先将nodesLeftInCurrentLevel设置为队列中的当前元素。
-
使用另一个while循环，你从队列中取出第一个nodesLeftInCurrentLevel数量的元素。每一个元素都会被打印出来，而不需要建立一个新的行。你也要排查该节点的所有子节点。
-
这时，你用print()生成新行。在下一次迭代中，nodesLeftInCurrentLevel将被更新为队列的计数，代表上一次迭代中的子节点数量。
这个算法的时间复杂度为O(n)。由于你将队列数据结构初始化为一个中间容器，这个算法也使用了O(n)空间。
挑战2的解决方案
你可以这样给TreeNode添加一个属性父节点。
public class TreeNode<T> {
public weak var parent: TreeNode?
// etc...
}
使用一个可选的类型，因为根节点没有父节点。赋予它弱所有权以避免引用循环。按照惯例，一个节点与它的子节点有强所有权关系，但与它的父节点有弱非所有权关系。继续链接列表的类比，有父节点的节点类似于一个双链接列表。有更多的簿记开销需要担心，但它允许快速向上遍历树。
| 上一章 | 目录 | 下一章 |
|---|