2023年数据结构实验报告

实验目的

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

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

⑶学会打印输出二叉树的遍历结果。

实验内容

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

输出遍历结果。

【基本规定】

从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序

来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结

果打印输出。

【测试数据】

ABC**DE*G*4>F**9（其中中表达空格字符）

则输出结果为先序：ABCDEGF

中序:CBEGDFA

后序:CGBFDBA

【选作内容】

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

实验环节

（-）需求分析

1、在这个过程中，接受遍历的二叉树是从键盘接受输入（先序），

以二叉链表作为存储结构，建立的二叉树。因此，一方面要创建一

棵二叉树，而这棵二叉树是先序二叉树。本演示程序中，集合的元

素设定为大写字母ABCDEFG,输出的先序，中序，后序遍历分

别为ABCDEGF,CBEGDFA,CGBFDBAo二叉树可以表达为：

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

果打印出来。

2、在程序运营的过程中可以看到，以计算机提醒用户执行的方

式进行下去，即在计算机终端上提醒“输入二叉树的先序序列”后，

由用户在键盘上输入ABC##DE#G##F###,之后相应的选择

遍历及遍历结果显示出来。

3、程序执行的命令涉及：一方面是二叉树的先序序列被创建输

入,另一方面是对输入进去的先序序列有顺序的进行先序，中序，

后序遍历。最后是打印出二叉树的遍历结果。

4、测试数据

(1)在键盘上输入的先序序列ABC##DE#G##F###

(2)先序遍历结果ABCDEGF

⑶中序遍历结果CBEGDFA

(4)后序遍历结果CGBFDBA

(二)概要设计

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

义树递归遍历的相关操作为依据。有关以二叉链表作为存储结构,

建立二叉树的操作为：

typedefBTNode*BTree;〃定义二叉树的指针

BTreeCreatBTree(void)

(

BTreeT;

charch;

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

»return(NULL);〃读入#,返回空指针

eIse(

T=(BTNode*)malloc(sizeof(BTNode));//分派空间,

生成结点

T->data=ch;

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

T—>rchild=CreatBTree();〃构造右子

树

»return(T);

}

}

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

voidPreorder(BTreeT)//先序遍历

{

»if(T){

»printf("%c",T->data);〃访问结点

»Preorder(T->1child);〃先序遍历左子树

Preorder(T—>rchild);〃先序遍历右子树

»)

}

voidInorder(BTreeT)〃中序遍历

if(T)

»Inorder(T->Ichild);〃中序遍历左子树

printf("%c",T->data);//访问结点

Inorder(T—>rchild);//中序遍历右字树

voidPostorder(BTreeT)〃后序遍历

»if(T)

Postorder(T—>Ichild);〃后序遍历左子树

»»Postorder(T->rchild);//后序遍历右子树

»»printf("%c",T—>data);〃访问结点

)

3、本程序包含的模块

(1)结点单元模块

(2)构建先序二叉树模块

(3)二叉树遍历模块

(4)主程序模块

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

丰程序橙玲

（三）具体设计

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

typedefstructnode

（

»chardata;〃二叉树的元素类型

»structnode*1chiId;

»structnode*rchiId;

}BTNode;〃自定义二叉树的结类

型

typedefBTNode*BTree;〃定义二叉树的指针

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

先序来速立）。

BTreeCreatBTree（void）

»BTreeT;

»charch;〃定义输入的数据类型

»if((ch=getchar())=='#')//支持在键盘上输入先

序二叉树

return(NULL);〃读入#,返回空指针

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

把握，由于是先序输入，在输入时要在拟定的位置输入“#”号，

否则先序二叉树将不完整。

eIse(

»T=(BTNode*)malloc(sizeof(BTNode));//分派空

间，生成结点

»T->data=ch;

T->Ichild=CreatBTree();〃构造

左子树

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

return(T);

)

)

当输入的叶子结点完整之后，要return(T),否则输入将一直连

续下去不能跳出来。在程序的设计过程中，在适当的位置插入#

