示例
我们已经学习了栈和队列等线性数据结构，并对递归有了一定的了解，现在来学习树这种常见的数据结构。树广泛应用于计算机科学的多个领域，从操作系统、图形学、数据库到计算机网络。作为数据结构的树和现实世界中的树有很多共同之处，二者皆有根、枝、叶。不同之处在于，前者的根在顶部，而叶在底部。
在研究树之前，先来看一些例子。第一个例子是生物学中的分类树。图 6-1 从生物分类学的角度给出了某些动物的类别，从这个简单的例子中，我们可以了解树的一些属性。第一个属性是层次性，即树是按层级构建的，越笼统就越靠近顶部，越具体则越靠近底部。在图 6-1 中，顶层是界，下一层（上一层的 “子节点”）是门，然后是纲，依此类推。但不管这棵分类树往下长多深，所有的节点都仍然表示动物。
可以从树的顶部开始，沿着由椭圆和箭头构成的路径，一直到底部。在树的每一层，我们都可以提出一个问题，然后根据答案选择路径。比如，我们可以问：“这个动物是属于脊索动物门还是节肢动物门？” 如果答案是 “脊索动物门”，就选脊索动物门那条路径；再问：“是哺乳纲吗？” 如果不是，就被卡住了（当然仅限于在这个简单的例子中）。继续发问：“这个哺乳动物是属于灵长目还是食肉目？” 就这样，我们可以沿着路径直达树的底部，找到常见的动物名。
树的第二个属性是，一个节点的所有子节点都与另一个节点的所有子节点无关。比如，猫属的子节点有家猫（英文名为 Domestica）和狮。家蝇属的子节点是家蝇，其英文名也是 Domestica，但此 Domestica 非彼 Domestica。这意味着可以变更家蝇属的这个子节点，而不会影响猫属的子节点。
第三个属性是，叶子节点都是独一无二的。在本例中，每一个物种都对应唯一的一条从树根到树叶的路径，比如动物界→脊索动物门→哺乳纲→食肉目→猫科→猫属→家猫。
另一个常见的树状结构是文件系统。在文件系统中，目录或文件夹呈树状结构。图 6-2 展示了 Unix 文件系统的一小部分。
文件系统树与生物分类树有很多共同点。在文件系统树中，可以沿着一条路径从根直达任何目录。这条路径能唯一标识子目录以及其中的所有文件。树的层次性衍生出另一个重要属性，即可以将树的某个部分（称作子树）整体移到另一个位置，而不影响下面的层。比如，可以将从 etc/ 起的全部子树挪到 usr/ 下。这会将到达 httpd/ 的路径从 /etc/httpd/ 变成 /usr/etc/httpd/，但不会影响 httpd 目录下的内容或子节点。
关于树的最后一个例子是网页。以下是一个简单网页的 HTML 代码。图 6-3 展示了该网页用到的 HTML 标签所对应的树。
<html xmlns="http://www.w3.org/1999/xhtml"
xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type"
content="text/html; charset=utf-8" />
<title>simple</title>
</head>
<body>
<h1>A simple web page</h1>
<ul>
<li>List item one</li>
<li>List item two</li>
</ul>
<h2><a href="http://www.ituring.com.cn">CS</a></h2>
</body>
</html>HTML 源代码与对应的树展示了另一种层级关系。树的每一层对应 HTML 标签的每一层嵌套。在源代码中，第一个标签是 <html>，最后一个是 </html>。其余的标签都在这一对标签之内。检查一遍会发现，树的每一层都具备这种嵌套属性。