数学与计算科学学院
实 验 报 告
实验项目名称 二叉树的遍历 所属课程名称 数据结构 实 验 类 型 验证型 实 验 日 期
班 级 学 号
姓 名
成 绩
1
2
附录1：源 程 序
3
4
5
附录2：实验报告填写说明
1．实验项目名称：要求与实验教学大纲一致。 6
2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。
3．实验原理：简要说明本实验项目所涉及的理论知识。
4．实验环境：实验用的软、硬件环境。
5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。 对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。对于创新性实验，还应注明其创新点、特色。
6．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。
7．实验结论（结果）：根据实验过程中得到的结果，做出结论。
8．实验小结：本次实验心得体会、思考和建议。
9．指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。
7
第二篇：二叉树遍历技巧
二叉树先根序、后根序、中根序遍历的速算法（解题技巧） 经过研究我找出了一种不用画图，由先（后）根序遍历和中根序遍历迅速确定遍历结果的办法。谨以此文献给智商与我同级而又不得不研究算法的朋友。
抽象思维太差，用例子来说明吧。下面这个是后根遍历的算法。
例1：已知某二叉树的先根序遍历为ABCDEFG,中根序遍历为CDBAFEG，则它的后根序遍历为_________
解法如下：
1、确定树根。由先序遍历知道，树根为A。
2、分离左、右子树。由中根序遍历知，A左面的为CDB左子树结点，右面的FEG为右子树结点。 把先根序遍历也分成左、右子树结点，BCD、EFG。
前根序遍历 BCD EFG
中根序遍历 CDB FEG
3、分别把先根序遍历左、右子树结点抄过来，写的时候要从右往左写，本例中，依次写下
B、C、D、，E、F、G，结果是DCB GFE。
当然不是简单到这种程序。上面只是个原理。抄的过程应该是这样的：盯着前根序的，瞅着中根序的。如果要抄的先根序中的结点在中根序中是最左/右边，则直接抄过来；如果不是，则把这个结点左边的结点先放记在右根序的最左边，然后继续抄。本题的结果是DCB,FGE,A, 即DCBFGEA。
上面这个例子太短，看不出“猫腻”来。再举个结点多一点儿的。
例2：已知某二叉树的先根序遍历为ABCDEFGHIJK,中根序遍历为CEDFBAHKJIG，则它的后根序遍历为_________
按上面的方法：
前根序遍历 BCDEF GHIJK
中根序遍历 CEDFB HKJIG
依次抄得前根序的结点：F、E(E在中根序遍历中不靠边，所以先放在后根遍序历中左子树结点最左边)、D、C
同理，把右子树也抄过来。因此，写下结点的过程依次是：
如果还是不太懂，你可以试着做一下下面的例子：
已知二叉树前序遍历 ABCDEFGHIJK，中序遍历 CEDFBAHGKJI，求后序遍历。 解：(1)以根结点A分左、右子树结点，
BCDEF GHIJK
CEDFB HGKJI
(2) 写左子树，盯着前序，从右到左开始写
DCB （在中序中，B靠右边，C靠左边，D不靠边。写一个，从中序中抹一个。）
因为D在中序遍历中不靠边，所以下一个结点E先搁到最左边（注意，是“搁”，也就是说，
不能把E从中序抹去。
E DCB
因为B已经抹了，F靠右边。于是F仍然按照从右到左的规则，写在D的的左边。 E FDCB
最后把E加上，左子树OK。
右子树仍然从右到写
G
因为G不靠边，所以下一个结点H先搁在最左边
H G
然后继续
H KJIG
于是，结果是
EFDCBHKJIGA
前根序遍历类似。
以上的方法只适用于三层以内的二叉树（含三层）。在选择题中，三层以上二叉树也可用以上方法初步判断正确答案。