实验一：二叉树的建立及其遍历

《实验一：二叉树的建立及其遍历》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、成绩:课程名称:实验项目:姓名:专业:班级:学号:实验报告数据结构实验二叉树的建立及遍历计算机科学与技术李翠超计算机16-61609040307计算机科学与技术学院实验教学中心2017年11月240实验项目名称：—二叉树的建立及遍历一、实验目的1.熟悉掌握课本二叉树相关理论知识2.实践与理论相结合，以实践加深对理论理解并掌握二叉树的应用程序3.学会二叉树的创建，遍历等其他基本操作的代码实现二、实验内容1.二叉树的创建代码实现2•二叉树先序、中序、后序遍历代码实现3・13寸间有余的同学尝试二叉树的

2、其他各项功能的代码实现，如:测量二叉树的深度，宽度，结点数，叶子结点数及某个结点左右孩子三、实验操作步骤1.阅读实验内容和要求2.编写程序实现以下功能(1)建立一棵二叉树(2)先序、中序、后序遍历此二叉树3.根据编译的结果，如果错误的及时找出并改正四、实验结果分析1.在键盘上输入一段字符串，建立一棵二叉树例如输入：abdg##h##e#Inncnvjnnn此二叉树的结构如下图:2•输出先序、中序、后序遍历序列（采用递归遍历）左■”C:UsersdellDesktop2二叉树链靖构实现.

3、BiTreeLinlcexe-□>［前序遍历二叉树:ABDGHEICFJ［中序逼历二叉树:GDHBEIACJF{后序遍历二叉树:GHDIEBJFCA{Processreturned0(0x0)executiontime:39.290sPressanykeytocontinuc.五、源代码#include"string.h"#include"stdio.h"#include"stdlib.h"#dcfincOK1#defineERROR0#defineTRUE1#defineFALSE0#defi

4、neMAXSIZE100〃存储空间初始分配量typedefintStatus;//Status是函数的类型，其值是函数结果状态代码，如OK等typedefcharTElemType;TElemTypeNil=*：〃字符型以空格符为空Statusvisit(TElemTypee){printf(”％c“,e);returnOK;}typedefstructB汀Node//结点结构{TElemTypedata;//结点数据structBiTNodc*lchild,*Tchild;//左右孩了指针}B

5、iTNode,*BiTree;//构造空二叉树TStatusInitBiTree(BiTree*T){*T=NULL;returnOK;}//初始条件：二叉树T存在。操作结果：销毁二叉树TStatusDestroyB汀ree(B汀ree*T){if(*T){if((*T)->lchild)//有左孩子DestroyBiTree(&(*T)->lchild);//销毁左孩子子树if((*T)->rchild)//有右孩子DestroyBiTree(&(*T)->rchild);//销毁右孩子子树哈

6、尔滨理工大学计算机科学与技术学院实验教学中心frcc(*T);//释放根结点*T=NULL;//空指针赋()}}//按前序输入二叉树中结点的值(一个字符)〃#表示空树，构造二叉链表表示二叉树T。StatusCreateBH7ee(B汀ree*T){TElemTypech;scanf("%c",&ch);ch=stiiindex++];if(ch==,#')*T=NULL;else{*T=(BiTree)malloc(sizeof(BiTNode));if(!*T)returnERROR;(*T)

7、->data=ch;//生成根结点CreateBiTree(&(*T)->lchild);//构造左子树CreateBiTree(&(*T)・>rchild);//构造右子树}//初始条件：二叉树T存在//操作结果：前序递归遍历TStatusPreOrderTraverse(BiTreeT){if(T==NULL)return;prin(fT%c“,T・>dala);〃显示结点数据，可以更改为其它对结点操作PrcOrdcrTravcrsc(T->lchild);//再先序遍历左了树PreOrde

8、rTraverse(T->rchiId);//最后先序遍历右子树returnOK;}//初始条件：二叉树T存在//操作结果：屮序递归遍历TStatusInOrderTraverse(BiTreeT)if(T=NULL)return;InOrderTraverse(T->lchiId);//中序遍历左子树printf(”％c“,T・>data);〃显示结点数据，可以更改为其它对结点操作InOrderTraverse(T->rchild);//最后中序遍历右子树returnOK;//初始条件：二叉树