数据结构实验 二叉树.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请选择:
"）;}
升级会员 