第三课：《二叉树进阶王国》
—— 完全二叉树 + 二叉排序树的神奇魔法
🌟故事开始：国王的两大神树
1、在“二叉树魔法学院”毕业后，
小勇者们继续前进。
他们来到了一座更神秘的地方：
🏰《二叉树进阶王国》
王国中央，
长着两棵神奇的大树：
2、🌳第一棵：
完全二叉树
它长得：
整整齐齐！
3、🌳第二棵：
二叉排序树
它拥有：
超快查找魔法！
4、汉克老师说：
“学会它们，”
“我们就真正进入高级算法世界了！”
于是，
新的冒险开始了！
第一章：什么是完全二叉树？
1、🌟先回忆普通二叉树
A / \ B C / D这是普通二叉树。
2、🌟再看完全二叉树
1 / \ 2 3 / \ / 4 5 6是不是特别整齐？
3、🌟完全二叉树的规则
（1）规则1
除了最后一层，
前面必须全部满！
（2）规则2
最后一层：
必须从左往右连续排列。
（3）🌟像电影院坐座位！
正确：
😀 😀 😀 😀 😀错误：
😀 ❌ 😀 😀中间不能空！
第二章：判断是不是完全二叉树
1、🌟正确例子
1 / \ 2 3 / \ / 4 5 62、🌟错误例子
1 / \ 2 3 / \ 4 6为什么错？
因为：
5的位置空了， 6却跑后面去了。不连续！
3、🌟课堂小游戏
汉克老师画树。
同学们来判断：
✅ 是完全二叉树
❌ 不是完全二叉树
第三章：为什么完全二叉树这么重要？
1、🌟完全二叉树的秘密：
完全二叉树可以不用“连线”！
直接用数组存！
2、🌟普通树的问题
普通树：
需要记录：
left right比较麻烦。
3、🌟完全二叉树的神奇规律
假设：
节点编号从1开始（1）🌟规律来了！
当前节点：
i左孩子：
left = 2i
右孩子：
right = 2i+1
父节点：
parent = i / 2 （向下取整）
（2）🌟举例！
假设：
节点3左孩子：
i*2 = 3×2 = 6右孩子：
i*2+1 = 3×2+1= 7父节点：
i / 2 = 3/2 =14、🌟是不是特别神奇？
电脑根本不用画树。
只靠位置就知道关系！
第四章：数组存树
1、🌟树
1 / \ 2 3 / \ / 4 5 62、🌟数组
下标: 1 2 3 4 5 6 数值: 1 2 3 4 5 63、🌟观察！
（1）节点2
左孩子：
4右孩子：
5（2）节点3
左孩子：
64、🌟太方便了！
这就是：
🌟堆（Heap）的基础！
后面会学到。
第五章：二叉排序树 BST
1、汉克老师带同学们来到：
🌳智慧查找森林
这里有一棵会“自动排序”的神树。
2、🌟什么是 BST？
BST：
Binary Search Tree
中文：
二叉排序树
3、🌟它有超级规则！
左边都小
右边都大
4、🌟例子
8 / \ 3 10 / \ \ 1 6 145、🌟观察！
左边
1 3 6都比8小。
右边
10 14都比8大。
6、🌟这就是 BST！
第六章：BST 为什么厉害？
1、汉克老师问：
“如果要找数字6怎么办？”
2、🌟普通树
只能一个个找。
很慢。
3、🌟BST
像猜数字游戏！
4、🌟开始查找6
（1）第一步
当前：
8（2）比较
6 < 8
所以：
往左走！
（3）到3
6 > 3
往右走！
（4）找到6！
（5）🌟只查了3次！
（6）🌟这就是：二分思想！
第七章：BST 插入
1、🌟现在插入7
（1）第一步
7 < 8
往左。
（2）第二步
7 > 3
往右。
（3）第三步
7 > 6
继续右。
（4）🌟放进去！
8 / \ 3 10 / \ 1 6 \ 72、🌟规律
一路比较。
一路寻找位置。
第八章：BST 中序遍历的秘密！
1、汉克老师给同学们说：
“BST还藏着一个秘密！”
2、🌟看这棵树
8 / \ 3 10 / \ \ 1 6 143、🌟中序遍历！
口诀：
左 根 右4、🌟结果！
1 3 6 8 10 145、🌟发现了吗？
自动从小到大排序了！
6、🌟超级重要结论
BST 的中序遍历：
一定是升序！
第九章：简单代码启蒙
1、🌟BST节点
struct Node { int val; Node *left; Node *right; };2、🌟查找函数
bool find(Node *root,int x) { if(root==NULL) return false; if(root->val==x) return true; if(x<root->val) return find(root->left,x); else return find(root->right,x); }3、🌟详细解释
（1）找到空节点
说明没找到。
（2）当前节点等于x
找到了！
（3）x更小
去左边。
（4）x更大
去右边。
4、🌟是不是特别像：
猜数字游戏？
第十章：课堂训练
🌟训练1：判断完全二叉树
哪个是？
A) 1 / \ 2 3 / \ 4 5B) 1 / \ 2 3 / \ 4 5答案：
A正确 B错误🌟训练2：BST查找路线
8 / \ 3 10 / \ \ 1 6 14找14：
路线是什么？
🌟答案
8 → 10 → 14🌟训练3：中序遍历
结果：
1 3 6 8 10 14第十一章：举一反三！
🌟后面哪里会用到 BST？
🌳字典查单词
🌳游戏排行榜
🌳数据库查找
🌳搜索系统
🌟后面哪里会用到完全二叉树？
🌳优先队列
🌳堆排序
🌳任务调度
第十二章：本课总结
🌟同学们今天学会了什么？
1、🌳完全二叉树
特点：
✅ 前面全满
✅ 最后一层从左连续
2、🌳数组存树
规律：
left = 2i
right = 2i+1
3、🌳BST
规则：
左边小 右边大4、🌳BST查找
像：
猜数字游戏5、🌳BST中序遍历
结果一定：
升序⚔️课后任务
🌟任务1
判断下面是不是完全二叉树。
1 / \ 2 3 / \ 4 5讲讲为什么？
🌟任务2
8 / \ 3 10 / \ \ 1 6 14写出寻找 1 的BST查找路径。
🌟任务3
自己设计一棵BST，
让其他同学来做中序遍历。
🌟下节课预告
下一课：
⚔️《哈夫曼密码森林》⚔️
我们将学习：
🌟 哈夫曼树
🌟 贪心思想
🌟 文件压缩
🌟 神奇编码魔法！