对于二叉树的遍历有着十分重要的作用，因此要明白二义树的先

序创建过程如何运营。

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

voidPreorder(BTreeT)〃先序

遍历

(

if(T){

printf("%cH,T->data);//访问结点

»Preorder(T->lchild);〃先序遍历左子树

»Preorder(T->rchild);〃先序遍历右子树

»)

)

这个是先序遍历，先序遍历与中序遍历，后序遍历相似，都是以不

同顺序访问子树及结点。先序遍历先访问根节点，先序遍历左子

树,再先序遍历右子树。而中序遍历是中序遍历左子树，访问根节

点，中序遍历右子树。后序遍历是后序遍历左子树，后序遍历右

子树，后序遍历根节点。三个遍历虽说顺序不一致，但是在程序

的编写上有很多可以相通的地方。以下分别是中序、后序的程序：

voidInorder(BTreeT)//中序遍

历

(

»if(T)

»(

1norder(T—>1child);

//中序遍历

左子树

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

〃访问结点

norder(T->rchild);

//中序遍历右字树

)

voidPostorder(BTreeT)//后序遍历

»if(T)

»»Postorder(T—>IchiId);//后序遍历左子树

»»Postorder(T->rchild)；//后序遍历右子树

»printf("%c",T->data);〃访问结点

0}

)

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

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

用旨在使每个程序模块可以链接在一起，调用各个函数以实现最

终的目的。

voidmain()

