【5-2】二叉树遍历与应用.pptVIP

数据结构中国地质大学信息工程学;第五章 树受豺惜件援狄酞秀肺或;内容提要5.1 树的基本概念5;5.4 二叉树的遍历 遍历二叉;访问操作的示例 例 假设;线性结构与非线性结构遍历的区别;树的遍历方式 深度优先遍历：;深度优先遍历1、一棵二叉树由三;1.前序遍历前序遍历的递归定义;前序遍历的递归算法templa;2.中序遍历中序遍历的递归定义;中序遍历的递归算法templa;3.后序遍历后序遍历的递归定义;后序遍历的递归算法templa;4.层次遍历：广度优先遍历层序;层次遍历的算法思想【思路】在进;层序遍历从二叉树的根节点开始，;ABDEFCHIGABCDEF;层序遍历的算法实现templa;if (p-leftChil;5.二叉树遍历的应用后序遍历的;（1）后序遍历的应用templ;后序遍历的应用（续）templ;1、可以把任意一个算术表达式用;2、对该二叉树分别进行前序、中;例: 表达式 Exp=a*b+;例: 表达式 Exp=a*b+;后缀表达式的特点： 后缀??达;后缀表达式的计算方法：从左自右;例：表达式A/(B+C*D)-;（3）前序遍历的应用templ;利用前序遍历-创建二叉树 思想;创建二叉树示例A B C @ ;templateclass ;CreateBinTree (;6.二叉树的非递归遍历 递归算;（1) 非递归前序遍历二叉树主;算法实现template c;另一种方法：P204程序5.1;（2) 非递归中序遍历二叉树主;算法实现template c;（3) 非递归后序遍历二叉树主;非递归后序遍历示例aLbLaL;算法实现在后序遍历过程中所用栈;算法实现（续）template;while (continue;7.二叉树计数（形态确定）二叉;结论由二叉树的前序序列和中序序;例：已知一棵二叉树的前序序列和;解答：若二叉树的任意两个节点的;前序：A B D H I E ;二叉树计数如果前序序列固定不变;二叉树计数（续1）如果前序遍历;例如: 有 3 个数据 { ;有0个, 1个, 2个, 3个;计算具有n个结点的不同二叉树的;2000年南开大学考研题 ;2000年西电考研题 ;ABCDEFKIJHGABDF;本节小结二叉树的遍历算法深度优;课后作业P2465.6P248