数据结构课程设计报告
从根结点到指定结点的路径
——二叉树遍历法
1
摘要：................................................................................................................................................3
引言：................................................................................................................................................4
一．需求分析：................................................................................................................................4
二．概要设计：................................................................................................................................5
2.1 主要模块：..........................................................................................................................5
2.2 流程图：..............................................................................................................................6
2.2.1 先序遍历：...............................................................................................................6
2.2.2 中序遍历...................................................................................................................7
2.2.3 后序遍历：...............................................................................................................9
三．详细设计：..............................................................................................................................11
3.1 建立二叉树。.....................................................................................................................11
3.2 先序遍历............................................................................................................................11
3.3 中序遍历............................................................................................................................12
3.4 后序遍历............................................................................................................................12
3.5 查找指定的路径................................................................................................................12
四．课程设计..................................................................................................................................13
4.1 先序遍历............................................................................................................................13
中序遍历..................................................................................................................................15
后序遍历..................................................................................................................................16
五．测试结果..................................................................................................................................18
先序遍历..................................................................................................................................18
中序遍历..................................................................................................................................20
后序遍历..................................................................................................................................20
六 设计体会.....................................................................................................................................21
七 结束语.........................................................................................................................................22
八 参考文献.....................................................................................................................................22
2
摘要：
随着社会科技的发展，人类的生活水平的提高。然而，在发展的同时
我们也不能避免选择，在十字路口，我们可能会有多种选项，由这些不
同的路口，我们都能达到相同的目的地。而这二叉树则强调最多只有二
个选项。在不同的路叉选择中，我们要达到相同的目的地。比如：由江
西理工大学到赣州市中心的火车站，我们可以有不同的路径。但是由这
些不同的路，我们都能达到所要抵达的目的地，只是路径不同而已！
3
引言：
在二叉树的遍历中，首先要学会建立二叉树，考虑到二叉树的储存
以及不同遍历方式。对根结点到指定结点的路径在不同的遍历方式下有
不同的结果。对结点的类型以及左右子树的建立有着相应的方式。以现
实路构造一个模型，详细的构造方式与查找方式如下所示。
一．需求分析：
1.1 建立一个二叉树，二叉树的实例就是赣州市中心的道路，三叉口处指定二个方
向，由此建立一个二叉树。根结点指定为江西理工大学，而指定的结点为火车站。
1.2 二叉树中的每个结点都编上号，分别为①,②,③,④,⑤,⑥,⑦,⑧.
二叉树的例图如下所示：
①
② ③
④ ⑤ ⑥
⑦
⑧
1.3 遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列，得到二杈树中
结点的先序序列或中序序列或后序序列。这实际上是对一个非线性结构进行线性化
4
操作，使每个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接
前驱和直接后继。但是，当以二叉链表作为存储结构时，只能找到结点的左，右孩
子的信息，而不能直接得到结点在任一序列中的前驱和后继信息，这种信息只能在
遍历的动态过程中才能得到。
因为在有n个结点的二杈链表中必定存在n+1个空链域，故可以利用这些空链域
来存放结点的前驱和后继信息。
试做如下规定：若结点有左子树，则其lchild域指示其左孩子，否则令lchild
域指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示
其后继。为了避免混淆，需要改变结点结构，增加两个标志域：LTag，RTag。
其中：LTag = 0，lchild域指示其左孩子； LTag = 1，lchild域指示其前驱。
RTag = 0，rchild域指示其右孩子； RTag = 1，rchild域指示其后继。
以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中
指向结点前驱和后继的指针，叫做线索。加上线索的二叉树叫做线索二叉树。对二
杈树以某种次序遍历使其变成线索二杈树的过程叫做线索化。
在线索树上进行遍历，只要先找到序列中的第一个结点，然后依次找结点后继
直到其后继为空为止。//二叉树的二叉线索存储表示
typedef enum PointerTag {Link, Thread}; //Link:指针,Thread:线索
typedef struct BiThrNode{
ElemType data;
struct BiThrNode *lchild, *rchild;//左，右孩子指针
PointerTag LTag, RTag; //左，右标志
} *BiThrTree;
1.4 由上间述的储存方式，分别对新建立的二叉树进行先序遍历，中序遍历，后序
遍历，分别得到由江西理工大学①，到指定结点火车站⑧的路径。
二．概要设计：
2.1 主要模块：
由题是二叉树从根结点到指定结点的路径，因为二叉树有左右子树之分，又有不同
的遍历方式。主要的遍历方式有以下三种：
如图（1）
5
