🌳
树与二叉树的基本概念
树就是一张家谱图：最上面是老祖宗，往下"生孩子"，一层生一层
💡 打个比方
把一家人画成一张家谱图：最顶上坐着老祖宗（他只有一个位置），往下每代人生孩子，孩子再往下生……
这张图就倒过来放——祖宗朝上、后代朝下——计算机里就叫树（Tree）。
如果规定每个人最多生 2 个孩子，得到的就是二叉树——六级考试里出场率最高的数据结构！
树：由"节点"和"边"组成的、像家谱一样的结构。最顶上的节点叫根，没有孩子的节点叫叶子。二叉树：每个节点最多只有 2 个孩子的树。
🖼️ 大图看明白
🧩 子任务 1：树词汇表
🎯 小目标：看到任何一棵树，都能叫出"根、叶子、高度、深度、路径"的名字
对着上面的大图，把这张"词汇卡"记牢：
· 节点：图中的每个方框（A、B、C…都是节点）。
· 边：连接节点的线。A 和 B 之间有一条边。
· 根：最顶上的 A。整棵树只有 1 个根。
· 叶子：没有孩子的节点——E、F、G 都是叶子。
· 树高：树一共有几层 = 3。树高和层数是同一个数。
· 深度：从根出发，走到某个节点要经过几层。A 深度 1，B/C/D 深度 2，E/F/G 深度 3。
· 路径：从根到某个节点走过的那串边。A→D→G 长度是 2（数边，不数节点）。
易混点：树高 = 层数；节点深度 = 它所在层数；路径长度 = 边数 = 深度 − 1。G 的深度是 3，A 到 G 的路径长度是 2。
✅ 小检查：图中 B 的"父亲"是谁？D 有几个孩子？
看看答案
B 的父亲是 A（A 的孩子有 B、C、D 三个）。D 只有 1 个孩子：G。
🧩 子任务 2：满二叉树 vs 完全二叉树
🎯 小目标：分清三种"整齐程度"不同的二叉树（单选题最爱考）
二叉树的规矩：每个节点最多 2 个孩子，孩子分左、右——只有左孩子、没有右孩子，也算数！
在这个规矩下，树可以有多"整齐"？三个等级：
· 满二叉树：每层都填得满满当当，一个空位都没有。
· 完全二叉树：从上到下、从左到右按号入座，不能留"空位"（最后一层可以不满，但必须靠左排）。
· 普通二叉树：想怎么长就怎么长，只遵守"最多 2 个孩子"。
记忆口诀：n 层满二叉树的节点数 = 1+2+4+…+2ⁿ⁻¹ = 2ⁿ − 1（n 是层数）；完全二叉树"排队不插队"，只有它才能用数组按号存储（第 03 课见）。
✅ 小检查：3 层的满二叉树有几个节点？4 个节点能摆成完全二叉树吗？
看看答案
3 层满二叉树：1+2+4 = 7 个（= 2³−1）。4 个节点可以：根 + 第二层 2 个 + 第三层最左边 1 个，按号入座没有空位。
🧩 子任务 3：用 C++ 造一棵树
🎯 小目标：会写"节点结构体"，会用指针把 3 个节点连成一棵小树
树在电脑里不是"画"出来的，而是用指针"连"出来的——每个节点手里拿着两个"地址"，一个指左孩子，一个指右孩子。没有孩子就放 nullptr（"空地址"）。
// 节点 = 自己的值 + 两只"手"（指向孩子）
struct Node {
int val; // 自己的值
Node* left; // 左手：左孩子的地址
Node* right; // 右手：右孩子的地址
};
连树就像牵手的顺序：先给每个人"出生"（new），再让他们"牵手"（把地址存进 left/right）。下面这棵小树：
1
/ \
2 3
为什么用指针（&地址）：节点的大小是"自己决定的"，不一定挨着排，所以不能用数组下标，只能用地址互相找到。这和 GESP5 链表课是同一个道理。
✅ 小检查：这棵 3 节点的小树里，2 和 3 的 left、right 应该是什么？
看看答案
都是 nullptr——它们没有孩子，两只手都空着。忘记置空是新手最容易犯的错（野指针会指到"别人家"）。
💻 完整 C++ 代码：建一棵小树
#include <iostream>
using namespace std;
struct Node {
int val;
Node* left;
Node* right;
};
int main() {
// 1) 三个节点"出生"
Node* root = new Node();
Node* l = new Node();
Node* r = new Node();
// 2) 写上各自的值
root->val = 1;
l->val = 2;
r->val = 3;
// 3) 牵手：root 的左手牵 l，右手牵 r
root->left = l;
root->right = r;
// 4) l、r 没有孩子，两只手都置空
l->left = l->right = nullptr;
r->left = r->right = nullptr;
// 5) 验证：从 root 出发，顺着地址找到孩子
cout << root->val << " "
<< root->left->val << " "
<< root->right->val << endl;
// 输出：1 2 3
return 0;
}
运行结果：1 2 3 —— 从 root 出发，left 找到 2，right 找到 3。以后遍历、查找、排序，全靠这套"顺着地址走"。
✋ 你来试试
第 1 题：4 层的满二叉树，一共有多少个节点？
1+2+4+8 = 15 个（= 2⁴ − 1）。
第 2 题：一棵树只有根和一个"右孩子"（没有左孩子），它是完全二叉树吗？
不是。按号入座的话，左孩子的位置（2 号位）空着，右孩子却站在 3 号位——中间留了空位，所以不是完全二叉树。
第 3 题：一棵完全二叉树一共有 10 个节点，第 4 层有几个节点？
前 3 层是满的：1+2+4 = 7 个。10 − 7 = 3，所以第 4 层有 3 个节点（靠左排着）。
🎯 一句话记住：树就是倒放的家谱——根在最上、叶子在最下；二叉树每个节点最多 2 个孩子；满 = 全满（2ⁿ−1 个），完全 = 按号入座（能塞进数组）。