搜索法讲解二叉树遍历的教学探讨VIP

搜索法讲解二叉树遍历的教学探讨摘要:本文从教学实践的角度出发,阐述了学生对“数据结构”课程教学中二叉树遍历这一知识点不易理解的问题,并提出了一种新的方法——搜索法来解决这一问题。通过对搜索法的分析、解决过程及案例的演示,使学生产生兴趣从而提高该知识点的课堂教学效果。关键字:数据结构二叉树二叉树遍历搜索法数据结构是计算机专业尤其是软件技术专业中极其重要的一门专业基础课。所有数据结构中,树是非常重要的一种,尤其是二叉树,学习者是应该牢固掌握的。在学习了较为简单的线性表之后,学生开始接触了较为复杂的数据结构——树。通过形象的比喻,概念树是容易接受的,但是讲到对树的建立和运算等问题时,很多学生或多或少地会感到一些困惑,尤其是二叉树的遍历,看似简单的递归算法,可要理解其遍历过程,未必能够一目了然。1、 问题的提出对于二叉树遍历过程的讲解,传统的讲法以递归算法为蓝本,加上图示的辅助,帮助学生理解该算法怎样实现在树的遍历中如何调用对子树的遍历,如何输出结点以及如何返回,返回到哪一个结点。由于学生接触的递归算法不多,所以理解不是很好,有时候感觉像是在走迷宫,教起来自然也就不轻松。多次讲解此处知识后我们发现,如果以二叉树的搜索图示为蓝本讲解,使学生反向理解二叉树的遍历算法效果要好很多。这样,不仅使学生容易理解二叉树的遍历过程,而且对递归这一常用的算法设计方法也有更深刻的理解。下面将总结后的经验与大家共勉。2、 问题的分析——搜索法二叉树的遍历是针对任意二叉树,任意二叉树存在结点度为0的结点,也可能存在结点度为的1的结点,还可能存在结点度为2的结点。用搜索法对二叉树进行遍历时,无论二叉树的结点度是为0,为1还是为2,首先将结点度不为2的结点,用空结点将其补充为结点度为2的结点。其次从根结点左侧出发,搜索每一个结点,每个非空结点都将访问三次。第一次访问标为①,第二次访问标为②,第三次访问标为③。如果是先序遍历(先根遍历),则沿着搜索线将标记为①的结点依次输出;如果是中序遍历(中根遍历),则沿着搜索线将标记为②的结点依次输出;如果后序遍历(后根遍历),则沿着搜索线将标记为③的结点依次输出。这样就将原来的根左右、左根右和左右根变为①、②、③的输出(当然标记也可以用其他数字或字母,只要标记统一就可以)。其他标记①、②、③也也正好是前序遍历、中序遍历和后序遍历递归算法中的输出语句所在的位置。3、问题的解决——搜索法根据对搜索法遍历方法的分析,可制定出搜索法遍历二叉树的三个步骤。(1)完善二叉树。纵观整个二叉树,将其结点度不为2的结点,用空结点将其补充为结点度为2的结点。(2)画搜索线。从根结点的左侧出发,沿着二叉树图画出搜索线。第一次到达某非空结点标示为①,第二次到达某非空结点标示为②,第三次到达某非空结点标示为③。最后回到根结点的右侧。(3)写出要求的遍历序列。如果是先序遍历,就沿着搜索线依次将标记为①的结点写出。如果是中序遍历,就沿着搜索线依次将标记为②的结点写出。如果是后序遍历,就沿着依次将标记为③的结点写出。4、综合案例给出二叉树(如图1)的先序遍历序列、中序遍历序列和后序遍历序列图1原始二叉树图2完善后的二叉树(1)完善二叉树,如图2所示:(2)画搜索线,如图3所示:图3带搜索线的二叉树根据搜索线图如图3所示,前序遍历是沿着箭头方向依次写出结点处标示为①的结点,故前序遍历序列为ABDCEF;中序遍历是沿着箭头方向依次写出结点处标示为②的结点,故中序遍历序列为DBAECF;后序遍历是沿着箭头方向依次写出结点处标示为③的结点,故后序遍历序列为DBEFCA。5 结语使用“搜索法”讲解二叉树遍历的优势显而易见的,直观的讲述和演示使学生能够很快掌握二叉树遍历的过程,轻松地写出二叉树的遍历序列。此外,在遇到较为复杂的二叉树需要写出遍历序列时,“搜索法”更显示出它的优点。但“搜索法”也有一个弱点,那就是操作繁琐。由于经验有限,此方法只是在作者讲授的软件技术“数据结构”课程和自考“数据结构”课程中使用,课堂上学生对这种方法表达出的浓厚兴趣。学生的学习效果也是非常好。考试结果显示,通过“搜索法”遍历二叉树的教学,同学们完全掌握了这个知识点,可以说“搜索法”比较地成功的运用于教学中。参考文献:[1]严蔚敏,吴伟民.数据结构(C语言版).北京:清华大学出版社,2007.8.[2]黄刘生数据结构.北京:经济科学出版社,2004.2.[3]谭浩强C语言程序设计(