第三课《二叉树进阶王国》—— 完全二叉树 二叉排序树的神奇魔法故事开始国王的两大神树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 2i1父节点parent i / 2 向下取整2举例假设节点3左孩子i*2 3×2 6右孩子i*21 3×21 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右孩子52节点3左孩子64、太方便了这就是堆Heap的基础后面会学到。第五章二叉排序树 BST1、汉克老师带同学们来到智慧查找森林这里有一棵会“自动排序”的神树。2、什么是 BSTBSTBinary 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、开始查找61第一步当前82比较6 8所以往左走3到36 3往右走4找到65只查了3次6这就是二分思想第七章BST 插入1、现在插入71第一步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(rootNULL) return false; if(root-valx) return true; if(xroot-val) return find(root-left,x); else return find(root-right,x); }3、详细解释1找到空节点说明没找到。2当前节点等于x找到了3x更小去左边。4x更大去右边。4、是不是特别像猜数字游戏第十章课堂训练训练1判断完全二叉树哪个是A) 1 / \ 2 3 / \ 4 5B) 1 / \ 2 3 / \ 4 5答案A正确 B错误训练2BST查找路线8 / \ 3 10 / \ \ 1 6 14找14路线是什么答案8 → 10 → 14训练3中序遍历结果1 3 6 8 10 14第十一章举一反三后面哪里会用到 BST字典查单词游戏排行榜数据库查找搜索系统后面哪里会用到完全二叉树优先队列堆排序任务调度第十二章本课总结同学们今天学会了什么1、完全二叉树特点✅ 前面全满✅ 最后一层从左连续2、数组存树规律left 2iright 2i13、BST规则左边小 右边大4、BST查找像猜数字游戏5、BST中序遍历结果一定升序⚔️课后任务任务1判断下面是不是完全二叉树。1 / \ 2 3 / \ 4 5讲讲为什么任务28 / \ 3 10 / \ \ 1 6 14写出寻找 1 的BST查找路径。任务3自己设计一棵BST让其他同学来做中序遍历。下节课预告下一课⚔️《哈夫曼密码森林》⚔️我们将学习 哈夫曼树 贪心思想 文件压缩 神奇编码魔法