基于NCRE的二叉树及二叉树遍历教学探索

李晓

摘要：二叉树及二叉树的遍历在全国计算机等级考试公共知识部分占很大比重，针对学生没有数据结构的系统知识，学起来困难，做题困难，拿不到分等问题，通过对二叉树遍历问题进行详细阐述，再结合一些考题进行分析，给学生找到一些解题的捷径，树立解决这类问题的信心，帮助学生顺利通过等级考试。

关键词：NCRE；二叉树；二叉树遍历

中图分类号：G64 文献标识码：A 文章编号：1009-3044（2018）08-0106-03

1引言

NCRE：全国计算机等级考试（National Compeer Rank Ex-amination），是由教育部考试中心主办，面向社会考试，考查应试人员计算机应用知识与技能的全国性计算机水平考试。该考试分为四个级别，即一级到四级，一级为初级，四级为最高级。通常，普通高等学校本科学生要求达到二级水平。二级考试要求参考者具有计算机基础知识和基本运用能力，可以从事计算机程序编制，初级计算机教学培训以及企业中与信息化相关的工作。二级考试分为9个不同的类别，但所有类别都需要考生掌握一定的二级公共知识，这些公共知识主要包括计算机基础知识，程序设计、软件工程、数据结构与算法、数据模型等。笔者所在的高校，学生普遍为文科类学生，这一部分公共知识的教学一直都非常困难，学生表示很难理解，考试中学生解题非常困难。其中数据结构中的二叉树及二叉树的遍历更是教学中的难点。

2二叉树即二叉树的遍历

树是一种非线性的数据结构，具有层次关系或分支关系，可以用来描述客观世界的很多结构，在人工智能和算法分析中都有广泛的应用。二叉树是指每个结点最多有两个子结点的结构，这两个结点通常被称为左子树和右子树。二叉树是一种独立的数据结构，不是树的特殊形式。若将二叉树的左右子树颠倒，就成为了另一棵不同的二叉树，即使二叉树中的根结点只有一个子结点，也要说明该结点是左子树还是右子树，这是二叉树与树的最大区别。

在二叉树的应用中，往往要求在二叉树中查找满足指定条件的结点，或者对树中全部结点逐一进行处理，如：输出结点信息等，这就引入了二叉树的遍历问题、或者称为二叉树的周游问题。二叉树的遍历实际上就是把二叉树的所有结点进行线性排列的过程，从而可以按这种线性排列访问到二叉树中的每一个结点，使得每一个结点均被访问一次，且只能被访问一次。遍历对线性结构非常容易解决，但对二叉树这种非线性的结构，需要找到一种规律，使二叉树上的结点能排列在一个线性队列上，从而便于遍历或周游。

根据二叉树的定义，二叉树由根结点和左右两课子树构成，如果用T代表根结点，L代表左子树，R代表右子树，那么二叉树有TLR，LTR，LRT，TRL，RTL，RLT六种不同的遍历方式。但最常用到的都是先左后右的顺序，所以，将TLR（即根左右）表示的遍历称为先根遍历，LTR（即左根右）表示的遍历称为中根遍历，而LRT（即左右根）表示的遍历称为后根遍历。另外，还有一种遍历的方式是一层一层地访问二叉树中的结点，称为层序遍历。但层序遍历一般不能简单地使用L、T、R排列的方式来表示。

（1）先根遍历

规则：先访问根结点，再访问左子树，最后访问右子树。

在二叉树中，如果除了先根遍历的结点序列，还有中根遍历的结点序列，由先根遍历的第一个结点在中根遍历节点序列中的位置，可以将中根遍历的结点序列分为左右两部分，由中根遍历的方式可知，中根遍历序列里根结点前面的结点必然是左子树的结点，根结点后面的结点必然是右子树中的结点。从而该二叉树的根结点及其左右子树中的结点就可以确定下来。将这一过程递归地进行下去，可逐步确定出二叉树的树形结构。同理，如果知道二叉树的中根遍历序列和后根遍历序列，同样可以确定出二叉树的树形结构。

全国计算机等级考试公共基础知识部分，关于二叉树的遍历每年都会有比较经典的考题出现，下面对等级考试中出现的关于二叉树遍历问题的几道考题做一一分析。

3实例讲解

（1）设二叉树如下图，则此二叉树的后根遍历序列为：（）

A、ABDEGCFH B、DBGEAFHC C、DGEBHFCA D、ABCDEFGH

解题方案一：根据后根序列规则，推算出此二叉树的后根序列。

从根结点依次往下，A到B，B为左子树的根结点，仍然不访问，继续再到下一层，到D。D为叶子结点，所以访问D，再到E，E为根結点，不访问，到下一层的左子树G，访问G，因为没有右子树，接着访问E，再到上一层，访问B，则左子树部分的后根序列为DGEB。接着是此树的右子树部分，直接到叶子结点H，访问H，接着访问上一层的F，再访问上一层的C，即右子树部分的后根序列为HFC，最后访问整棵树的根结点A，因此，这棵二叉树的后根序列为DGEBHFCA，答案为C。

解题方案二：此题可以有捷径的解法。根据二叉树后根序列的规则，需要先访问左子树，再访问右子树，最后访问根结点，因此二叉树的后根序列的最后一个字母一定是根结点。分析答案，发现只有C答案是以A字母结尾的，因此，可以很快得到此题答案为C。

