最新数据结构实验报告x

实验目的

（ 1 ）学会用先序创建一棵二叉树。

（ 2 ）学会采用递归算法对二叉树进行先序、中序、后序遍历。

（ 3 ）学会打印输出二叉树的遍历结果。

实验内容

【问题描述】建立一棵二叉树，并对其进行遍历（先序、中序、后序） ， 打印输出遍历结果。

【基本要求】

从键盘接受输入（先序） ，以二叉链表作为存储结构，建立二叉树（以先 序来建立），并采用递归算法对其进行遍历（先序、中序、后序） ，将遍历 结果打印输出。

【测试数据】

ABC DE ?G 其中?表示空格字符）

则输出结果为 先序： ABCDEGF

中序： CBEGDFA

后序： CGBFDBA

【选作内容】

采用非递归算法实现二叉树遍历。

实验步骤

（一）需求分析

、在这个过程中， 接受遍历的二叉树是从键盘接受输入 （先序）， 以二叉链表作为存储结构，建立的二叉树。因此，首先要创建一 棵二叉树，而这棵二叉树是先序二叉树。本演示程序中，集合的 元素设定为大写字母 ABCDEFG ，输出的先序， 中序， 后序遍历 分别为 ABCDEGF,CBEGDFA,CGBFDBA 。二叉树可以表示 为：

A

接受的输入数据在进行递归的先序，中序，后序遍历后，分别将

结果打印出来。

2、 在程序运行的过程中可以看到，以计算机提示用户执行的方 式进行下去，即在计算机终端上提示“输入二叉树的先序序列”

后，由用户在键盘上输入 ABC##DE#G##F### ，之后相应的选 择遍历及遍历结果显示出来。

3、 程序执行的命令包括：首先是二叉树的先序序列被创建输入， 其次是对输入进去的先序序列有次序的进行先序，中序，后序遍 历。最后是打印出二叉树的遍历结果

T=(BTNode *)malloc(sizeof(BTNode));

T=(BTNode *)malloc(sizeof(BTNode)); // 分配空间，生成

4 、测试数据

）在键盘上输入的先序序列 ABC##DE#G##F###

）先序遍历结果 ABCDEGF

）中序遍历结果 CBEGDFA

）后序遍历结果 CGBFDBA

二）概要设计

1、为实现上述程序功能，应以二叉树定义的相关操作和二

叉树递归遍历的相关操作为依据 构，建立二叉树的操作为： typedef BTNode *BTree;BTree CreatBTree(void){BTree T;

叉树递归遍历的相关操作为依据 构，建立二叉树的操作为： typedef BTNode *BTree;

BTree CreatBTree(void)

{

BTree T;

char ch;

if((ch=getchar())=='#')

return(NULL);

else{

有关以二叉链表作为存储结

// 定义二叉树的指针

// 读入 #，返回空指针

结点

T->data=ch;

T->lchild=CreatBTree(); // 构造左子树

T->rchild=CreatBTree(); // 构造右子树 return(T);

}

}

、而有关先序、中序、后序遍历的递归操作为：

void Preorder(BTree T)

{

if(T){

printf("%c",T->data);

Preorder(T->lchild);

Preorder(T->rchild);

}

// 先序遍历

// 先序遍历

// 访问结点

// 先序遍历左子树

// 先序遍历右子树

void Inorder(BTree T)

// 中序遍历

}

}

if(T)

{

Inorder(T->lchild);

printf("%c",T->data);

Inorder(T->rchild);

}

}

// 中序遍历左子树

// 访问结点

// 中序遍历右字树

void Postorder(BTree T)

