1. 学习目标

你好，我是悦创。

  • 理解树这种数据结构及其用法。
  • 了解如何用树实现映射。
  • 用列表实现树。
  • 用类和引用实现树。
  • 将树实现为递归数据结构。
  • 用堆实现优先级队列。

2. 示例

我们已经学习了栈和队列等线性数据结构，并对递归有了一定的了解，现在来学习树这种常见的数据结构。树广泛应用于计算机科学的多个领域，从操作系统、图形学、数据库到计算机网络。

作为数据结构的树和现实世界中的树有很多共同之处，二者皆有根、枝、叶。不同之处在于，前者的根在顶部，而叶在底部。

在研究树之前，先来看一些例子。

第一个例子是生物学中的分类树。从生物分类学的角度给出了某些动物的类别，从这个简单的例子中，我们可以了解树的一些属性。

2.1 层次性

第一个属性是层次性，即树是按层级构建的，越笼统就越靠近顶部，越具体则越靠近底部。

在图中，顶层是界，下一层（上一层的“子节点”）是门，然后是纲，依此类推。但不管这棵分类树往下长多深，所有的节点都仍然表示动物。
image.png
可以从树的顶部开始，沿着由椭圆和箭头构成的路径，一直到底部。

在树的每一层，我们都可以提出一个问题，然后根据答案选择路径。

比如，我们可以问：

  • “这个动物是属于脊索动物门还是节肢动物门？”如果答案是“脊索动物门”，就选脊索动物门那条路径；
  • 再问：“是哺乳纲吗？”如果不是，就被卡住了（当然仅限于在这个简单的例子中）。
  • 继续发问：“这个哺乳动物是属于灵长目还是食肉目？”

就这样，我们可以沿着路径直达树的底部，找到常见的动物名。

2.2 无关性

树的第二个属性是，一个节点的所有子节点都与另一个节点的所有子节点无关。

比如，猫属的子节点有家猫（英文名为 Domestica）和狮。家蝇属的子节点是家蝇，其英文名也是Domestica，但此 Domestica 非彼 Domestica。这意味着可以变更家蝇属的这个子节点，而不会影响猫属的子节点。
image.png

2.3 独一无二

第三个属性是，叶子节点都是独一无二的。

在本例中，每一个物种都对应唯一的一条从树根到树叶的路径，比如：动物界→脊索动物门→哺乳纲→食肉目→猫科→猫属→家猫。

另一个常见的树状结构是文件系统。在文件系统中，目录或文件夹呈树状结构。下图展示了 Unix 文件系统的一小部分。
image.png
Windows 其实也有，就是查看不方便：

  1. clela@AIYC D:\Github_pages\QuicksandTeam.github.io\docs
  2. # tree
  3. 文件夹 PATH 列表
  4. 卷序列号为 C0000100 0BF4:1B94
  5. D:.
  6. ├─.vuepress
  7. │  ├─dist
  8. │  │  ├─AboutTeam
  9. │  │  ├─article
  10. │  │  ├─assets
  11. │  │  │  ├─css
  12. │  │  │  ├─fonts
  13. │  │  │  ├─icon
  14. │  │  │  ├─img
  15. │  │  │  └─js
  16. │  │  ├─category
  17. │  │  │  └─Markdown 基础
  18. │  │  ├─ColumnImages
  19. │  │  │  ├─jysfimg
  20. │  │  │  └─MarkdownBase
  21. │  │  │      └─01
  22. │  │  ├─en
  23. │  │  │  └─home
  24. │  │  ├─encrypt
  25. │  │  ├─images
  26. │  │  │  └─公众号
  27. │  │  ├─slide
  28. │  │  ├─star
  29. │  │  ├─tag
  30. │  │  │  └─Markdown
  31. │  │  ├─timeline
  32. │  │  ├─WebSiteData
  33. │  │  └─zh
  34. │  │      ├─column
  35. │  │      │  ├─aiycsf
  36. │  │      │  ├─jysf
  37. │  │      │  └─md
  38. │  │      │      ├─EightMarkdownform
  39. │  │      │      ├─FiveMarkdowncode
  40. │  │      │      ├─fourmarkdownblock
  41. │  │      │      ├─nineMarkdownskills
  42. │  │      │      ├─oneMarkdowntitle
  43. │  │      │      ├─SevenMarkdownpictures
  44. │  │      │      ├─SixMarkdownlink
  45. │  │      │      ├─threeMarkdown_list
  46. │  │      │      └─twoMarkdown_paragraph
  47. │  │      ├─guide
  48. │  │      ├─home
  49. │  │      └─slides
  50. │  ├─public
  51. │  │  ├─assets
  52. │  │  │  └─icon
  53. │  │  ├─ColumnImages
  54. │  │  │  ├─aiycsf
  55. │  │  │  ├─jysfimg
  56. │  │  │  └─MarkdownBase
  57. │  │  │      └─01
  58. │  │  └─images
  59. │  │      └─公众号
  60. │  └─styles
  61. ├─en
  62. └─zh
  63.     ├─column
  64.     │  ├─aiycsf
  65.     │  ├─jysf
  66.     │  └─md
  67.     └─guide

文件系统树与生物分类树有很多共同点。在文件系统树中，可以沿着一条路径从根直达任何目录。这条路径能唯一标识子目录以及其中的所有文件。树的层次性衍生出另一个重要属性，即

image.png
可以将树的某个部分（称作子树）整体移到另一个位置，而不影响下面的层。比如，可以将从
etc/ 起的全部子树挪到 usr/ 下。

这会将到达 httpd/ 的路径从 /etc/httpd/ 变成 /usr/etc/httpd/，但不会影响 httpd 目录下的内容或子节点。

