第10章：树

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

• 表示层次关系。

• 管理排序的数据。

• 促进快速查找操作。

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

术语

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

节点

像链接列表一样，树是由节点组成的。

每个节点都可以携带一些数据，并跟踪其子女。

父节点和子节点

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

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

根节点

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

叶子节点

如果一个节点没有孩子，它就是一个叶子。

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

实现

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

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

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

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

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

注意：使用一个类的类型来表示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)
}

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

遍历算法

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

遍历树就比较复杂了。

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

深度优先的遍历法

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

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

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

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

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

接下来，添加这个。

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

在下一节中，你将会看到水平顺序遍历，这是一种根据节点的深度来访问树的每个节点的技术。

层序遍历

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

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的底部写上以下内容。

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

你会看到下面的控制台输出。

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

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

关键点

• 树与链接列表有相似之处，但一个树节点可以链接到许多子节点，而链接列表的节点只能链接到一个后继节点。

• 除根节点外，每个树节点都有一个确切的父节点。

• 根结点没有父结点。

• 叶子结点没有子结点。

• 熟悉树的术语，如父、子、叶和根。这些术语中有许多是程序员同行的常用语，将有助于解释其他树形结构。

• 遍历，如深度优先和水平顺序遍历，并不是针对一般树的。它们在其他种类的树上工作，尽管它们的实现会根据树的结构方式而略有不同。

---

上一章	目录	下一章