下载后可任意编辑1．熟练掌握各种遍历策略的递归和非递归算法
熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法
教学重点: 掌握二叉树的遍历, 包括中根遍历、 前根遍历和后根遍历方法
教学难点: 理解什么是线索, 中序线索化二叉树的结构特性及寻找某结点的前驱和后继的方法
授课内容4
3 遍历二叉树遍历二叉树是指以某种顺序访问二叉树中的每个结点, 而且每个结点仅被访问一次
这里”访问”的含义很广, 能够是查询结点数据域的内容、 输出结点的数据、 修改结点的数据或是执行对结点的其它操作
假设遍历时访问结点仅是输出结点数据域的值, 那么遍历的结果将是得到一个线性序列
由于二叉树有左、 右子树, 因此遍历的次序不同, 得到的结果就会不同
假设 L、 T、 R 分别代表遍历左子树、 访问根结点和遍历右子树, 则对一棵二叉树的遍历能够有六种不同次序: TLR、 LTR、 LRT、 TRL、 RTL、 RTL
若约定先左( L)后右( R) , 再把访问根结点( T) 穿插其中, 则只有三种不同的遍历次序: TLR、 LTR 和 LRT
它们分别称作先根遍历、 中根遍历和后根遍历
在介绍常见的三种遍历算法之前, 先介绍一下遍历的具体方第十三讲 二叉树下载后可任意编辑法
例如有一棵二叉树, 它有四个结点
为了便于理解遍历的思想, 临时为每个没有子树的结点均补充上相应的空子树, 用 ø 表示, 见图 4-3-1
设想有一条搜索路线( 用虚线表示) , 它从根结点的左支开始, 自上而下自左至右搜索, 最后由根结点右支向上出去
不难看出, 若考虑到空子树的话, 恰好搜索线途径每个有效结点都是三次
把第一次经过就访问的结点列出, 它们是 A、 B、 D、 C, 这就是先根遍历的结果
那么第二此经过才访问的则是中根遍历, 其结果是 B、 D、 A、 C