关于树的最后一个例子是网页。以下是一个简单网页的HTML代码。下图展示了该网页用到的 HTML 标签所对应的树。

  1. <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
  2. <head>
  3.     <meta http-equiv="Content-Type"
  4.           content="text/html; charset=utf-8"/>
  5.     <title>simple</title>
  6. </head>
  7. <body>
  8. <h1>A simple web page</h1>
  9. <ul>
  10.     <li>List item one</li>
  11.     <li>List item two</li>
  12. </ul>
  13. <h2><a href="http://www.aiyc.top">CS</a></h2></body>
  14. </html>

image.png
HTML 源代码与对应的树展示了另一种层级关系。树的每一层对应 HTML 标签的每一层嵌套。在源代码中，第一个标签是，最后一个是。其余的标签都在这一对标签之内。检查一遍会发现，树的每一层都具备这种嵌套属性。

3. 术语及定义

在看了一些树的例子之后，现在来正式地定义树及其构成。

3.1 节点

节点是树的基础部分。它可以有自己的名字，我们称作“键”。

节点也可以带有附加信息，我们称作“有效载荷”。有效载荷信息对于很多树算法来说不是重点，但它常常在使用树的应用中很重要。

3.2 边

b41b1267ed9e7a8388ee9327b431813.png
边是树的另一个基础部分。两个节点通过一条边相连，表示它们之间存在关系。除了根节点
以外，其他每个节点都仅有一条入边，出边则可能有多条。

3.3 根节点

image.png
根节点是树中唯一没有入边的节点。在上图中，/ 就是根节点。

3.4 路径

路径：是由边连接的有序节点列表。比如，哺乳纲→食肉目→猫科→猫属→家猫就是一条路径。

3.5 子节点

image.png
一个节点通过出边与子节点相连。在上图中，log/、spool/ 和 yp/ 都是 var/ 的子节点。

3.6 父节点

image.png
一个节点是其所有子节点的父节点。在上图中，var/ 是 log/、spool/ 和 yp/ 的父节点。

3.7 兄弟节点

image.png
具有同一父节点的节点互称为兄弟节点。文件系统树中的 etc/ 和 usr/ 就是兄弟节点。

3.8 子树

一个父节点及其所有后代的节点和边构成一棵子树。

3.9 叶子节点

叶子节点没有子节点。比如，上图中的人和黑猩猩都是叶子节点。

3.10 层数

image.png
节点 n 的层数是从根节点到 n 的唯一路径长度。在上图中，猫属的层数是 5。由定义可知，根节点的层数是 0。

3.11 高度

image.png
树的高度是：其中节点层数的最大值。上图中的树高度为 2。

定义基本术语后，就可以进一步给出树的正式定义。实际上，悦创将提供两种定义：

  • 其中一种涉及节点和边；
  • 另一种涉及递归。你在后面会看到，递归定义很有用。

4. 定义一：树由节点及连接节点的边构成。

树有以下属性：

  • 有一个根节点；
  • 除根节点外，其他每个节点都与其唯一的父节点相连；
  • 从根节点到其他每个节点都有且仅有一条路径；
  • 如果每个节点最多有两个子节点，我们就称这样的树为二叉树。

下图展示了一棵符合定义一的树。边的箭头表示连接方向。
image.png

5. 定义二：一棵树要么为空，要么由一个根节点和零棵或多棵子树构成，子树本身也是一棵树。

每棵子树的根节点通过一条边连到父树的根节点。下图展示了树的递归定义。

从树的递归定义可知，图中的树至少有 4 个节点，因为三角形代表的子树必定有一个根节点。这棵树或许有更多的节点，但必须更深入地查看子树后才能确定。
image.png

6. 实现

根据6.3节给出的定义，可以使用以下函数创建并操作二叉树。

  • BinaryTree()：创建一个二叉树实例。
  • getLeftChild()：返回当前节点的左子节点所对应的二叉树。
  • getRightChild()：返回当前节点的右子节点所对应的二叉树。
  • setRootVal(val)：在当前节点中存储参数 val 中的对象。
  • getRootVal()：返回当前节点存储的对象。
  • insertLeft(val)：新建一棵二叉树，并将其作为当前节点的左子节点。
  • insertRight(val)：新建一棵二叉树，并将其作为当前节点的右子节点。

实现树的关键在于选择一个好的内部存储技巧。Python 提供两种有意思的方式，我们在选择前会仔细了解这两种方式。第一种称作“列表之列表”，第二种称作“节点与引用”。

image.png
注意，可以通过标准的列表切片操作访问子树。

  • 树的根节点是： myTree[0]；
  • 左子树是： myTree[1]；
  • 右子树是： myTree[2]

以下会话展示了如何使用列表创建树。一旦创建完成，就可以访问它的根节点、左子树和右子树。

“列表之列表”表示法有个很好的性质，那就是表示子树的列表结构符合树的定义，这样的结构是递归的！

由一个根节点和两个空列表构成的子树是一个叶子节点。还有一个很好的性质，那就是这种表示法可以推广到有很多子树的情况。如果树不是二叉树，则多一棵子树只是多一个列表。

myTree = ['a',
          ['b', ['d', [], []], ['e', [], []]],
          ['c', ['f', [], []], []]
          ]

print(myTree)

In [4]: myTree = ['a',
   ...:           ['b', ['d', [], []], ['e', [], []]],
   ...:           ['c', ['f', [], []], []]
   ...:           ]

In [5]: myTree
Out[5]: ['a', ['b', ['d', [], []], ['e', [], []]], ['c', ['f', [], []], []]]

In [6]: myTree[0]
Out[6]: 'a'

In [7]: myTree[1]
Out[7]: ['b', ['d', [], []], ['e', [], []]]

In [8]: myTree[2]
Out[8]: ['c', ['f', [], []], []]