二叉树的遍历实验报告
一、需求分析
在二叉树的应用中,常常要求在树中查找具有某种特征的结点,或者对树中全部结点逐
一进行某种处理,这就是二叉树的遍历问题。
对二叉树的数据结构进行定义,建立一棵二叉树,然后进行各种实验操作。
二叉树是一个非线性结构,遍历时要先明确遍历的规则,先访问根结点还时先访问子树,
然后先访问左子树还是先访问有右子树,这些要事先定好,因为采用不同的遍历规则会产生
不同的结果。本次实验要实现先序、中序、后序三种遍历。
基于二叉树的递归定义,以及遍历规则,本次实验也采用的是先序遍历的规则进行建树
的以及用递归的方式进行二叉树的遍历。
二、系统总框图
主程序
建立二叉树 输入二叉树 先序遍历 中序遍历 后序遍历
结点结构
二叉树结点
Data
Lchild data Rchild
Lchild Rchild
三、各模块设计分析
(1)建立二叉树结构
建立二叉树时,要先明确是按哪一种遍历规则输入,该二叉树是按你所输入的遍历规则
来建立的。本实验用的是先序遍历的规则进行建树。
二叉树用链表存储来实现,因此要先定义一个二叉树链表存储结构。因此要先定义一
个结构体。此结构体的每个结点都是由数据域 data、左指针域 Lchild、右指针域 Rchild 组成,
两个指针域分别指向该结点的左、右孩子,若某结点没有左孩子或者右孩子时,对应的指针
1