{

if(T)

{

Postorder(T->lchild);

Postorder(T->rchild);

printf("%c",T->data);

// 后序遍历

// 后序遍历左子树

// 后序遍历右子树

// 访问结点

3、本程序包含的模块

结点单元模块

构建先序二叉树模块

(3 )二叉树遍历模块

(4)主程序模块

各模块之间的调用关系如下：

主程序模块

结点单元模块

构建先序二叉树模块

二叉树遍历模块

(三)详细设计

1、元素类型，结点类型和指针类型 typedef struct node

char data;// 二叉树的元素类型

char data;

struct node *lchild;

struct node *rchild;

// 自定义二叉树的结类型

// 自定义二叉树的结类型

// 定义二叉树的指针

typedef BTNode *BTree;

2 、定义类型之后， 要以二叉链表作为存储结构， 建立二叉树（以 先序来建立）。

BTree CreatBTree(void){

BTree CreatBTree(void)

{

BTree T;

char ch;

if((ch=getchar())=='#')

叉树

return(NULL);

// 定义输入的数据类型

// 支持在键盘上输入先序二

// 读入 # ，返回空指针

对于二叉树的先序输入，在输入中要注意的是对于空指针的

把握，由于是先序输入，在输入时要在确定的位置输入“ # ”号， 否则先序二叉树将不完整。

else{

T=(BTNode *)malloc(sizeof(BTNode)); // 分配空间，生

成结点

T->data=ch;

T->lchild=CreatBTree(); // 构造左子树

T->rchild=CreatBTree(); // 构造右子树

return(T);

}

}

当输入的叶子结点完整之后，要 return(T) ，否则输入将一直持 续下去不能跳出来。在程序的设计过程中，在适当的位置插入 # 对于二叉树的遍历有着十分重要的作用，因此要明白二叉树的先 序创建过程如何运行。

、对于二叉树进行先序、中序、后序的遍历

void Preorder(BTree T)//

void Preorder(BTree T)

// 先序遍历

}

}

{

{

if(T){

// 访问结点

// 访问结点

// 先序遍历左子树

// 先序遍历右子树

Preorder(T->lchild);

Preorder(T->rchild);

}

// 中序遍历

// 中序遍历

void Inorder(BTree T)

if(T)

Inorder(T->lchild);

// 中序遍历左子树

printf("%c",T->data);

// 访问结点

Inorder(T->rchild);

// 中序遍历右字树

}

}

void Postorder(BTree T)

{

if(T)

{

Postorder(T->lchild);

Postorder(T->rchild);

// 后序遍历//

// 后序遍历

// 后序遍历左子树

// 后序遍历右子树

// 访问结点

4、主程序模块的链接。在这个模块中，不仅要实现二叉树先序

序列从键盘的输入，还要实现选择三个遍历的输出。主函数的作

用旨在使每个程序模块能够链接在一起，调用各个函数以实现最 终的目的。

void main()

{

// 数的根结点

// 数的根结点

// 可供选择的整型变量 i

int i;

printf("\n");

printf（" 请输入二叉树的先序序列，用 # 代表虚结点 :"）;

root=CreatBTree();do{

root=CreatBTree();

do{

// 返回根结点

// 循环语句

printf("********************SELECT********************\n");

printf("\t1: 先序遍历 \n");

printf("\t2: 中序遍历 \n");

printf("\t3: 后序遍历 \n");

printf("\t0:Exit\n");

printf("\t*********************************************\n")

printf("\t*

******************************************

**\n")

scanf("%d",&i);// 输入菜单序号

switch(i)

{

case 1:printf(" 先序遍历结果为 :");

Preorder(root);

break;

case 2:printf(" 中序遍历结果为 :");

Inorder(root);

break;

case 3:printf(" 后序遍历结果为 :");

Postorder(root);

break;

在这三个选择中，充分调用了先序、中序、后序遍历函数，选

择 1 、2 、3 数字实现对三个遍历的输出打印。

default:exit(1);

}

prin tf("\n");

}

while(i!=O);

}

5、函数的调用关系图反映了演示程序的层次结构:

调试分析

1、实验涉及的部分包括用二叉链表创建先序二叉树，对二叉树 进行三种遍历，最后是对三种遍历结果进行打印。在做这个实验 的过程中，我们首先最先碰到的问题是用二叉链表存储先序二叉 树，由于对二叉树存储的不深入了解，我们在输入数据时，只能 对其无限输入，并不能及时的终止，导致的结果是程序停止不了, 运行不下去。不能返回的问题困扰了我们很久，在这个过程中，

我们还尝试了一些用栈来对其进行存储，通过一遍遍的摸索，最

终找到了正确的方法。在这个过程中，我们也对二叉树的存储有 了更为深刻的了解，相信这在我们以后的学习中也有很大的帮 助。

2 、在实验过程中，我们还有尝试了非递归的算法对于二叉树的 遍历，递归算法和非递归算法各有千秋，产用递归算法更为简单 明了。

3、根节点的运用没有得到合理的开发，在主程序的链接中，创 建二叉树，返回根节点。接着是一个 do 循环对于选择三种遍历 结果的打印输出和退出操作，在开始的程序设计阶段没有发挥作 用，前期使用的是 while 和 swith 语句，没有返回根结点，造成 算法的运行不能有序进行下去。

4、刚开始是忽略了一些细节问题，对于元素类型，结点类型的

定义没有认真检查，程序前期运行过程中有很多的失误，导致了 效率低下。今后一定要重视确定参数的变量和赋值属性的区别和 标志。

5、程序的设计基本是由一个个子模块联系到一起，由于前期没 有将这个程序的大致模型框架构架好，子模块之间的联系在主程 序中就出现了一些问题，因此在以后的实验过程中，要首先构造 大框架更有利于子模块的链接。

（五）用户手册

1、 本程序的运行环境为 DOS操作系统，本程序执行文件为“执 行二叉树建立与遍历.exe ”。

2、 进入程序运行后会有说明指示

首先创建二叉树按照完全二叉树的先序序列输入，以回车键结

束，程序主界面就会形成：

创建二戈林這输入克全二更材的先呼住列.

ELECT

31$ JfJfT

U：Exlt

3、按照要求输入各个功能的命令，程序接受命令后立即执行并

且显示相应的结果

（六）测试结果

（1）首先二叉链表存储（以先序创建）键盘输入

册二叉林薛入融二财漑序序乳用■代巔给点:《BC删河IFm 尊* 耳耳m* ■ NlnM FLICT ■■ 3<N*NNIlM M4MH

1;磧朗

—It

(2)选择数字“ 1 ”，先序遍历:

先辛湎万给垄为堆aci）謂f怕

先辛湎万给垄为堆aci）謂f

怕■?■■*■■■■ ￡ ELECT**

2氓壬遍瓦 J诟序遍圧

削建二艮护?睛输入宪兰二見桝前先序序列,用#弋希鏗吉点汕DCMDH*血阳删15历历

谊鲁U 先牡 ■?■_■■■■ 二 12

削建二艮护?睛输入宪兰二見桝前先序序列,

用#弋希鏗吉点汕DCMDH*血阳删

15历历

谊鲁

U 先牡 ■?■_■■■■ 二 12 3 0-

閱芹遽历结杲为

3；lff

OsExit

sflflCDEGF ******^ ELECT*1

调历

历

(3)选择数字“ 2 ”，中序遍历:

中序遍历结果为:仙EGJFR

鋼:hie,荼at w兰w lew就慕桂ac沌直掘吕ELEGT特制熹恤甘* M： *过廉齋sfirac科抗握■養:m ［诜後页

2沖声毓

3踰遍历

8： Exit

请iS入死皇二罠村的先序评列.「则皆表虚笫黒“BCI^DRCM解?沖 MM M HHjCMMlifH 4 H.M H H |iiNMN.rig ELECTUMH 4 M 耳经暮植?融耳i诜应遍万

请iS入死皇二罠村的先序评列.「则皆表虚笫黒“BCI^DRCM解?沖 MM M HHjCMMlifH 4 H.M H H |iiNMN.rig ELECTUMH 4 M 耳经暮植?融耳

i诜应遍万

2；

3；后 SSffl

0：EkH

苧運冇鰭圭加CBEGDM

I鼻?鼻n耳■￡ ELECT耳算翼”耳塁秆*鼻耳■■鼻

i吨圧朗 话焦门 欧血i*

K M mtSi M'M'rtlH H li MWffcC M M M 9t Si H*M^4*MH M H1 W! W 9f'BrMtl

予遍方结羌为:加血囲

■M WK, Ml Wilf, 3C1[豪■英第酬耳 KJf￡ ELECT ：MHi3flCM；iEiC]t iOflCMEWE>f]fM：^l[if? i=feffiiffi 2；匚声遍历 3：启声谯历

a：Exit

先序遍历结果为；ABCDEGF

■■轉■?! MHMWJtKW M Mg EL ECT

B：Exit中序H

B：Exit

中序H历结杲为:CBEGDFR 料 icy 钿 料 g 胚 L ECT

2：中庄遍厉

旅后库遍历

0：Exit

后序逋历结思为:

后序逋历结思为

:CGEFDBA 十十select

■iHttit

■iHttit :5tJ^E:EX 12 3 0

（七） 心得体会

此次的实验过程中，和以前的课程设计有一些不同之处，首次产 用团队合作的方式完成实验，我们也在这个过程中体会到了团队 合作的好处，大家积极分享彼此的经验，在分工的基础上合作， 在合作的前提下创新。学到了很多课本上没有的知识，也在团队 合作过程中提升了自身的能力。

（八） 附录：源程序清单

#in clude<stdio.h> #in clude<stdlib.h>

#include<string.h> //*****************************************************

typedef struct node

{

char data; // 二叉树的元素类型

struct node *lchild;

struct node *rchild;

}BTNode; // 自定义二叉树的结点类 型

typedef BTNode *BTree;BTree CreatBTree(void){

typedef BTNode *BTree;

BTree CreatBTree(void)

{

BTree T;

char ch;

if((ch=getchar())=='#')

先序二叉树

// 定义二叉树的指针

// 支持在键盘上输入

return(NULL);//

return(NULL);

// 读入 #，返回空指针

}

}

//

// 先序遍历

// 访问结点

// 先序遍历左子树

// 先序遍历右子树

else{

T=(BTNode *)malloc(sizeof(BTNode)); // 分配空间，生成 结点

T->data=ch;

T->lchild=CreatBTree(); // 构造左子树

T->rchild=CreatBTree(); // 构造右子树 return(T);

}

}

void Preorder(BTree T)

{

if(T){

printf("%c",T->data);

Preorder(T->lchild);

Preorder(T->rchild);

}

}

// 中序遍历//

// 中序遍历

// 中序遍历左子树

// 访问结点

// 中序遍历右字树

**************************************************** void Inorder(BTree T)

{

if(T)

{

Inorder(T->lchild);

printf("%c",T->data);

Inorder(T->rchild);

}

}

// 后序遍历

// 后序遍历

// 后序遍历左子树

// 后序遍历右子树

// 访问结点

void Postorder(BTree T)

{

if(T)

{

Postorder(T->lchild);

Postorder(T->rchild);

printf("%c",T->data);

}

void main()

{

BTree root; // 二叉树的根结点

int i;

printf("\n");

printf(" 请输入二叉树的先序序列，用 # 代表虚结点 :"); root=CreatBTree(); // 返回根结点 do{ //do 做循环打印遍历结果

n");

printf("\t1:

先序遍历 \n");

printf("\t2:

中序遍历 \n");

printf("\t3:

后序遍历 \n");

printf("\t0:Exit\n");

}

}

printf("\t*********************************************\n")

printf("\t*

******************************************

**\n")

scanf("%d",&i);// 输入菜单序号

switch(i)

{

case 1:printf(" 先序遍历结果为 :");

Preorder(root);

break;

case 2:printf(" 中序遍历结果为 :");

Inorder(root);

break;

case 3:printf(" 后序遍历结果为 :");

Postorder(root);

break;

default:exit(1);

printf("\n");

}

while(i!=0);

}

实验结果分析

在这个实验过程中，我们碰到了一些问题，比如说二叉树的存储 没有能够准确返回，主函数与模块函数之间没有实现很好的连接 造成调试程序上用了很多时间。忽略了一些细节问题，对于元素 类型，结点类型的定义没有认真检查，程序前期运行过程中有很 多的失误，导致了效率低下。但是我们充分发挥了团队的力量， 依次解决了这些问题，实验结果的正确性也得到了验证。虽说可 能仍存在一些不足之处，我们也会虚心接受，在过程中力求做到 尽可能的完善