《二叉树魔法学院》—— 二叉树与遍历的魔法秘密1、故事开始1在“图与树王国”的深处有一座神秘学院 二叉树魔法学院2传说学会“二叉树遍历魔法”的同学可能解锁新的魔法技能3汉克老师说“普通树的孩子不受限制。”“而二叉树每个节点最多只有两个孩子。”于是今天同门们的冒险又开始了第一章什么是二叉树 一、普通树1、先看看普通树1 / | \ 2 3 42、节点1有234三个孩子。 二、二叉树1、二叉树规定每个节点最多只能有两个孩子2、而且必须区分左孩子 右孩子3、例子A / \ B C这里B 是左孩子C 是右孩子4、再看复杂一点A / \ B C / \ \ D E F5、观察A有左孩子 B右孩子 CB有左孩子 D右孩子 EC有没有左孩子右孩子 F6、重点二叉树最多两个孩子。不是必须两个第二章为什么二叉树这么重要1、例如表达式计算 / \ 3 5表示3 5是不是很清晰呢2、结论二叉树是算法世界重要的结构之一第三章二叉树的重要概念1、根节点RootA / \ B C / \ \ D E F最上面的节点。A2、叶子节点Leaf没有孩子的节点。例如D E F3、父节点Parent你的上面谁连着你谁是爸爸节点。4、兄弟节点例如B 和 C 父节点都是 A是兄弟节点。5、深度节点在第几层。6、课堂小游戏A / \ B C / \ \ D E F问题1谁是叶子答案D E F问题2谁是C的爸爸节点答案A问题3B和谁是兄弟节点答案C第四章二叉树如何存进电脑1、汉克老师说“电脑看不懂树。”“所以我们要用结构体的方法让电脑记住它”2、方法节点结构struct Node { char val; Node *left; Node *right; };3、详细说明1val存自己的名字。2left记住左孩子。3right记住右孩子。4举例A / \ B CA会记住left - B right - C5像什么像藏宝图每个节点都知道“往左去哪”“往右去哪”第五章二叉树遍历 —— 魔法学院核心1、汉克老师说有了节点“我们还要学会如何遍历才行”2、所谓遍历3、就是把树里的所有节点访问一遍。4、重点中的重点今天同学们要掌握⚔️前序遍历⚔️中序遍历⚔️后序遍历5、记住它们的区别是“什么时候访问自己”第六章前序遍历Preorder1、口诀先自己 再左边 最后右边简称根 → 左 → 右2、例子A / \ B C / \ \ D E F3、开始遍历1第一步先访问A因为先自己。2第二步进入左边B3第三步继续左边D4第四步D没孩子。退回B。去右边E5第五步退回A。去右边C6第六步去F。7最终顺序A B D E C F4、前序遍历代码void preorder(Node *root) { if(root NULL) return; cout root-val ; preorder(root-left); preorder(root-right); }5、详细解释1第一行if(root NULL)如果没节点了就结束。2第二行cout root-val;先打印自己3第三行去左边。4第四行去右边。6、口诀记忆先看自己 再看左边 最后右边。第七章中序遍历Inorder1、口诀先左边 再自己 最后右边简称左 → 根 → 右2、还是这棵树A / \ B C / \ \ D E F3、遍历过程1先一路向左到D2D没左边打印D3回到B打印B4去E打印E5回到A打印A6去右边C最后F。7最终顺序D B E A C F4、中序遍历代码void inorder(Node *root) { if(root NULL) return; inorder(root-left); cout root-val ; inorder(root-right); }5、发现了吗只是打印位置变了第八章后序遍历Postorder1、口诀先左边 再右边 最后自己简称左 → 右 → 根2、过程一路往下。孩子都处理完。最后才处理自己。3、最终顺序D E B F C A4、后序代码void postorder(Node *root) { if(root NULL) return; postorder(root-left); postorder(root-right); cout root-val ; }5、口诀孩子先做完 自己最后出场。第九章递归的作用1、小猴子探险A ├──B │ ├──D │ └──E └──C2、小猴子规则1到一个房间先干自己的事。2再进入左房间3再进入右房间4没路了自动退回来。第十章课堂训练训练1写遍历顺序A / \ B C / \ D E前序答案A B D E C中序答案D B E A C后序答案D E B C A训练2谁是叶子答案D E C训练3画遍历路线同学们✅ 用箭头画✅ 手指走树✅ 模拟回退掌握了画遍历路线的方法效果会特别好。第十一章举一反三哪里会用到二叉树1、搜索系统2、AI决策树3、表达式计算* / \ 5 / \ 2 3表示(23)*5等等第十二章本课总结同学们今天学会了什么1、二叉树每个节点最多两个孩子2、三种遍历1前序根 左 右2中序左 根 右3后序左 右 根3、递归方法⚔️课后任务任务1画一棵符合定义的“二叉树”。任务2写出下面树的前序中序后序1 / \ 2 3 / \ 4 5下节课预告下一课⚔️《二叉树进阶王国》⚔️我们将学习 完全二叉树 数组存树 二叉排序树 BST 神奇的查找魔法