程序员学数据结构

第9章　树：非线性数据结构

树结构（tree structure）本质上是由节点构成的数据集，该数据集通常不允许对同一个节点进行多次引用，并且也规定这些引用不能指向根节点。这种数据结构模拟了一种树状的层次结构。根据每个节点中所含的值的不同，树可分为有序树和无序树。此外，根据树的用途，节点既可用来存储值类型的数据，也可用来存储对象的实例。

尽管树结构在应用中可能会受到某些限制，但它依然在编程中极其有用。在某些情况下，你甚至不会注意到树结构的存在，这是因为很多数据结构都是以它为基础构建而成的。本章，我们将对树结构进行深入讨论，并在随后的章节中对树结构的扩展结构进行研究。

本章将涵盖以下主要内容：

• 树结构的定义；
• 树结构与树类型；
• 树的相关术语；
• 树的基本操作；
• 树的创建；
• 递归；
• 遍历。

9.1　树结构与树类型

实际中不仅存在树结构，还存在树类型（tree data type），这两者有本质上的区别。因此在进行下一步的学习之前，有必要区分清楚树结构和树类型。

对于初学者而言，数据类型只是数据的一种组织形式，并不包含数据集实现方式的定义。另一方面，数据结构关注的是如何处理特定类型的数据，以及如何对该类型的数据进行具体实现。

因此，树类型必须存在一个值，并且其中的每个子树都也为树类型。而树结构由一组节点构成，这些节点按照树类型的模式相互连接起来。

以下示意图展示了两种不同的树结构。

• 有序树。有序树如图9-1所示。

图9-1

• 无序树。无序树如图9-2所示。

图9-2

其中，每个节点都是一棵树，并且其潜在的子节点也均为树。本章，我们将集中讨论树结构的具体实现。 ...