课程进度 33% · 第4/10章第4/10章 · 标签 1/4
— 1 —
树与二叉树的基本概念与存储结构
树是重要的非线性结构，二叉树是每个节点最多有两个子节点的树。常用术语有根、叶子、深度、高度、度等。二叉树常用链式存储：
cpp
1
// 二叉树节点定义
2
struct TreeNode {
3
int val;
4
TreeNode *left, *right;
5
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
6
};
顺序存储常用于完全二叉树（如堆），用数组下标表示父子关系。
cpp
1
// 顺序存储（完全二叉树/堆）
2
vector<int> tree; // tree[0]为根，左子2*i+1，右子2*i+2
— 2 —
遍历算法（递归与非递归）
常见遍历：先序（根左右）、中序（左根右）、后序（左右根）、层序（BFS）。
cpp
1
// 递归遍历
2
void preorder(TreeNode* root) {
3
if (!root) return;
4
cout << root->val << ' ';
5
preorder(root->left);
6
preorder(root->right);
7
}
8
void inorder(TreeNode* root) {
9
if (!root) return;
10
inorder(root->left);
11
cout << root->val << ' ';
12
inorder(root->right);
13
}
14
void postorder(TreeNode* root) {
15
if (!root) return;
16
postorder(root->left);
17
postorder(root->right);
18
cout << root->val << ' ';
19
}
二叉树链式存储顺序存储递归遍历