二叉树遍历稿ppt课件.pptVIP

二叉树的遍历 1 知识与技能 理解遍历算法 掌握遍历规则 体会遍历算法的应用 过程与方法 通过遍历规则讲解和自主总结遍历思想及算法的教学过程 掌握学习分析总结问题的方法 实现价值 体会复杂数据结构在计算机中的存储方式及组织结构 学会解决如何合理的用计算机程序处理复杂数据 教学目标 2 教学重点掌握二叉树的遍历方法 理解二叉树的遍历算法 教学难点二叉树遍历的应用 重点难点 3 教学过程 引导讲授分析总结 4 问题引入 3 2 5 9 6 7 先算哪个呢 5 借助二叉树 将算术表达式画成一棵二叉树 它的中序遍历序列为 3 2 5 9 6 它的后序遍历序列为 25 3 96 中缀表达式 人的思维 后缀表达式 电脑的思维 6 遍历定义 遍历用途 遍历方法 指按某条搜索路线遍访每个结点且不重复 又称周游 它是树结构插入 删除 修改 查找和排序运算的前提 是二叉树一切运算的基础和核心 对每个结点的查看通常都是 先左后右 7 基础知识 遍历规则 二叉树由根 左子树 右子树构成 定义为D L R 以根结点为参照系 注 先 中 后 的意思是指访问的结点D是先于子树出现还是后于子树出现 D L R的组合定义了六种可能的遍历方案 LDR LRD DLR DRL RDL RLD若限定先左后右 则有三种实现方案 DLRLDRLRD先序遍历中序遍历后序遍历 8 基础知识 先序遍历 DLR 先序遍历序列 ABDC 先序遍历 DLR 特点 任意一个结点均处在其子女结点的前面 根结点在前 有什么特点 9 分析思想总结算法 DLR 访问根结点 先序遍历根的左子树 先序遍历根的右子树 递归过程 先序遍历算法DLR node root if root NULL printf d root data DLR root lchild DLR root rchild return 0 10 基础知识 中序遍历 LDR 中序遍历序列 BDAC 特点 根结点左右分别为左右子树的所有结点 中序遍历 LDR 讨论中序遍历思想及算法 11 基础知识 后序遍历 后序遍历 LRD 讨论后序遍历思想及算法 LRD 后序遍历序列 DBCA 12 三种遍历算法总结 中序遍历算法LDR node root if root NULL LDR root lchild printf d root data LDR root rchild return 0 后序遍历算法LRD node root if root NULL LRD root lchild LRD root rchild printf d root data return 0 结点数据类型自定义typedefstructnode intdata structnode lchild rchild node node root 先序遍历算法DLR node root if root NULL 非空二叉树 printf d root data 访问DDLR root lchild 递归遍历左子树DLR root rchild 递归遍历右子树 return 0 13 三种遍历算法分析 1 从前面的三种遍历算法可以知道 如果将print语句抹去 从递归的角度看 这三种算法是完全相同的 或者说这三种遍历算法的访问路径是相同的 只是访问结点的时机不同 从虚线的出发点到终点的路径上 每个结点经过3次 第1次经过时访问 是先序遍历第2次经过时访问 是中序遍历第3次经过时访问 是后序遍历 2 二叉树遍历的时间效率和空间效率时间效率 O n 每个结点只访问一次空间效率 O n 栈占用的最大辅助空间 精确值 树深为k的递归遍历需要k 1个辅助单元 14 实践内容 练习讨论 例1 先序遍历的结果是 中序遍历的结果是 后序遍历的结果是 DBEACDEBCA 口诀 DLR 先序遍历 即先根再左再右 A B D E C LDR 中序遍历 即先左再根再右 LRD 后序遍历 即先左再右再根 15 实践内容 练习讨论 例2 先序序列 中序序列 后序序列 ABCDEFGHK BDCAEHGKF DCBHKGFEA 16 知识应用 表达式计算 先序遍历结果 ABCDE 前缀表示法中序遍历结果A B C D E 中缀表示法后序遍历结果AB C D E 后缀表示法层次遍历结果 E D CAB 例3 用二叉树表示算术表达式 17 特别讨论 若已知先序 或后序 遍历结果和中序遍历结果 能否 恢复 出二叉树 例 已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA 请画出这棵二叉树 分析 由后序遍历特征 根结点必在后序序列尾部 即A 由中序遍历特征 根结点必在其中间 而且其左部必全部是左子树的子孙 即BDCE 其右部必全部是右子树的子孙 即FHG 继而 根据后序中的DECB子树可确定B为A的左孩子 根据HGF子串可确定F为A的右孩子 以此类推 18 特别讨论 利用后序和中序遍历序列构造一棵二叉树 已知中序遍历 BDCEAFHG已知后序遍历 DECBHGFA BDCE FHG A DCE A B B A C C DCE 如果是先序序列和中序序列呢 19 知识拓展 利用遍历建立二叉树 用空格字符表示 无孩子 或指针为空 如何把二叉树存入电脑内 怎样利用遍历建立一棵二叉树 例 将下面的二叉树以二叉链表形式存入计算机内 考虑1 输入结点时怎样表示 无孩子 考虑2 以何种遍历方式来输入和建树 将二叉树按先序遍历次序输入 ABC DE G F n 以先序遍历最为合适 让每个结点都能及时被连接到位 字符串输完后应当再加一特殊的结束符号 如 因为 无法惟一表示结束 20 知识拓展 利用遍历建立二叉树 建树算法 StatusCreateBiTree BiTree CreateBiTree 输入序列 ABC DE G F 21 课程总结 二叉树的遍历 定义 用途 方法 中序遍历 左 根 右 先序遍历 根 左 右 后序遍历 左 右 根 利用先序遍历建立二叉树 表达式的计算顺序 如何利用遍历构造一棵二叉树 22 课后拓展 上机练习 把二叉树的遍历算法改写成程序进行上机调试 小组讨论完成 小牛试刀 写出利用先序遍历创建一棵二叉树的完整算法 个人独立完成 23 课后作业 1 如右图所示 写出该二叉树的前序遍历 中序遍历和后序遍历的