（2）设二叉树的前根序列为ABDEGHCFIJ，中根序列为DB-GEHACIFJ，则按层次输出（从上到下，同一层从左到右）的序列为（）。

A、ABCDEFGHIJ B、DGHEBUFCA C、JIHGFEDCBA D、GHIJDEFBCA

解题方案一：根据前根序列和中根序列，还原这棵二叉树。

根据前根序列规则，第一个字母即为这棵二叉树的根结点，则这棵二叉树的根结点为A，因为根结点为A，在中根序列中，A字母以前的字母DBGEH为这棵二叉树的左子树部分，CIFJ为这棵二叉树的右子树。继续分析左子树部分，根据前根序列BDEGH，左子树的根结点为B，根据中根序列DBGEH，B字母左边的D为左子树，GEH为右子树部分。再根据前根EGH，判断E为根结点，依次判断G为左子树，H为右子树。再分析右子树部分，前序CFIJ，C为根节点，下一层，前序FIJ，中序IFJ，即根结点F，左子树I，右子树J。至此，已经还原了这棵二叉树。见图2。

根据还原以后的二叉树，可以得到此题答案为：ABCDEF-GHIJ，则答案为A答案

解题方案二：此题也可不还原二叉树，根据前根序列规则，二叉树的前根序列第一个字母即为二叉树的根结点，则该二叉树的根结点为A，根据层序遍历规则，层序的第一个字母必须是二叉树的根结点，因此，此題可以在答案中选择以A字母开头的序列，分析答案，只有A答案符合这个条件，因此，选择A答案。

（3）设二叉树的前根序列为ABDEGHCFIJ，中根序列为DB-GEHACIH，则该二叉树的后根序列为（）

A、DGHEBIJFCA B、JIHGFEDCBA C、GHIJDEFBCA D、ABCDEFGHIJ

解题方案一：根据前根序列和中根序列，还原这棵二叉树。

根据前根序列开头字母A，证明这棵二叉树的根结点为A，再分析中根序列，A字母以前的DBGEH均为该二叉树的左子树部分，而CIFJ均为zJ.树的右子树部分。再看左子树的前根序列，B字母开头，则证明左子树的根结点为B字母，再看中根序列，B字母的左边只有D字母，证明左子树为D，GEH为右子树部分，根据中根序列为EGH，得出结论，E为根节点，G为左子树，H为右子树。分析右子树部分，前序CFIJ，证明，C为根结点。看中根序列，C的左边没有字母，因此没有左子树，右子树部分，前序为FIJ，则F为根结点，I为左子树，J为右子树，至此，这个二叉树已经确定。见图3。

根据已经还原出来的二叉树和二叉树后根遍历规则，此二叉树的后跟遍历序列为：DGHEBIJFCA，所以A答案为正解。

解题方案二：本题也可不必还原二叉树。从前根序列可以分析出此树的根结点为A，再分析此树中根序列，A字母以前的DBGEH为此树的左子树部分，CIFJ为此树的右子树部分。根据二叉树后根序列的规则：先左子树再右子树最后根结点，那么必须把左子树部分访问完了以后，才会访问右子树。因此右子树部分的CIFJ结点不可能出现在二叉树后根序列的前五个字母，分析答案。B答案开头即为JI，C答案第三第四个字母为U，故这两个答案均为错误答案。再看D答案，此题已经判断出A结点为根结点，那么后根序列的最后一个字母应为A，所以，D答案错误。得出此题的正确答案为A。

（4）某二叉树的前根序列为ABCD，中根序列为DCBA，则后根序列为（）。

A、BADC

B、DCBA

C、CDAB

D、ABCD

解题方案一：此题仍然需要根据前根序列和中根序列还原ZJ.树。根据前根序列规则，得出结论此二叉树的根结点为A，再分析中根序列，发现，此二叉树所有的结点都在左边。再看左子树的前序为BCD，则根结点为B，再依据中根序列，剩下两个结点仍然还是在左边。那么前序下一个根结点为C，再分析中序D还是在C的左边，得出结论，此二叉树是一棵非常特殊的二叉树。见图4。

根据还原出来的二叉树，得到此二叉树的后跟序列为：DC-BA。故答案为B答案。

解题方案二：此题仍然有比较捷径的解法。根据前根序列，得出此二叉树的根结点为A字母，那么根据二叉树后根序列的规则，根结点必然是后根序列里最后一个字母。根据上述推论，在答案里找到以A字母结束的序列就是正确答案。由此得到此题的答案是B。

4结论

根据二叉树的先根遍历结点序列和中根遍历结点序列可确定二叉树的树形结构；同样的，由二叉树的后根遍历结点序列和中根遍历结点序列，也可确定二叉树的树形结构。但是，如果同时知道二叉树的先根遍历和后根遍历，则无法确定二叉树的树形结构。

全国计算机等级考试中关于二叉树遍历的问题，一般都是围绕知道先根，中根，求后根。或者知道中根，后根，求先根这一考点。根据上述四道非常典型的考题分析，同学们可以依靠扎实的理论知识，认真分析已知条件，再求解。同时，我们也发现，多数考题考虑到考生往往并不是计算机专业的学生，对数据结构的知识掌握并不是特别系统和牢固，因此考题中也有一些捷径的解法，即并不用完全还原二叉树，就能得到最终答案，考生掌握这样的分析方法，可以很快求得答案，通过等级考试。