什么是树？

简介

在本课中，我们将学习一种称为树的层次化数据结构。树由节点（顶点）组成，节点之间通过指针（边）相互连接。树与图类似，关键的区别在于：树中不能存在环。

树的基本结构包含以下组成部分：

• 节点：用于存储数据
• 根节点（Root）：树的最顶层节点
• 父节点（Parent Node）：连接到下层一个或多个节点（即子节点）的节点
• 子节点（Child Node）：与上层某个节点（即父节点）相连的节点
• 兄弟节点（Sibling Node）：具有相同父节点的节点
• 叶节点（Leaf Node）：没有子节点的节点

下图展示了上述所有术语的含义：

说明：

在上图中，节点 1 是根节点，同时也是节点 2、3 和 4 的父节点。节点 3 是其子节点 6 和 7 的父节点。由于节点 2、3、4 拥有同一个父节点 1，因此它们互为兄弟节点。同理，节点 6 和 7 因为父节点都是 3，所以也是兄弟节点。

树中的常用术语

以下是树结构中其他一些常见术语：

• 子树（Sub-tree）：
  子树是指树的一部分，可以看作是一棵完整的独立树。树中的任意一个节点及其所有下层相连的节点共同构成原树的一个子树。可将子树类比于“真子集”的概念。

• 度（Degree）：
  一个节点的度指的是该节点拥有的子树的总数。

• 深度（Depth）：
  从根节点到某一节点的连接数（边数）称为该节点的深度。

• 层级（Level）：
  $(节点的深度) + 1$

• 节点的高度（Height of a Node）：
  从该节点到其路径下的叶节点之间的最大连接数（边数），称为该节点的高度。

• 树的高度（Height of a Tree）：
  树的高度等于其根节点的高度。

上图所示的树中共有六个子树，每个子树都标有编号。每个非叶节点都有两个子树，分别称为左子树和右子树。对于叶节点而言，其左子树和右子树均为 null。

---

本课我们学习了树的结构及其相关术语。