(

»BTreeroot;//数的根结点

inti;//可供选择的

整型变量i

叩rintf("\n");

printf(”请输入二叉树的先序序列，用#代表虚结点:")；

»root=CreatBTree()：〃返回根结点

do{〃循环语句

printf(”********************SELECT********

************\n").

gprintf("\tl:先序遍历\n");

»printf(”\t2:中序遍历\n")；

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

。printf("\tO:Exit\n");

Prntf(”\t******************************

********

%canf(M%d”i);〃输入菜单序号

switch(i)

acasel:printf(H先序遍历结果为：");

aPreorder(root);

3break;

^case2:printf("中序遍历结果为:")；

3。Inorder(root);

abreak;

3case3:printf(''后序遍历结果为：11);

38Postorder(root);

break;

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

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

default:exit(1);

3printf("\nH);

)

，while(i!=O);

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

（四）调试分析

1、实验涉及的部分涉及用二叉链表创建先序二叉树，对二叉树

进行三种遍历，最后是对三种遍历结果进行打印。在做这个实验

的过程中，我们一方面最先碰到的问题是用二叉链表存储先序二

义树，由于对二叉树存储的不进一步了解，我们在输入数据时，只

能对其无限输入，并不能及时的终止，导致的结果是程序停止不

了，运营不下去。不能返回的问题困扰了我们很久，在这个过程中，

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

找到了对的的方法。在这个过程中，我们也对二叉树的存储有了

更为深刻的了解，相信这在我们以后的学习中也有很大的帮助。

2、在实验过程中，我们尚有尝试了非递归的算法对于二叉树的遍

历，递归算法和非递归算法各有千秋，产用递归算法更为简朴明

了。

3、根节点的运用没有得到合理的开发，在主程序的链接中，创

建二叉树,返回根节点。接着是一个do循环对于选择三种遍历结

果的打印输出和退出操作，在开始的程序设计阶段没有发挥作用,

前期使用的是while和swith语句，没有返回根结点，导致算法

的运营不能有序进行下去。

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

义没有认真检查，程序前期运营过程中有很多的失误，导致了效

率低下。此后一定要重视拟定参数的变量和赋值属性的区别和标

志。

5、程序的设计基本是由一个个子模块联系到一起，由于前期没

有将这个程序的大体模型框架构架好，子模块之间的联系在主程

序中就出现了一些问题，因此在以后的实验过程中,要一方面构造

大框架更有助于子模块的链接。

（五）用户手册

1、本程序的运营环境为DOS操作系统，本程序执行文献为

“执行二叉树建立与遍历.exe”。

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

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

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

翔t二叉树,请输入完全二叉村的先序序列,用“代表虚结点:ABC“DE«；”P*”

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

显示相应的结果。

(六)测试结果

(1)一方面二叉链表存储(以先序创建)键盘输入

国壁二叉树的先用曲,用。代表虚结点：ABCMDEttCMPMt

ELECT*****,********

先

中

石

EX

⑵选择数字“1”，先序遍历:

先遍

1历

遍

历

2中

遍

历

3后

0

Ex

|创建二叉树，请输入完全二叉树的无序序列，用*代表虚结点:ABCUHDEIIGIWFIIg

先

遍历

中

历

遍

后

历

遍

以

历

遍

中

历

2遍

后

3历

0

Ex

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

2

中序遍历结果为:CBEGDFA

日建二叉树，请输入完全二叉树的先序序列，用■代表虚结点:ABCMDERGMFBM

***X*******X*X>l*>l*xSELECT***XW*X*X***XW

1:先用6历

2冲序遍历

3：后南鲂j

0：Exit

HHHHHHHHHHHWSELECT

1冼生遍历

2冲历直历

3：后序遍历

0：Exit

中序遍历结果为:CBEGDFA

HHHHHHHHHHHH»SELECT

i:先匠遍历

2冲庄遍历

3：后序遍历

0：Exit

(4)选择数字“3”后序遍历:

3

后序遍历结果为:CGEFDBA

1：先匠遍历

2：中住遍后

3：后用遍后

0：Exit

先序遍历结果为:ABCDEGF

i:先生遍历

2：中住遍历

3：后序遍历

0：Exit

中序遍历结果为:CBEGDFA

xxxxxxxxxxxxxxxxxxzxSELECT***«

,1:先生遍历

2：史:沮历

3：后序遍历

0：Exit

3

后序遍历结果为:CGEFDBfi

xxuxxxxxxxxxxxxxxSELECT****

1:先序渡历

2：中虎遍历

3：后序遍历

0：Exit

（七）心得体会

本次的实验过程中，和以前的课程设计有一些不同之处，初次产

用团队合作的方式完毕实验，我们也在这个过程中体会到了团队

合作的好处，大家积极分享彼此的经验,在分工的基础上合作，在

合作的前提下创新。学到了很多课本上没有的知识，也在团队合

作过程中提高了自身的能力。

（八）附录：源程序清单

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

//****************************************

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

typedefstructnode

(

chardata;//二叉树的元素类

型

»structnode*lchild;

structnode*rchiId;

JBTNode;〃自定义二义树的

结点类型

//*********************************************

********

typedefBTNode*BTree;〃定义二叉树

的指针

BTreeCreatBTree(void)

(

BTreeT;

charch;

»if((ch=getchar())==,#')//支持

在键盘上输入先序二叉树

。return(NULL);//读入#,返回空指针

e1se{

«T=(BTNode*)maI1oc(sizeof(BTNode));〃分派空间，生

成结点

dT->data=ch;

«T—>lchiId=CreatBTree();//构造左子树

T—>rchild=CreatBTree();〃构造右子树

return(T);

)

)

//*******************************************

***********

voidPreorder(BTreeT)〃先序遍历

(

if(T){

gprintf("%c”,T—>data);〃访问结点

aPreorder(T->lchiId);//先序遍历左子树

aPreorder(T->rchiId);//先序遍历右子树

)

)

//*****************************************

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

voidInorder(BTreeT)//中序遍历

if(T)

»Inorder(T->1chiId);//中序遍历左

子树

»printf("%c",T->data);〃访问结点

»Inorder(T->rchiId);〃中序遍历右字树

)

)

〃*********************************************

******

voidPostorder(BTreeT)//后序遍

历

(

if(T)

。(

»Postorder(T->lchiId);〃后序遍历左子树

»»Postorder(T—>rchild);〃后序遍历右子树

printf("%c",T->data);〃访问结点

。}

}

//*********************************

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

voidmain()

BTreeroot;//二又树的

根结点

»inti;

printf("\n");

prin