第三课《神奇的排序魔法——BST遍历》
🌟故事开始：魔法图书馆的大难题
1、经过前两课。
我们已经学会了：
🌳建立BST！
2、现在。
魔法图书馆已经有很多很多书了：
8 3 10 1 6 143、形成了：
8 / \ 3 10 / \ \ 1 6 144、可是！
新的问题来了！
5、有一天。
国王突然说：
👑“我要所有魔法书按编号排序！”
图书管理员爷爷瞬间崩溃：
😵“这么多书怎么排呀？”
一本一本排序？
太慢了！
6、这时。
算法魔法师微微一笑：
🌟“BST本身就会排序！”
6、全场震惊：
😮“树还能排序？！”
7、今天我们就来学习：
🌟BST最神奇的魔法：
⚔️遍历（Traversal）⚔️
第一部分：什么叫“遍历”？
1、🌟遍历是什么？
可以理解成：
🌟“把整棵树走一遍”
就像：
2、🌳森林探险
你需要：
每个地方都去
每个节点都访问
3、🌟访问是什么意思？
例如：
看到数字：
8就把它输出。
4、🌟今天我们重点学习：
🎯中序遍历（Inorder）
因为：
它是 BST 最神奇的地方！
第二部分：三种DFS遍历方式
1、其实树的遍历本质上就是：
🌟DFS（深度优先搜索）
因为：
我们会：
一路往下走2、🌟树的遍历有三种经典方式
① 前序遍历
顺序：
根 → 左 → 右② 中序遍历
顺序：
左 → 根 → 右③ 后序遍历
顺序：
左 → 右 → 根3、🌟今天重点：
🎯中序遍历
因为：
🌟BST + 中序遍历 = 自动升序！
第三部分：中序遍历到底怎么走？
1、现在看这棵树：
8 / \ 3 10 / \ \ 1 6 142、🌟中序遍历规则
🎯左 → 根 → 右
意思是：
第一步
先去左边。
第二步
再看自己。
第三步
最后去右边。
3、🌟开始真正冒险！
第一步：从8开始
规则：
左 → 根 → 右所以：
先去左边。
来到：
3第二步：来到3
还是：
左 → 根 → 右继续左。
来到：
1第三步：来到1
继续：
左 → 根 → 右左边没人！
于是：
🌟输出1！
结果：
1第四步：返回3
左边已经访问完了。
现在轮到：
🌟输出3！
结果：
1 3第五步：去3的右边
来到：
6左边没人。
输出6。
结果：
1 3 6第六步：返回8
左边全部结束。
输出8。
结果：
1 3 6 8第七步：去8的右边
来到：
10左边没人。
输出10。
结果：
1 3 6 8 10第八步：继续右边
来到：
14输出14。
最终结果：
1 3 6 8 10 144、🌟震撼时刻！
发现没有？
🌟自动变成升序了！
😮“树居然自己排序了！”
这就是：
🌟BST最厉害的地方！
第四部分：为什么会自动升序？
这个特别重要！
1、🌟因为BST满足：
左边更小 右边更大而中序遍历顺序：
左 → 根 → 右2、所以：
先输出小的
再输出中间
最后输出大的
于是天然升序！
3、🌟这是算法中的经典思想！
很多高级算法都来自这里。
第五部分：中序遍历代码
终于开始真正写代码啦！
🌟中序遍历函数
void inorder(Node* root) { // 空节点直接返回 if(root == NULL) { return; } // 先遍历左边 inorder(root->left); // 输出当前节点 cout << root->val << " "; // 再遍历右边 inorder(root->right); }第六部分：一步一步拆解代码
1、🌟第一步
if(root == NULL) { return; }什么意思？
2、表示：
🌟“这条路走没了”
例如：
1 的左边没有节点。
于是返回。
3、🌟第二步
inorder(root->left);表示：
🌟先去左边探险！
4、🌟第三步
cout << root->val << " ";表示：
🌟访问当前节点
也就是：
输出数字。
5、🌟第四步
inorder(root->right);表示：
🌟最后去右边
6、🌟核心口诀
🎯左 → 根 → 右
一定要掌握背熟！
第七部分：完整程序
#include <iostream> using namespace std; struct Node { int val; Node* left; Node* right; Node(int x) { val = x; left = NULL; right = NULL; } }; // 插入节点 Node* insert(Node* root, int x) { if(root == NULL) { return new Node(x); } if(x < root->val) { root->left = insert(root->left, x); } else if(x > root->val) { root->right = insert(root->right, x); } return root; } // 中序遍历 void inorder(Node* root) { if(root == NULL) { return; } inorder(root->left); cout << root->val << " "; inorder(root->right); } int main() { Node* root = NULL; int a[] = {8, 3, 10, 1, 6, 14}; for(int i = 0; i < 6; i++) { root = insert(root, a[i]); } cout << "中序遍历结果：" << endl; inorder(root); return 0; }🌟程序输出
中序遍历结果： 1 3 6 8 10 14第八部分：前序和后序（复习前期知识）
虽然今天重点是中序。
但也让同学们回顾下另外两种。
1、🌟前序遍历
顺序：
根 → 左 → 右结果：
8 3 1 6 10 142、🌟后序遍历
顺序：
左 → 右 → 根结果：
1 6 3 14 10 83、🌟不用死记！
重点是：
🌟理解访问顺序不同。
第九部分：课堂互动小游戏
🌟游戏1：真人遍历
同学们站成BST。
汉克老师说：
🎯“中序遍历开始！”
孩子必须：
左 → 根 → 右移动。
十分有趣！
🌟游戏2：猜输出结果
汉克老师画树。
让同学们猜：
中序遍历结果是什么。
🌟游戏3：谁先输出？
老师问：
“8和3谁先输出？”同学们会慢慢体会递归过程。
第十部分：最重要的思想
今天真正重点不是代码。
而是掌握：
🌟结构决定结果！
1、因为 BST：
左小右大2、所以：
中序遍历才会：
自动升序3、🌟这就是算法思维！
不是乱写。
而是：
🌟利用结构的规律。
第十一部分：本课总结
🌟今天学会了什么？
1、🌳遍历
把整棵树走一遍。
2、🌳中序遍历
口诀：
🎯左 → 根 → 右
3、🌳BST最神奇的地方
🌟中序遍历会自动升序！
4、🌟记住一句话
🌳BST不是只能搜索。
🌳它还能自动排序！
