树是 "一对多" 的非线性结构，它的结构类似自然界中的树，有一个 “根”，从根延伸出多个 “分支”，最终到达 “叶子”。最常用的是二叉树（每个节点最多 2 个子节点：左孩子、右孩子）。
一、二叉树的定义
二叉树是树的一种特殊形式，它的每个节点最多有两个子节点，分别称为左子节点和右子节点。
二叉树的特性
- 每个节点的度（子节点数量）≤ 2。
- 左子节点和右子节点有明确顺序（即使只有一个子节点，也要区分左右）。
二叉树的基本形态
- 空树：没有任何节点。
- 只有根节点：仅有一个节点，无左右子树。
- 只有左子树：根节点有左子节点，无右子节点。
- 只有右子树：根节点有右子节点，无左子节点。
- 完全二叉树：除最后一层外，每一层都满，最后一层的节点从左到右连续排列（如堆的结构）。
- 满二叉树：每一层的节点都达到最大数量（所有叶子节点在同一层，且非叶子节点都有两个子节点）。
示例（二叉树）：
1 ← 根节点
/ \
2 3
/ / \
4 5 6 ← 叶子节点（4、5、6）二、二叉树的遍历（核心操作）
遍历即按一定顺序访问所有节点，常见有 4 种（时间复杂度均为 O(n)，n 为节点数）：
- 前序遍历：根 → 左 → 右
- 中序遍历：左 → 根 → 右
- 后序遍历：左 → 右 → 根
- 层序遍历：按层次从左到右（需配合队列）
1. 前序遍历（Pre-order）：根 → 左 → 右
void preOrder(Node* root) {
if (root == NULL) return;
printf("%d ", root->data); // 访问根
preOrder(root->left); // 遍历左子树
preOrder(root->right); // 遍历右子树
}示例遍历结果：1 2 4 3 5 6
2. 中序遍历（In-order）：左 → 根 → 右
void inOrder(Node* root) {
if (root == NULL) return;
inOrder(root->left); // 遍历左子树
printf("%d ", root->data); // 访问根
inOrder(root->right); // 遍历右子树
}示例遍历结果：4 2 1 5 3 6
3. 后序遍历（Post-order）：左 → 右 → 根
void postOrder(Node* root) {
if (root == NULL) return;
postOrder(root->left); // 遍历左子树
postOrder(root->right); // 遍历右子树
printf("%d ", root->data); // 访问根
}示例遍历结果：4 2 5 6 3 1
4. 层序遍历（Level-order）：按层次从左到右访问（借助队列实现）
void levelOrder(Node* root) {
if (root == NULL) return;
Queue* q = createQueue(); // 假设已有队列实现
enqueue(q, root);
while (!isEmpty(q)) {
Node* curr = dequeue(q);
printf("%d ", curr->data); // 访问当前节点
if (curr->left != NULL) enqueue(q, curr->left);
if (curr->right != NULL) enqueue(q, curr->right);
}
}示例遍历结果：1 2 3 4 5 6
三、二叉树的应用场景
- 二叉搜索树（BST）：左子树所有节点值 <根节点值 < 右子树所有节点值，支持高效的查找、插入、删除（平均 O (log n)）。
- 平衡二叉树（如 AVL 树、红黑树）：解决 BST 在极端情况下退化为链表的问题，保证操作效率稳定。
- 堆（完全二叉树）：实现优先级队列、堆排序。
- 表达式树：解析和计算数学表达式（如
(3+4)*5可表示为二叉树）。 - 霍夫曼树：用于数据压缩（如霍夫曼编码）。
四、总结
- 树是层级结构的非线性数据结构，用于表示具有 “一对多” 关系的数据。
- 二叉树是每个节点最多有两个子节点的特殊树，因结构简单、操作高效而被广泛应用。
- 二叉树的遍历是处理树结构的基础，不同遍历方式适用于不同场景（如中序遍历可用于 BST 的排序输出）。