二叉树的性质与遍历
一、二叉树的基本性质
1. 定义
二叉树是每个节点最多有两个子树的树结构，子树分为左子树和右子树，具有顺序性
2. 关键性质
- 性质1：在非空二叉树中，第 \(i\) 层最多有 \(2^{i-1}个\)节点
- 性质2：深度为k的二叉树最多有 \(2^k - 1\) 个节点
- 性质3：对任何一棵非空二叉树，若叶子节点数为 \(n_0\)，度为 2 的节点数为 \(n₂\)，则 \(n_0 = n_2 + 1\)
- 性质4：具有 n 个节点的完全二叉树深度为\(\lfloor \log_2 n\rfloor + 1\)
- 性质5：完全二叉树中节点编号规律（根节点编号为1）：
- 若节点 i 有左孩子，则左孩子编号为 \(2i\)
- 若节点 i 有右孩子，则右孩子编号为 \(2i+1\)
- 若节点 i 有父节点，则父节点编号为 \(\lfloor \frac{i}{2} \rfloor\)
二、二叉树的遍历方式
1. 深度优先遍历（DFS）
- 前序遍历（根 - 左 - 右）
- 中序遍历（左 - 根 - 右）
- 后序遍历（左 - 右 - 根）
2. 广度优先遍历（BFS）- 层次遍历
遍历顺序：按层次依次访问各节点，同一层次从左到右
bfs(s) {q = new queue()q.push(s), visited[s] = truewhile (!q.empty()) {u = q.pop()for each edge(u, v) {if (!visited[v]) {q.push(v)visited[v] = true}}}
}