第三课《神奇的排序魔法——BST遍历》故事开始魔法图书馆的大难题1、经过前两课。我们已经学会了建立BST2、现在。魔法图书馆已经有很多很多书了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不是只能搜索。它还能自动排序
