北航计软实验报告二.docx
《北航计软实验报告二.docx》由会员分享，可在线阅读，更多相关《北航计软实验报告二.docx（12页珍藏版）》请在冰点文库上搜索。
北航计软实验报告二
实验报告
实验名称二叉树
班级140228
学号14021198
姓名程浩
成绩
实验概述：
掌握二叉树的存储结构
【实验目的及要求】
1．分别编制实验内容中题2、3、4的三个子程序。
2．以实验二图所示的二叉树为例编制主程序，实现下述功能，并运行这个程序。
（1）输入二叉树用链式结构存储；
（2）调用题2的子程序，并输出结果；
（3）调用题3的子程序，并输出结果；
（4）调用题4的子程序，并输出结果；
3．自行设计一棵二叉树，重复步骤2。
4．整理程序清单与所有结果，并写出实验报告。
【实验原理】
（1）二叉树的链式存储结构
二叉树的每一个结点i有三个域：
值域V（i），左链域L（i），右链域R（i）。
我们分别用三个一维数组表示它们，并用头指针HBT指向二叉树的根结点。
具体存储方案由读者自行考虑。
（2）按层次输出所有结点
为了达到按层次扫描结点的目的，需要设置一个容量足够大的循环队列（可以用一个首尾相接的一维数组模拟）。
初始时，将根结点序号入队。
然后每次从队列中退出一个结点序号，将此结点的值及左右链指针输出，且依次将此结点的左右链指针入队。
这个过程一直进行到队列空为止。
（3）输出所有叶子结点
叶子结点的左右指针域均为零。
因此，为了输出所有叶子结点，需要设置一个容量足够大的栈S（可以用一个一维数组模拟它，栈底在数组的第一个元素处）。
具体过程是：
从根结点开始扫描二叉树，如果扫描的当前结点的左右均为零，则输出次叶子结点；否则将非零的右指针和左指针值推入堆栈。
然后从栈中退出一个结点序号重新进行这个过程，直至栈空为止。
（4）将所有左右子树值交换
这个问题的处理和输出所有叶子结点的问题很类似，只要将非叶子结点的左右指针交换即可。
【实验环境】（使用的软硬件）
PC
VisualC++
实验内容：
【实验方案设计】
【实验过程】（实验步骤、记录、数据、分析）
问题2的程序清单如下：
#include
usingnamespacestd;
classtree//构建一个二叉树类，用二叉链表形式存储
{
public:
typedefstructCSNode{
intdata;//结点值
inttag;//结点序号
structCSNode*l,*r;
}CSNode,*CSTree;
structCSNode*temp;
structCSNodecsnode[10];
CSNode*hbt;//设置根结点指针
};
classCq:
publictree//构建二叉树的子类循环队列，用来按层次输出结点
{
public:
CSNodecq[10];
intfront,rear;//设置头指针和尾指针
voidadd（CSNode*p）//添加函数
{
rear++;
if（rear==10）rear=0;
cq[rear]=*p;
}
voiddel（）//删除函数
{
front++;
if（front==10）front=0;
}
};
classstack:
publictree//构建二叉树的子类栈，用来输出叶子结点和交换左右子树
{
public:
CSNodesta[10],s;
inttop;//栈顶指针
voidpush（CSNode*p）//入栈函数
{
sta[top]=*p;
top++;
if（top==10）cout<<"栈满！
"<}
CSNodepop（）//出栈函数
{
top--;
returnsta[top];
}
};
intmain（）{
inti;
treet;//构建一个二叉树对象
t.csnode[0].data=15;t.csnode[0].l=&t.csnode[1];t.csnode[0].r=&t.csnode[2];//二叉树的初始化
t.csnode[1].data=98;t.csnode[1].l=&t.csnode[3];t.csnode[1].r=&t.csnode[4];
t.csnode[2].data=6;t.csnode[2].l=&t.csnode[5];t.csnode[2].r=NULL;
t.csnode[3].data=20;t.csnode[3].l=&t.csnode[6];t.csnode[3].r=&t.csnode[7];
t.csnode[4].data=10;t.csnode[4].l=NULL;t.csnode[4].r=NULL;
t.csnode[5].data=45;t.csnode[5].l=NULL;t.csnode[5].r=&t.csnode[8];
t.csnode[6].data=30;t.csnode[6].l=NULL;t.csnode[6].r=NULL;
t.csnode[7].data=40;t.csnode[7].l=NULL;t.csnode[7].r=NULL;
t.csnode[8].data=60;t.csnode[8].l=&t.csnode[9];t.csnode[8].r=NULL;
t.csnode[9].data=70;t.csnode[9].l=NULL;t.csnode[9].r=NULL;
for（i=0;i<10;i++）t.csnode[i].tag=i;
t.hbt=&t.csnode[0];
if（t.hbt==NULL）cout<<"这个二叉树是空的"<cout<<"以下是按层次输出所有结点：
"<CqCq1;//实例化队列类
Cq1.front=0;Cq1.rear=0;
Cq1.add（t.hbt）;
while（Cq1.front!
=Cq1.rear）
{
Cq1.del（）;
cout<<"当前结点的序号为"<if（Cq1.cq[Cq1.front].l!
=NULL）{
cout<<"该结点的左孩子的序号为"<tag<<",值为"<data<Cq1.add（Cq1.cq[Cq1.front].l）;
}
if（Cq1.cq[Cq1.front].r!
=NULL）{
cout<<"该结点的右孩子的序号为"<tag<<",值为"<data<Cq1.add（Cq1.cq[Cq1.front].r）;
}
cout<<"\n"<}
cout<<"\n\n********************************************************\n\n"<cout<<"以下是输出所有叶子结点：
"<stackst1;//实例化栈类
st1.top=0;
st1.push（t.hbt）;
while（st1.top!
=0）
{
st1.s=st1.pop（）;
if（st1.s.l!
=NULL）st1.push（st1.s.l）;
if（st1.s.r!
=NULL）st1.push（st1.s.r）;
if（（st1.s.l==NULL）&&（st1.s.r==NULL））
cout<<"结点"<}
cout<<"\n\n********************************************************\n\n"<cout<<"以下是输出所有交换左右树的结点的值：
"<stackst2;//实例化栈类
st2.top=0;
st2.push（t.hbt）;
while（st2.top!
=0）
{
st2.s=st2.pop（）;
if（（st2.s.l!
=NULL）&&（st2.s.r!
=NULL））
{
cout<<"当前结点的值：
"<data<<"和"<data<t.temp=st2.s.l;st2.s.l=st2.s.r;st2.s.r=t.temp;//交换左右指针
cout<<"交换后左右孩子的值分别为"<data<<"和"<data<st2.push（st2.s.l）;st2.push（st2.s.r）;
}
elseif（（st2.s.l!
=NULL）&&（st2.s.r==NULL））
{
cout<<"当前结点的值：
"<data<<"，没有右孩子"<t.temp=st2.s.l;st2.s.l=st2.s.r;st2.s.r=t.temp;//交换左右指针
cout<<"交换后没有左孩子，右孩子的值为"<data<st2.push（st2.s.r）;
}
elseif（（st2.s.l==NULL）&&（st2.s.r!
=NULL））
{
cout<<"当前结点的值：
"<data<<"，没有左孩子"<t.temp=st2.s.l;st2.s.l=st2.s.r;st2.s.r=t.temp;//交换左右指针
cout<<"交换后没有右孩子，左孩子的值为"<data<st2.push（st2.s.l）;
}
}
system（"pause"）;
return0;
}
程序输出结果如下：
问题3要求自行设计一个二叉树，自行设计的二叉树如下：
程序与2相似，故不列程序清单，而只列出程序运行结果如下：
【结论】（结果）
二叉树可用二叉链表的形式储存，并可以以堆栈、循环队列的形式进行输出。
在编程的时候利用这些特定的数据结构对解决问题是有一定益处的。
指导教师评语及成绩：
成绩：
指导教师签名：
批阅日期：
升级会员 