一、树与二叉树的基础概念
在数据结构中，树是一种典型的一对多关系的非线性结构，我们可以从节点、前驱后继、度、层、高度、深度这些维度来理解它的构成。
1. 树的核心术语
- 节点：是构成树形结构的基本单元，我们可以根据它的位置和作用进一步划分：
- 根节点：树的起始节点，只有后继节点，没有前驱节点。
- 分支节点：既有前驱也有后继的节点，在树形结构中最多只有一个前驱，但可以有多个后继。
- 叶子节点：位于树的最末端，只有前驱，没有后继的节点。
- 前驱（祖先）：指的是当前节点的'来源'节点，也就是在路径上直接指向它的上一个节点。
- 后继（子孙）：是当前节点的后续节点，也就是由它直接指向的下一级节点。
- 度：代表节点拥有的前驱或后继的数量，又可以细分为：
- 入度：节点拥有的前驱数量，在树形结构中所有节点的入度均为 1。
- 出度：节点拥有的后继数量，不同类型的节点出度不同，比如叶子节点的出度为 0。
- 层：根节点所在的位置为第 1 层，每向下经过一个节点，层数就加 1。
- 高度：一个节点的高度，是指从该节点到距离它最远的叶子节点之间的距离。
- 深度：一个节点的深度，是指从根节点到该节点所经过的节点个数。
- 树的高度 / 深度：整棵树的高度等于树的深度，也等于树的总层数。
二、二叉树的定义与特性
1. 二叉树的定义
二叉树是树形结构的一种特殊形式，它的核心约束是：每个节点最多有 2 个后继节点，这两个后继节点分别被称为左孩子（左侧的子节点）和右孩子（右侧的子节点）。
2. 常见的二叉树类型
- 满二叉树：一种理想的二叉树结构，其所有的叶子节点都在同一层上，并且除了叶子节点之外，每个节点都有左右两个子节点。
- 完全二叉树：将二叉树的所有节点按层序展开并连续编号，若编号顺序与满二叉树的编号完全对应，就是完全二叉树。它的特点是叶子节点只会出现在最后两层，且最后一层的叶子节点都靠左排列。
3. 二叉树的重要特性
- 第 k 层最多节点数：在二叉树的第 k 层上，最多有
2^(k-1)个节点（k ≥ 1）。 - 前 k 层最多节点数：在二叉树的前 k 层中，最多有
2^k - 1个节点（k ≥ 1）。
三、二叉树的遍历方式
遍历是操作二叉树的基础，我们可以按照**深度优先（DFS）和广度优先（BFS）**两大思路来遍历二叉树。
1. 深度优先遍历（DFS）
深度优先遍历的核心是沿着一条路径尽可能深地探索，直到无法继续再回溯，它包含三种常见的顺序：
- 前序遍历：访问顺序为 根 → 左 → 右。
- 中序遍历：访问顺序为 左 → 根 → 右。
- 后序遍历：访问顺序为 左 → 右 → 根。