数据结构实验 二叉树.docx
- 文档编号:9503846
- 上传时间:2023-05-19
- 格式:DOCX
- 页数:13
- 大小:245.87KB
数据结构实验 二叉树.docx
《数据结构实验 二叉树.docx》由会员分享,可在线阅读,更多相关《数据结构实验 二叉树.docx(13页珍藏版)》请在冰点文库上搜索。
数据结构实验二叉树
实验名称二叉树
班级:
学号:
姓名:
报告日期:
一、实验目的及要求
1.掌握二叉树的存储实现
2.掌握二叉树的遍历思想
3.掌握二叉树的常见算法的程序实现
二、实验内容
1.编写函数,输入字符序列,建立二叉树的二叉链表。
2.编写函数,实现二叉树的中序递归遍历算法。
(最好也能实现前缀和后缀遍历算法)
3.编写函数,实现二叉树的中序非递归遍历算法。
4.编写函数,借助队列实现二叉树的层次遍历算法。
5.编写函数,求二叉树的高度。
6.编写函数,求二叉树的结点个数。
7.编写函数,求二叉树的叶子个数。
8.编写函数,交换二叉树每个结点的左子树和右子树。
9.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法。
三、程序运行界面:
实验总结:
这次实验主要是对所学的二叉树的知识的应用,通过这次实验,我对二叉树的存储实现、遍历思想以及常见算法有了更深的理解,在课堂所学知识上,通过计算机的编程实现,印象更加深刻。
此外,实验要求我们要掌握一定的c语言编程知识,所以以后在这方面要更加努力。
程序代码:
#include
#include
#defineMAXSIZE100
typedefcharDataType;
typedefstructBiTNode/*二叉链表存储结构*/
{DataTypedata;
structBiTNode*lchild,*rchild;}BiTree;
typedefBiTree*ElemType;/*栈中数据元素类型,栈中保存结点指针*/
typedefstruct
{ElemTypedata[MAXSIZE];
inttop;
}SeqStack;/*栈的类型定义,顺序栈*/
typedefstruct
{ElemTypequeue[MAXSIZE];
intfront,rear;
}SP;
SeqStack*initSeqStack()/*初始化栈*/
{SeqStack*s;/*首先建立栈空间,然后初始化栈顶指针*/
s=(SeqStack*)malloc(sizeof(SeqStack));
s->top=-1;
returns;}
intpush(SeqStack*s,ElemTypex)
{if(s->top==MAXSIZE-1){/*栈满不能入栈*/
printf("栈满");
return0;}
s->top++;
s->data[s->top]=x;
return1;}
voidpop(SeqStack*s)/*出栈,假设栈不空*/
{s->top--;}
intempty(SeqStack*s)
{if(s->top==-1)return1;
elsereturn0;}
ElemTypetop(SeqStack*s)/*设栈不空*/
{return(s->data[s->top]);}
voidmain()
{BiTree*createBiTree();
voidInOrder(BiTree*T);
voidPreOrder(BiTree*T);
voidPostOrder(BiTree*T);
voidInOrderFei(BiTree*p);
voidLevelOrder(BiTree*T);
intheight(BiTree*T);
intNodes(BiTree*T);
intleafs(BiTree*T);
voidexchange(BiTree*T);
voidDisplay(BiTree*T);
voidmenu();
BiTree*bt;bt=NULL;intn,m=1;
while(m){
menu();scanf("%d",&n);getchar();
switch(n){
case0:
{printf("\n\t请输入结点的先序序列创建二叉树,0表示空:
");
bt=createBiTree();break;}/*生成二叉树*/
case1:
{printf("\n\t中序遍历二叉树:
");
InOrder(bt);printf("\n");break;}
case2:
{printf("\n\t先序遍历二叉树:
");
PreOrder(bt);printf("\n");break;}
case3:
{printf("\n\t后序遍历二叉树:
");
PostOrder(bt);printf("\n");break;}
case4:
{printf("\n\t非递归-中序遍历二叉树");
InOrderFei(bt);printf("\n");break;}
case5:
{printf("\n\t按层次遍历二叉树:
");
LevelOrder(bt);printf("\n");break;}
case6:
{printf("\n\t二叉树的高度为:
%d\n",height(bt));printf("\n");break;}
case7:
{printf("\n\t二叉树的结点数为:
%d\n",Nodes(bt));printf("\n");break;}
case8:
{printf("\n\t二叉树中叶子结点数为:
%d\n",leafs(bt));break;}
case9:
{printf("\n\t交换二叉树每个结点的左子树和右子树为:
");printf("\n\n");
exchange(bt);Display(bt);break;}
case10:
m=0;}}}
BiTree*createBiTree()/*递归算法创建二叉链表*/
{DataTypech;
BiTree*T;
ch=getchar();
if(ch=='0')returnNULL;
else{T=(BiTree*)malloc(sizeof(BiTree));
T->data=ch;
T->lchild=createBiTree();
T->rchild=createBiTree();
returnT;}}
voidInOrder(BiTree*T)/*中序遍历二叉树的递归算法*/
{if(T)
{InOrder(T->lchild);
printf("%c",T->data);
InOrder(T->rchild);}}
voidPreOrder(BiTree*T)/*先序遍历二叉树的递归算法*/
{if(T)
{printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);}}
voidPostOrder(BiTree*T)/*后序遍历二叉树的递归算法*/
{if(T)
{PostOrder(T->lchild);
PostOrder(T->rchild);
printf("%c",T->data);}}
/*中序遍历二叉树的非递归算法*/
voidInOrderFei(BiTree*p)
{SeqStack*s;s=initSeqStack();
while
(1)
{while(p){push(s,p);p=p->lchild;}/*先将结点指针压栈,待出栈时再访问*/
if(empty(s))break;
p=top(s);pop(s);printf("%c",p->data);p=p->rchild;}}
voidLevelOrder(BiTree*T)/*按层次遍历*/
{SP*p;
p=(SP*)malloc(sizeof(SP));
p->front=0;
p->rear=0;
if(T!
=NULL){
p->queue[p->front]=T;
p->front=p->front+1;}
while(p->front!
=p->rear){
T=p->queue[p->rear];
p->rear=p->rear+1;
printf("%c",T->data);
if(T->lchild!
=NULL){
p->queue[p->front]=T->lchild;/*左孩子进队列*/
p->front=p->front+1;}
if(T->rchild!
=NULL){
p->queue[p->front]=T->rchild;/*右孩子进队列*/
p->front=p->front+1;}}}
intheight(BiTree*T)/*求二叉树的高度*/
{inti,j;
if(!
T)return0;
i=height(T->lchild);/*求左子树的高度*/
j=height(T->rchild);/*求右子树的高度*/
returni>j?
i+1:
j+1;/*二叉树的高度为左右子树中较高的高度加1*/}
intNodes(BiTree*T)/*求二叉树的所有结点个数*/
{intn1,n2;
if(T==NULL)return0;
elseif(T->lchild==NULL&&T->rchild==NULL)return1;
else{n1=Nodes(T->lchild);
n2=Nodes(T->rchild);
returnn1+n2+1;}}
intleafs(BiTree*T)/*求二叉树的叶子结点个数*/
{intnum1,num2;
if(T==NULL)return0;
else{if(T->lchild==NULL&&T->rchild==NULL)return1;
num1=leafs(T->lchild);/*求左子树中叶子结点数*/
num2=leafs(T->rchild);/*求右子树中叶子结点数*/
returnnum1+num2;}}
voidexchange(BiTree*T)/*交换二叉树的所有左右子树*/
{BiTree*temp=NULL;
if(T->lchild==NULL&&T->rchild==NULL)return;
else{temp=T->lchild;
T->lchild=T->rchild;
T->rchild=temp;}
if(T->lchild)exchange(T->lchild);
if(T->rchild)exchange(T->rchild);}
/*交换后二叉树的遍历*/
voidDisplay(BiTree*T)
{printf("\t交换后二叉树按中序遍历输出:
");InOrder(T);printf("\n");
printf("\t交换后二叉树按先序遍历输出:
");PreOrder(T);printf("\n");
printf("\t交换后二叉树按后序遍历输出:
");PostOrder(T);printf("\n");}
voidmenu()
{printf("\n");
printf("\t\t0.创建二叉链表\n");
printf("\t\t1.中序遍历二叉树\n");
printf("\t\t2.先序遍历二叉树\n");
printf("\t\t3.后序遍历二叉树\n");
printf("\t\t4.非递归-中序遍历二叉树\n");
printf("\t\t5.层次遍历二叉树\n");
printf("\t\t6.求二叉树的高度\n");
printf("\t\t7.求二叉树的结点个数\n");
printf("\t\t8.求二叉树的叶子结点个数\n");
printf("\t\t9.交换二叉树每个结点的左子树和右子树\n");
printf("\t\t10.退出系统\n");
printf("\n\t请选择:
");}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构实验 二叉树 数据结构 实验 二叉