10.Trees¶

tree是一种具有深远意义的数据结构。它被用于软件开发的许多方面，如：

表示层次关系。
管理排序的数据。
促进快速查找操作。

有许多类型的树，它们有不同的形状和大小。在本章中，你将学习使用和实现树的基本知识。

术语¶

许多术语都与树有关，这里有一些你应该一开始就知道的术语。

节点¶

与链表一样，树是由nodes组成的。

每个节点可以携带一些数据，并保持对其子类的跟踪。

父和子¶

树从顶部开始，向底部分支，就像真正的树一样，只是倒着看。

每个节点（除了最上面的一个）都正好连接到它上面的一个节点。该节点被称为parent节点。直接在它下面并与之相连的节点被称为它的child节点。在一棵树中，每个孩子都有一个确切的父节点。这就是树的特点，嗯，是树。

`Root`¶

树中最顶端的节点被称为树的root。它是唯一没有父节点的节点：

`leaf`¶

如果一个节点没有孩子，它就是一个leaf：

以后你会遇到更多的术语，但这应该足以让你开始。

实施¶

打开本章的入门Playground，开始学习。一棵树由节点组成，所以你的第一个任务是创建一个TreeNode类。

创建一个名为TreeNode.swift的新文件，并在其中写入以下内容：

public class TreeNode<T> {
  public var value: T
  public var children: [TreeNode] = []

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

每个节点负责一个value，并使用一个数组持有对其所有子节点的引用。

! note 使用一个类类型来表示TreeNode将意味着失去价值语义。另一方面，它使得创建对节点的引用变得很简单，这一点你将在后面使用。

接下来，在TreeNode类中添加以下方法：

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

这个方法在一个节点上添加一个子节点。

是时候给它一个惊喜了。回到Playground页面，写下以下内容：

example(of: "creating a tree") {
  let beverages = TreeNode("Beverages")

  let hot = TreeNode("Hot")
  let cold = TreeNode("Cold")

  beverages.add(hot)
  beverages.add(cold)
}

层次结构是树状结构的自然候选者，所以，在这里，你已经定义了三个不同的节点，并将它们组织成一个逻辑层次结构。这种安排对应于以下结构：

遍历算法¶

遍历线性集合，如数组或链表，是很直接的。线性集合有一个明确的起点和终点：

迭代树的过程就比较复杂了：

左边的节点应该有优先权吗？一个节点的深度与它的优先权应该有什么关系？你的遍历策略取决于你所要解决的问题。对于不同的树和不同的问题，有多种策略。在下一节中，你将看到depth-first traversal，这是一种从根部开始，在回溯之前尽可能地访问节点的技术。

深度优先的遍历法(`depth-first traversal`)¶

在TreeNode.swift的底部写上以下内容：

extension TreeNode {
  public func forEachDepthFirst(visit: (TreeNode) -> Void) {
    visit(self)
    children.forEach {
      $0.forEachDepthFirst(visit: visit)
    }
  }
}

这个简单的代码使用递归来处理下一个节点。

如果你不希望你的实现是递归的，你可以使用你自己的栈。

是时候测试一下了。回到Playground页面，写下以下内容：

func makeBeverageTree() -> TreeNode<String> {
  let tree = TreeNode("Beverages")

  let hot = TreeNode("hot")
  let cold = TreeNode("cold")

  let tea = TreeNode("tea")
  let coffee = TreeNode("coffee")
  let chocolate = TreeNode("cocoa")

  let blackTea = TreeNode("black")
  let greenTea = TreeNode("green")
  let chaiTea = TreeNode("chai")

  let soda = TreeNode("soda")
  let milk = TreeNode("milk")

  let gingerAle = TreeNode("ginger ale")
  let bitterLemon = TreeNode("bitter lemon")

  tree.add(hot)
  tree.add(cold)

  hot.add(tea)
  hot.add(coffee)
  hot.add(chocolate)

  cold.add(soda)
  cold.add(milk)

  tea.add(blackTea)
  tea.add(greenTea)
  tea.add(chaiTea)

  soda.add(gingerAle)
  soda.add(bitterLemon)

  return tree
}

这个函数创建了以下的树：

接下来，添加这个：

example(of: "depth-first traversal") {
  let tree = makeBeverageTree()
  tree.forEachDepthFirst { print($0.value) }
}

这段代码产生了以下深度优先的输出：

---Example of: depth-first traversal---
Beverages
hot
tea
black
green
chai
coffee
cocoa
cold
soda
ginger ale
bitter lemon
milk

在下一节中，你将看到level-order traversal，这是一种根据节点的深度来访问树的每个节点的技术。

级序遍历(`level-order traversal`)¶

在TreeNode.swift的底部写上以下内容：

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) }
    }
  }
}

forEachLevelOrder按等级顺序访问每个节点：

注意你是如何使用队列（而不是堆栈）来确保你以正确的级别顺序访问节点。简单的递归（隐含地使用了堆栈）是不会成功的

回到Playground页面，写下以下内容：

example(of: "level-order traversal") {
  let tree = makeBeverageTree()
  tree.forEachLevelOrder { print($0.value) }
}

在控制台，你将看到以下输出：

---Example of: level-order traversal---
Beverages
hot
cold
tea
coffee
cocoa
soda
milk
black
green
chai
ginger ale
bitter lemon

搜索¶

你已经有了一个遍历所有节点的方法，所以建立一个搜索算法应该不会花很长时间。在TreeNode.swift的底部写上以下内容：

extension TreeNode where T: Equatable {
  public func search(_ value: T) -> TreeNode? {
    var result: TreeNode?
    forEachLevelOrder { node in
      if node.value == value {
        result = node
      }
    }
    return result
  }
}

回到Playground页面，测试你的代码。为了节省一些时间，复制前面的例子，并修改它以测试search方法：

example(of: "searching for a node") {
  // tree from the last example

  if let searchResult1 = tree.search("ginger ale") {
    print("Found node: \(searchResult1.value)")
  }
  if let searchResult2 = tree.search("WKD Blue") {
    print(searchResult2.value)
  } else {
    print("Couldn't find WKD Blue")
  }
}

你将看到以下控制台输出：

---Example of: searching for a node---
Found node: ginger ale
Couldn't find WKD Blue

在这里，你使用了你的级序遍历算法。由于这段代码访问了所有的节点，如果有多个匹配，最后的匹配将获胜。这种不稳定性意味着你将得到不同的对象，这取决于你使用何种遍历算法。

关键点¶

树与链接列表有相似之处，但一个树节点可以链接到许多子节点，而链接列表的节点只能链接到一个后继节点。
除了根节点之外，每个树节点都有一个父节点。
根结点没有父结点。
叶子结点没有子结点。
熟悉树的术语，如parent、child、leaf和root。这些术语中有许多是程序员同行的常用语，将有助于解释其他树形结构。
遍历，如depth-first和level-order遍历，并不是针对一般的树。它们在其他类型的树上工作，尽管它们的实现会根据树的结构方式而略有不同。

10.Trees¶

术语¶

节点¶

父和子¶

Root¶

leaf¶

实施¶