二叉树性质

在二叉树中，度为 2 的节点数等于叶子节点数减 1。

树节点计数原理

对于一棵度为 k 的树，设度数为 i 的节点数为 w_i，则总节点数 n = Σ (w_i × i) + 1。理由：除根节点外，每个节点都是某个节点的子节点，因此总子节点数加 1 即为总节点数。

示例 1：一棵度为 3 的树，有 3 个度数为 1 的节点、2 个度数为 2 的节点、3 个度数为 3 的节点，求叶子数。

先计算总节点数：n = 3×1 + 2×2 + 3×3 + 1 = 17。
叶子节点数 = 总节点数 - 非叶子节点数 = 17 - (3 + 2 + 3) = 9。

示例 2：一棵有 2024 个节点的二叉树，度为 1 的节点数多于叶子数。度为 2 的节点最多有多少个？

设度为 2 的节点数为 a，则叶子数为 a+1。根据条件 "度为 1 的节点数 > 叶子数"，得：
2024 - a - (a+1) > a+1，化简得 a < 674，所以 a 的最大值为 673。

遍历顺序

• 前序：根、左、右
• 中序：左、根、右
• 后序：左、右、根

给定前序和中序（或前序和后序）可唯一确定二叉树；仅给前序和后序则无法确定。

数学相关内容

换底公式：log_bN = log_aN / log_ab。例如，log₂N = lgN / lg2（lg 以 10 为底），常用于计算上界。

等比数列求和：2⁰ + 2¹ + ... + 2^n-1 = 2ⁿ - 1。证明：令 S = 该数列，则 2S = 2¹ + ... + 2ⁿ，2S - S = 2ⁿ - 1。

应用：高度为 n 的满二叉树有 2ⁿ - 1 个节点。

进制转换

n 进制转十进制：按权展开。示例：十进制数 1234 = 1×10³ + 2×10² + 3×10¹ + 4×10⁰。

十进制转 n 进制：整数部分除以 n 取余，逆序排列；小数部分乘以 n 取整，顺序排列。

二进制转十六进制：从右向左，每 4 位二进制对应一个十六进制数（10→A, 11→B, ...）。

排序稳定性对照

稳定排序：冒泡排序、插入排序、归并排序、计数排序、基数排序。

不稳定排序：选择排序、快速排序、堆排序、希尔排序。

CPU 与内存

访问速度：寄存器 > 高速缓存（Cache）> 内存 > 外存。

WAN：广域网；LAN：局域网。

BIOS（基本输入输出系统）存储于 ROM，不可修改。

操作系统管理硬件与软件资源。中断指硬件或软件信号暂停当前程序，以响应事件。

计算机内部数据和指令以二进制传输，但不一定是机器码。

Intel 发明了最早的 CPU。

进制前缀

• 0x：十六进制
• 0：八进制
• 0b：二进制

例如：1 + 01 中，1 为十进制，01 为八进制（1），结果 = 2。
0x10 + 01 = 十六进制的 16 + 八进制的 1 = 17。

存储单位

最小信息单位：Bit；1 Byte = 8 Bits。

RAM（易失性存储器）断电丢失数据；ROM（只读存储器）永久保留数据。

位运算技巧

交换 unsigned x 的高 16 位和低 16 位：(x << 16) | (x >> 16)。
x << 16 得到高 16 位，x >> 16 得到低 16 位。

BMP 图片大小计算

24 位和 32 位 BMP 不含调色板。文件大小（不含文件头）= 宽度 × 高度 × 位数 / 8。

示例：2560×1440 的 32 位 BMP 大小 = 2560×1440×32÷8 = 14,745,600 Bytes ≈ 14.1 MiB。

Linux 基本命令

• mkdir：创建目录
• touch：创建文件或更新时间戳
• ls：列出目录内容
• mv：移动或重命名文件/目录
• cat：连接文件并输出
• vi：编辑文件；more：分页显示；ls：显示文件和目录

GDB 调试命令

• next 或 n：不进入函数单步执行
• step 或 s：进入函数单步执行
• breakpoint 或 b：设置断点
• continue 或 c：继续执行

real 表示实际运行时间（含 I/O 等待），user + sys 表示 CPU 执行时间，两者通常不相等。

链表

双向链表：每个节点包含前驱和后继指针。
单向链表：仅后继指针。
循环链表：尾节点的后继指向头节点。

链表特点：无需预分配空间，插入/删除 O(1)，不支持随机访问，遍历 O(n)。

插入操作示例：在双向链表节点 p 前插入节点 q：

q->rlink = p;
q->llink = p->llink;
p->llink->rlink = q;
p->llink = q;

图论存储方式

邻接表：

vector<int> edges[N];
edges[u].push_back(v);
edges[v].push_back(u);

邻接矩阵：

int mat[N][N];
mat[u][v] = w;
mat[v][u] = w;

Kruskal 边列表存储（非邻接表/矩阵）：

struct Edge { int u, v, w; };
vector<Edge> edges;

哈夫曼树

哈夫曼编码保证无歧义且总长度最小。构造方法：将频率放入最小堆，每次取出最小两个节点合并，新节点权值为两者之和，重复至只剩一个根节点。

特性：哈夫曼树中不存在度为 1 的节点。

例题：1000 个字母文件中，字母 e 的哈夫曼编码长度为 1，e 至少出现几次？
编码长度为 1 说明 e 是最后合并的，且其权值不小于其他两棵子树权值和。设 e 出现 x 次，则另外两棵子树权值和 ≤ x，总权值 1000 ≤ 3x，得 x ≥ 334。选 B。

图论基础

完全无向图边数：n(n-1)/2。有向完全图边数：n(n-1)。

环：至少包含一个顶点（自环），或两个及以上。

有向图所有顶点入度和出度之和等于边数的两倍。因为每条边贡献一个出度和一个入度。

强连通图：任意两点互相可达。

函数传参

void func(int *a[]);     // 指针数组
void func(int **a);      // 指针的指针，等价于上方
void func(int a[][3]);   // 合法，需指定列数
void func(int a[][]);    // 非法

字符串拼接示例：

char s[100];
char *t = s;
while (scanf("%s", t) != EOF)
    t += strlen(t);