第一课《会自己整理的魔法树》故事开始乱糟糟的魔法图书馆1、很久很久以前。在算法王国里有一座超级大的魔法图书馆2、里面有魔法咒语书龙族秘籍隐身术宝典火球术大全3、每本书都有一个编号8 3 10 1 6 144、可是有一天……图书管理员爷爷快崩溃了因为书全乱了5、比如8 14 1 3 10 6如果想找编号 10 的书怎么办6、爷爷只能一本一本翻……7、问题来了如果只有 6 本书。还好。但如果有100万本书呢那得找到什么时候8、于是算法王国最聪明的大魔法师说“我们需要一种会自己整理的树”9、今天。我们就来学习二叉搜索树BST第一部分什么叫二叉搜索树1、先复习二叉树我们之前学过每个节点最多有一个左孩子一个右孩子比如8 / \ 3 10这就是二叉树。2、但普通二叉树是“乱放”的例如8 / \ 10 3也能叫二叉树。但是找东西会很麻烦3、BST最重要的规则二叉搜索树有一个超级重要的魔法规则规则左边比自己小右边比自己大4、例如8 / \ 3 10因为3 8 10 8所以它符合 BST 规则。5、再看8 / \ 3 10 / \ \ 1 6 14检查一下1节点8左边3 1 6都比8小。右边10 14都比8大。正确2节点3左边1比3小。右边6比3大。正确3所以BST 不是随便长的树。它是“有规律”的树第二部分BST为什么搜索快1、现在。魔法师爷爷说“我要找编号10的书”2、普通方法笨方法如果书乱放8 14 1 3 10 6你只能一个一个找过程8 ❌ 14 ❌ 1 ❌ 3 ❌ 10 ✅找了5次3、BST的聪明方法1现在看 BST8 / \ 3 10 / \ \ 1 6 14找10。2第一步看8。10 8说明目标一定在右边3因为左边全比8小。不可能有10。4于是直接去右边5第二步来到10。找到啦4、发现没有我们直接排除了一大片这就是 BST 最厉害的地方5、像不像猜数字游戏1例如你猜1~1002别人说“大了”你是不是就能3排除一半BST 就是这个思想第三部分BST搜索过程1、搜索口诀记住如果目标更小往左走。如果目标更大往右走。如果相等找到啦2、例子1找6看树8 / \ 3 10 / \ 1 6第一步6 和 8 比。6 8往左。第二步6 和 3 比。6 3往右。第三步找到6搜索路线8 → 3 → 63、例子2找1414 8往右。14 10继续右。找到14搜索路线8 → 10 → 14第四部分为什么BST这么厉害1、因为它会不断缩小范围2、例如找14。当你来到8。你立刻知道左边全部不用找这就节省了大量时间3、普通查找 vs BST查找1普通查找像在垃圾堆找玩具乱翻。2BST查找像图书馆按编号找书特别快第五部分用C实现BST搜索现在开始真正写代码啦1、先定义节点struct Node { int val; Node* left; Node* right; };2、开始搜索函数bool search(Node* root, int target) { // 没找到 if(root NULL) return false; // 找到 if(root-val target) return true; // 去左边 if(target root-val) return search(root-left, target); // 去右边 else return search(root-right, target); }3、代码详解1root NULL说明路走没了。书库里没有这本书。2target root-val找到啦3target root-val目标更小。去左边。4target root-val目标更大。去右边。5这就是BST搜索是不是比全部遍历聪明很多第六部分课堂小游戏游戏1你来当BST老师报数字8 3 10 1 6孩子站成树形。然后老师说“找6”孩子必须8 → 3 → 6一路跳过去特别有趣游戏2猜数字同学们会理解“缩小范围”这个核心思想。第七部分本课总结今天学了什么1、BST规则左小右大2、搜索方法小了往左大了往右3、BST为什么快因为能不断排除大量范围4、记住一句最重要的话BST不是乱找。而是“聪明地缩小范围”。5、课后挑战请孩子自己画出5 2 8 1 3 7 9形成的 BST。然后尝试找7找1找9看看搜索路线是什么。下节课预告下节课。我们会学习⚔️《魔法图书管理员——BST插入与构建》⚔️孩子将真正学会BST到底是怎么“长出来”的