之所以把这种数据结构称为「树」是因为这种数据结构看起来就像是一棵倒挂的树，也就是说数据结构中的「树」是根朝上，而叶朝下的。如下图所示。

「树」具有以下的特点：

如下图所示，红色节点 $A$ 是根节点，除了根节点之外，还有 $3$ 棵互不相交的子树 $T_1(B, E, H, I, G)$、$T_2(C)$、$T_3(D, F, G, K)$。

**「树的节点」** 由一个数据元素和若干个指向其子树的树的分支组成。而节点所含有的子树个数称为 **「节点的度」**。度为 $0$ 的节点称为 **「叶子节点」** 或者 **「终端节点」**，度不为 $0$ 的节点称为 **「分支节点」** 或者 **「非终端节点」**。树中各节点的最大度数称为 **「树的度」**。

- **树的节点**：由一个数据元素和若干个指向其子树的树的分支组成。

- **节点的度**：一个节点所含有的子树个数。

一个节点的子树的根节点称为该节点的 **「孩子节点」**，相应的，该节点称为孩子的 **「父亲节点」**。同一个父亲节点的孩子节点之间互称为 **「兄弟节点」**。

- **孩子节点（子节点）**：一个节点含有的子树的根节点称为该节点的子节点。例如图中 $B$ 是 $A$ 的孩子节点。

- **父亲节点（父节点）**：如果一个节点含有子节点，则这个节点称为其子节点的父节点。例如图中 $B$ 是 $E$ 的父亲节点。

**「节点的层次」** 是从根节点开始定义，将根节点作为第 1 层，根的孩子节点作为第 2 层，以此类推，如果某个节点在第 $i$ 层，则其孩子节点在第 $i + 1$ 层。而父亲节点在同一层的节点互为 **「堂兄弟节点」**。树中所有节点最大的层数称为 **「树的深度」** 或 **「树的高度」**。树中，两个节点之间所经过节点序列称为 **「路径」**，两个节点之间路径上经过的边数称为 **「路径长度」**。

- **节点的层次**：从根节点开始定义，根为第 $1$ 层，根的子节点为第 $2$ 层，以此类推。

- **树的深度（高度）**：所有节点中最大的层数。例如图中树的深度为 $4$。

下图就是一棵二叉树。

二叉树也可以使用递归方式来定义，即二叉树满足以下两个要求之一：

二叉树在逻辑上可以分为 $5$ 种基本形态，如下图所示。

我们可以来看几个例子。

我们可以来看几个例子。

如图所示，这 $3$ 棵树都是二叉搜索树。

如图所示，前 $2$ 棵树是平衡二叉搜索树，最后一棵树不是平衡二叉搜索树，因为这棵树的左右子树的高度差的绝对值超过了 $1$。

下图为二叉树的顺序存储结构。

从图中我们也可以看出节点之间的逻辑关系。

二叉树采用链式存储结构时，每个链节点包含一个用于数据域 $val$，存储节点信息；还包含两个指针域 $left$ 和 $right$，分别指向左右两个孩子节点，当左孩子或者右孩子不存在时，相应指针域值为空。二叉链节点结构如下图所示。

二叉链节点结构的对应代码为：

下面我们将值为 $[1, 2, 3, 4, 5, 6, 7]$ 的二叉树使用链式存储结构进行存储，即为下图所示。

二叉树的链表存储结构具有灵活、方便的特点。节点的最大数目只受系统最大可存储空间的限制。一般情况下，二叉树的链表存储结构比顺序存储结构更省空间（用于存储指针域的空间开销只是二叉树中节点数的线性函数），而且对于二叉树实施相关操作也很方便，因此，一般我们使用链式存储结构来存储二叉树。

如下图所示，该二叉树的前序遍历顺序为：$A - B - D - H - I - E - C - F - J - G - K$。

如下图所示，该二叉树的中序遍历顺序为：$H - D - I - B - E - A - F - J - C - K - G$。

如下图所示，该二叉树的后序遍历顺序为：$H - I - D - E - B - J - F - K - G - C - A$。

如下图所示，该二叉树的后序遍历顺序为：$A - B - C - D - E - F - G - H - I - J - K$。

二叉树的层序遍历是通过队列来实现的。具体步骤如下：

如图所示，这 $3$ 棵树都是二叉搜索树。

二叉树具有一个特性，即：**左子树的节点值 < 根节点值 < 右子树的节点值**。