2023年数据结构二叉树操作实验报告

数据结构实验报告

指导教师xX实验时间：指23年

J_L月L日

学院计算机学院专业信息安全

班级XXXXXX学号XXXXX姓名XX实验室

S331

实验题目:二叉树操作

实验规定：

采用二叉树链表作为存储结构，完毕二叉树的建立,先序、中序和后序以及按层次

遍历的操作，求所有叶子及结点总数的操作。

示例程序：

#include"stdio.h〃

#include"string.h〃

#defineMax20〃结点的最大个数

typedefstructnode{

chardata;

structnode*1child,*rchild;

}BinTNode；〃自定义二叉树的结点类型

typedefBinTNode*BinTree;〃定义二叉树的指针

intNodeNum,leaf;〃NodeNum为结点数，leaf为叶子数

〃=二=======基于先序遍历算法创建二叉树==========

//=====规定输入先序序列，其中加入虚结点以不空指针的位置==========

BinTreeCreatBinTree(void)

BinTreeT;

charch;

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

return(NULL)；〃读入礼返回空指针

else(

<>T=(BinTNode*)malloc(sizeof(BinTNode))；生成结点

«»T->data=ch;

◎T—>1child=CreatBinTree()；//构造左子树

oT->rchi1d=CreatBinTree();〃构造右子树

return(T);

}

)

〃=二二==二二=NLR先序遍历=二========

voidPreorder(BinTreeT)

I

if(T){

gprintfT—>data);〃访问结点

oPreorder(T->lchi1d);〃先序遍历左子树

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

)

)

//=二=二二二二二LNR中序遍历二=========

//==========LRN后序遍历=========

//===采用后序遍历求二叉树的深度、结点数及叶子数的递归算法==

intTreeDepth(BinTreeT)

inth1,hr,max；

if(T){

hl=TreeDepth(T->1chi1d);“/求左深度

。hr=TreeDepth(T->rchild);//求右深度

max=hl>hr?hl:hr;〃取左右深度的最大值

NodeNum=NodeNum+1；〃求结点数

if(hl==0&&,hr==0)leaf=leaf+1;//若左右深度为0,即为叶子。

return(max+l);

)

elsereturn(0)；

)

〃====运用"先进先出"(FIFO)队列，按层次遍历二叉树========

voidLevelorder(BinTreeT)

I

intfront=0,rear=l;

BinTNode*cq[Max],*p;〃定义结点的指针数组cq

cq[1]=T;//根入队

while(front!=rear)

