6.2.树的例子

优质

小牛编辑

129浏览

2023-12-01

现在我们已经研究了线性数据结构，如栈和队列，并且有一些递归的经验，我们将看一个称为树的常见数据结构。树在计算机科学的许多领域中使用，包括操作系统，图形，数据库系统和计算机网络。树数据结构与他们的植物表亲有许多共同之处。树数据结构具有根，分支和叶。自然界中的树和计算机科学中的树之间的区别在于树数据结构的根在顶部，其叶在底部。

在我们开始研究树形数据结构之前，让我们来看几个常见的例子。我们树的第一个例子是生物学的分类树。Figure 1 展示了一些动物的生物分类的实例。从这个简单的例子，我们可以了解树的几个属性。此示例演示的第一个属性是树是分层的。

通过分层，我们的意思是树的层次结构，更接近顶部的是抽象的东西和底部附近是更具体的东西。层次结构的顶部是 Kingdom，树的下一层（上面的层的“Children”）是 Phylum，然后是 Class，等等。然而，无论我们在分类树中有多深，所有的生物仍然是 animals。

Figure 1

注意，你可以从树的顶部开始，并沿着圆圈和箭头一直到底部的路径。在树的每一层，我们可能问自己一个问题，然后遵循与我们的答案一致的路径。例如，我们可能会问，“这个动物是Chordate(脊椎动物)还是Arthropod(节肢动物)？”如果答案是“Chordate”，那么我们遵循这条路径，问“这个Chordate是 Mammal(哺乳动物)吗？”如果不是，我们就卡住了这个简化的例子）。当我们在哺乳动物那层时，我们问“这个哺乳动物是Primate(灵长类动物)还是 Carnivore(食肉动物)？”我们可以遵循以下路径，直到我们到达树的最底部，在那里我们有共同的名字。

树的第二个属性是一个节点的所有子节点独立于另一个节点的子节点。例如，Felis 有属于 Domestica 和 Leo 的孩子。Musca 也有一个名为 Domestica 的孩子，但它是一个不同的节点，并独立于 Felis 的 Domestica孩子。这意味着我们可以改变作为 Musca 的孩子的节点而不影响 Felis 的孩子。

第三个属性是每个叶节点是唯一的。我们可以指定从树的根到唯一地识别动物王国中的每个物种的叶的路径;例如，Animalia→→Chordate→→Mammal→→Carnivora→→Felidae→→Felis→→Domestica。

你可能每天使用的树结构的另一个示例是文件系统。在文件系统中，目录或文件夹被构造为树。Figure 2 说明了 Unix文件系统层次结构的一小部分。

Figure2

文件系统树与生物分类树有很多共同之处。你可以遵循从根目录到任何目录的路径。该路径将唯一标识该子目录（及其中的所有文件）。树的另一个重要属性来源于它们的层次性质，你可以将树的整个部分（称为子树）移动到树中的不同位置，而不影响层次结构的较低级别。例如，我们可以使用整个子树 /etc/，从根节点分离，并重新附加在 usr/ 下。这将把 httpd 的唯一路径名从 /etc/httpd 更改为 /usr/etc/httpd，但不会影响 httpd 目录的内容或任何子级。

树的最后一个例子是网页。以下是使用HTML编写的简单网页的示例。 Figure 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.cs.luther.edu">Luther CS </a><h2>
</body>
</html>

Figure 3

HTML源代码和伴随源的树说明了另一个层次结构。请注意，树的每个级别都对应于HTML标记内的嵌套级别。源中的第一个标记是 <html>，最后一个是</html> 页面中的所有其余标记都是成对的。如果你检查，你会看到这个嵌套属性在树的所有级别都是 true。