第二课《魔法图书管理员——BST插入与构建》故事开始魔法图书馆的新危机1、上节课。我们已经认识了二叉搜索树BST2、知道了左边小 右边大还能快速找书3、可是新的问题来了4、每天。都会有新的魔法书送进图书馆。例如《火焰龙咒语》《隐身术大全》《100种糖果魔法》图书管理员爷爷急坏了“新书到底该放哪里呀”5、因为如果乱放。BST 就会失去魔法力量6、于是今天。我们要学习BST到底是怎么“长出来”的7、也就是BST插入Insert第一部分BST不是画出来的1、有的同学会以为BST是老师画出来的其实不是2、BST是“长出来”的就像种树3、数字一个一个插进去。树就慢慢长出来了。4、今天我们的任务依次插入8 3 10 1 6 14看看 BST 怎么生长第二部分插入第一个数字1、插入8现在树是空的什么都没有。2、于是8 来了。它说“我要住进图书馆”3、因为现在没人。所以8直接成为树根4、结果85、规则第一位来到的数字会成为根节点第三部分插入31、现在树里已经有82、新书3来了。3、开始比较1第一步比较3 和 8因为3 8所以往左边走2左边有没有人没有空的3于是3住进去4结果8 / 34、插入口诀1比当前节点小往左走。2比当前节点大往右走。3找到空位插进去第四部分插入101、现在树8 / 32、新书10来了。3、开始比较10 8所以往右边走4、右边没人。于是10住进去5、结果8 / \ 3 10第五部分插入1开始变有趣了1、现在树8 / \ 3 102、新书1来了。3、第一步1 8往左。来到32、第二步1 3继续往左。3、左边没人于是1住进去4、结果8 / \ 3 10 / 15、发现了吗BST插入其实像“闯关找房间”每次比较小了往左大了往右直到找到空位置。第六部分插入61、现在轮到62、第一步6 8往左。3、第二步来到3。6 3往右。4、右边没人。6住进去5、结果8 / \ 3 10 / \ 1 6第七部分插入141、现在轮到142、第一步14 8往右。3、来到10。14 10继续右。4、没人14住进去5、最终8 / \ 3 10 / \ \ 1 6 14一棵完整BST诞生啦第八部分BST插入参考代码现在开始真正写程序BST插入函数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; }第九部分一步一步拆解代码1、第一步if(root NULL) { return new Node(x); }2、什么意思1表示“找到空房间啦”2于是新建节点。3、第二步if(x root-val)什么意思1例如3 82说明3应该住左边。3于是root-left insert(root-left, x);继续去左边寻找位置。4、第三步else if(x root-val)表示目标更大。去右边。5、核心思想其实只有一句话一路比较大小直到找到空位置第十部分完整构建程序#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 BST中序遍历 endl; inorder(root); return 0; }1、程序输出1 3 6 8 10 142、神奇现象明明插入顺序是8 3 10 1 6 14结果输出1 3 6 8 10 14自动变有序了3、这是BST最神奇的地方“树居然会排序”第十一部分特别重要的知识点1、插入顺序会影响树形2、例如插入1 2 3 4 53、会变成1 \ 2 \ 3 \ 4 \ 54、树长歪了这样搜索会变慢后面课程会详细讲。第十二部分课堂互动小游戏游戏1同学们当节点1、汉克老师依次报8 3 10 1 62、同学们自己决定站左边站右边最后形成真人BST特别有趣游戏2谁的位置错了1、汉克老师故意摆错8 \ 32、同学们来找错误。第十三部分本课总结今天最重要的内容1、BST插入规则小了往左大了往右2、BST是怎么形成的一个数字一个数字长出来3、BST最核心思想通过比较大小寻找位置4、记住一句话BST不是“画出来”的。而是“长出来”的。