(

8front=(front+1)%NodeNum;

。p=cq[front]；〃出队

aprintf("%c〃，p->data);//出队，输出结点的值

gif(p->lchi1d!=NULL){

。rear=(rear+1)%NodeNum;

00cq[rear]=p->lchi1d；//左子树入队

oif(p->rchi1d!=NULL){

。rear=(rear+1)%NodeNum;

ocq[rear]=p->rchi1d;〃右子树入队

)

}

voidmain()

{

BinTreeroot；

inti,depth；

printf("\n〃)；

printf(〃CreatBinTree;Inputpreorder:，z)；〃输入完全二叉树的先

序序列，

//用#代表虚结点，如ABD###CE##F##

root=CreatBinTree();〃创建二叉树，返回根结点

do{//从菜单中选择遍历方式，输入序号。

oprintf(〃\t**********select********");

printf(〃\tl:PreorderTraversa1\n〃)；

8Printf("\t2:IorderTraversa1\n〃)；

oprintf("\t3:Postordertraversal\n〃)；

叩rintf("\t4:PostTreeDepth,Nodenumber,Leafnumber\n〃)；

printfC\t5:LevelDepth\nz，);//按层次遍历之前,先选择4,求出该树的结点

数。

叩rintf(H\t0:Exit\n〃)；

printf('\t*******************************\n〃)；

scanf(〃%d"，&i);//输入菜单序号(0-5)

switch(i){

必case1:printf(〃PrintBin_treePreorder:，z)；

。Preorder(root);//先序遍历

obreak；

ocase2:printf("PrintBinTreeInorder：〃)；

g^Inorder(root);〃中序遍历

◎break;

。case3：printf("PrintBin_TreePostorder：〃)；

gPostorder(root);〃后序遍历

break;

case4:depth=TreeDepth(root);〃求树的深度及叶子数

oprintf(〃BinTreeDepth=%dBinTreeNodenumber=%d，z,depth,N

odeNum);

ooprintf(〃BinTreeLeafnumber=%d，z,leaf)；

oobreak;

oe*>case5:printf(〃LevePrintBin_Tree：〃)；

Levelorder(root);//按层次遍历

gbreak;

defau1t:exit(l)；

°)

gprintf("\n〃)；

}while(i!=0);

)

实验内容及环节:

1、分析、理解程序。

2、添加中序和后序遍历算法.

3、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点(空指针),

如ABD###CE##F##,建立二叉树，求出先序、中序和后序以及按层次遍历序列,

求所有叶子及结点总数。

4、画出所设计的二义树，以后序遍历算法为例，画出执行踪迹示意图。给出实验结果。

5、给出实验结果。

改正后的完整程序：

#include"stdio.hn

#include"string.h"

#include<malloc.h>

#include<stdlib.h>

#defineMax20//结点的最大个数

typedefstructnode{

chardata；

structnode*Ichiid,*rchi1d；

}BinTNode；//自定义二叉树的结点类型

typedefBinTNode*BinTree;//定义二叉树的指针

intNodeNum,leaf；//NodeNum为结点数，leaf为叶子数

//==========基于先序遍历算法创建二叉树==============

〃=====规定输入先序序列，其中加入虚结点"#"以示空指针的位置==========

BinTreeCreatBinTree(void)

BinTreeT;

charch;

if((ch=getcha「())=='#')

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

else{

oT=(BinTNode)malloc(sizeof(BinTNode));//生成结点

。T->data=ch;

T->1chi1d=CreatBinTree();//构造左子树

ooT—>rchild=CreatBinTree();〃构造右子树

oreturn(T);

)

)

//========NLR先序遍历=============

voidPreorder(BinTreeT)

(

if(T){

oprintf(n%cn,T->data);〃访问结点

^Preorder(T->lchiId);〃先序遍历左子树

。Preorder(T->rchi1d);〃先序遍历右子树

)

)

//========LNR中序遍历===============

voidInorder(BinTreeT)

(

if(T){

。。Inorder(T—>lchiId);〃先序遍历左子树

printf(*'%cn,T->data);〃访问结点

Inorder(T—>rchi1d);〃先序遍历右子树

}

)

/*voidInorder(BinTreeT)。

whi1e(pI|!StackEmpty(BinTreeT)){

qf(T){Push(BinTreeT,T);T=T->1child；}//根指针进栈，遍历左子树

oelse{//根指针退栈，访问根节点，遍历右子树

Pop(BinTreeT,t)；

“if(!Visit(T->data))

returnERROR;

。T=T-rchild;

}//else

)//while

returnOK;

)

*/

//==========LRN后序历============

voidPostorder(BinTreeT)

(

if(T){

。Postorder(T—>lchild)；〃先序遍历左子树

。Postorder(T—>rchi1d);〃先序遍历右子树

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

〃=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法=:

intTreeDepth(BinTreeT)

(

inthl,hr,max；

if(T){

hl=TreeDepth(T->lchild);〃求左深度

hr=TreeDepth(T->rchi1d)；//求右深度

max=h1>hr?hl:hr;//取左右深度的最大值

"NodeNum=NodeNum+1；〃求结点数

if(hl==O&&hr==0)leaf=leaf+l;//若左右深度为0,即为叶子。

。retum(max+l);

)

elsereturn(0);

)

〃=二==运用"先进先出"(FIFO)队列，按层次遍历二叉树==========

voidLeve1order(BinTreeT)

(

intfront=0,rear=1；

BinTNode*cq[Max],*p;//定义结点的指针数组cq

cq[l]=T;//根入队

while(front!=rear)

(

®front=(front+l)%NodeNum;

p=cq[front];〃出队

printf("%cn,p->data);〃出队，输出结点的值

if(p->lchild!=NULL){

rear=(rear+1)%NodeNum;

。。cq[rear]=p->lchild;//左子树入队

0}

ooif(p->rchiId!=NULL){

。rear=(rear+1)%NodeNum；

。cq[rear]=p—>rchild;//右子树入队

}

)

)

//==========±函数=================

voidmain()

(

BinTreeroot;

inti,depth;

printf("\n")；

printf(℃reatBin_Tree；Inputpreorder:")；〃输入完全二叉树的先序序列,

〃用#代表虚结点，如ABD###CE##F##

root=CreatBinTree();〃创建二叉树，返回根结点

do{〃从菜单中选择遍历方式，输入序号。

»°printf(u\t**********select********");

printf("\t1：PreorderTraversal\n”)；

eprintf(n\t2:lorderTraversal\n");

«printf(M\t3：Postordertraversa1\nM);

ooprintf(n\t4:PostTreeDepth,Nodenumber,Leafnumber\n");

®printf(n\t5:Leve1Depth\n");//按层次遍历之前,先选择4,求出该树的结点数。

叩rimf("\tO：Exit\n")；

gprintf(%*******************************\n")♦

scanf("%dn,&i);//输入菜单序号(0—5)

switch(i){

gcase1:printf("PrintBin_treePreorder：")；

°Preorder(root)；//先序遍历

obreak;

case2:printf("PrintBin_TreeInorder:")；

。。Inorder(root);〃中序遍历

wbreak;

。case3：printf(”PrintBin_TreePostorder:")；

6Postorder(root);〃后序遍历

»break;

case4:depth=TreeDepth(root)；〃求树的深度及叶子数

。printf(nBinTreeDepth=%dBinTreeNodenumber=%d",d

epth,NodeNum);

aprintf(MBinTreeLeafnumber=%d",leaf)；

。break;

case5:printf(nLevePrintBin_Tree:")；

°Lev