遍历二叉树(递归+非递归)实验报告

2021年1月25日发(作者：赤壁赋翻译)
实验报告

课程名称

实验名称

学生学号

实验目的：

掌握二叉树的结构特征，掌握用指针类型描述、遍历二叉树的运算。


实验条件：

电脑一台
Vc++6.0

实验内容与算法思想：

内容：

P213
实习题
1
建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序、
和后序）
，打印输出遍历结果。基本要求如下：

从键盘接受输入线序序列， 以二叉链表作为存储结构，建立二叉树（以先
序来建立）并对其进行遍历（先序、中序、后序）
，然后将遍历结果打印输出。
要求采用递归和非递归两种方法实现。


算法思想：

定义二叉树结构体类型时，也定义了一个顺序栈结构体类型，用以辅助完
成二叉树的非递归遍历。

由键盘输入二叉树先序序列，用扩展线序序列函数接受并创建二叉链表。

遍历前先判 断二叉树是否为空，若为空，执行空操作；否则依次执行各遍
历函数相应操作。

先序遍历算法思想，先访问根节点，然后按先序遍历左子树，再按先序遍
历右子树。

中序遍历算法思想，先按中序遍历左子树，再访问根节点，然后按中序访
问右子树。

后序遍历算法思想，先按后序遍历左子树，接着按中序遍历右子树，然后
访问根节点。

B11050226
二叉树的遍历

姓名

枯天蝎

数据结构

日期

班级

2013/05/30
B110502
运行结果：

递归算法：

非递归算法：

实验总结（结论或问题分析）
：

通过实验，加深了对
C
语言尤其是函数调用部分的认识和掌握。

没 有找到在实验运行结果上明确区分递归算法实现的遍历和非递归算法实
现的遍历的方法。


实验成绩


附：源程序：

递归算法程序

#include
#include
#include
#define maxsize 100
#define FALSE 0
#define TRUE 1

typedef struct node
















//
二叉树结构体类型定义

{



char data;
struct node *lchild;
struct node *rchild;

任课教师签名

张红霞

}bitnode,*bitree;


/*
扩展先序序列创建二叉链表
*/
void cteatebitree(bitree *bt)
{










}

/*
先序递归遍历
*/
void preorder(bitree root)
{






}

/*
中序递归遍历
*/
void inorder(bitree root)
{


if(root!=NULL)
{
if(root!=NULL)
{



}
printf(
preorder(root->lchild);
preorder(root->rchild);
char ch;
ch=getchar();
if(ch=='.')*bt=NULL;
else

{




}
*bt=(bitree)malloc(sizeof(bitnode));
(*bt)->data=ch;
cteatebitree(&((*bt)->lchild));
cteatebitree(&((*bt)->rchild));




}




}
preorder(root->lchild);
printf(
preorder(root->rchild);
/*
后序递归遍历
*/
void postorder(bitree root)
{






}


void main()
{











bitree bt;
cteatebitree(&bt);
printf(
先序递归遍历序列：
n
preorder(bt);
printf(
printf(
中序递归遍历序列：
n
inorder(b t);
printf(
printf(
后序递归遍历序列：
n
po storder(bt);
printf(
if(root!=NULL)
{



}
preorder(root->lchild);
preorder(root->rchild);
printf(