数据结构二叉树实验报告.docx
《数据结构二叉树实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构二叉树实验报告.docx（17页珍藏版）》请在冰点文库上搜索。
数据结构二叉树实验报告
一、需求分析：
编写一段程序，对二叉树进行复合操作，包括创建一棵二叉树，显示二叉树的树型结构，对创建的二叉树进行先根、中根、后根三种方式进行遍历，并且打印出叶子结点，并且可以随时删除我们创建的二叉树，然后用循环语句将上述的操作封装起来，使之能够进行可重复、连续的操作。
输入为a-z或者是A-Z之间的字符，用‘@’字符作为结束当前结点的标识符。
二、概要设计：
本程序要用到的数据类型
structBinTreeNode
{DataTypeinfo;
PBinTreeNodellink;
PBinTreeNoderlink;
};
然后定义我们需要的指针类型
typedefstructBinTreeNode*PBinTreeNode;/*定义指向二叉树结点的指针类型*/
typedefPBinTreeNode*PBinTree;/*定义指向树型结点的指针类型*/
程序需要用到的自定义函数
1．创建一个二叉树根节点
PBinTreeCreate_BinTreeRoot（void）
2．创建一个二叉树的节点
PBinTreeNodeCreate_BinTreeNode（void）
3．创建一棵二叉树
PBinTreeNodeCreate_BinTree（void）
4．用先根的方法遍历一棵二叉树
voidpreOrder（PBinTreeNodepbnode）
5．用中根的方法遍历一棵二叉树
voidinOrder（PBinTreeNodepbnode）
6．用后根的方法遍历一棵二叉树
voidpostOrder（PBinTreeNodepbnode）
7．打印出我们创建的二叉树的树型结构
voidoutputTree（PBinTreeNodepbnode,inttotalSpace）
8．打印出二叉树的叶子结点
voidleaves（PBinTreeNodepbnode）
9．释放我们所申请的所有结点空间
voidfreeAllNodes（PBinTreeNodepbnode）
10．判断我们输入的是否是合格的字符
intisalphabet（chari）
三、详细设计：
1．PBinTreeNodeCreate_BinTreeNode（void）
我们定义一个指向二叉树结点类型的指针PBinTreeNode，然后，申请一个二叉树结点大小的空间，对左右子结点赋为空。
2．创建一个二叉树根节点
定义一个指向二叉树结点的指针的指针即：
BinTreeNode**pbtree,或者是：
PBinTreeNode*pbtree;用于存放树的根结点，同时，将我们创建的二叉树的地址传给它即：
*pbtree=Create_BinTree（）;
3．创建一棵二叉树
首先我们定义一个DataType类型的变量i,用于存放我们输入的字符（即作为缓冲区），并用scanf函数去接收它，由于使用scanf函数时，会出现吸收我们输入的回车字符，并将会车作为接收的字符的情况发生，为了避免这种情况，我们用函数fflush（stdin）将缓冲区的字符全部冲掉，然后再吸收我们输入的字符，就可以完全避免此类问题的发生。
我们定义我们输入的字符是从a-z或者是A-Z，用字符@为我们结束当前结点左或者右结点的字符，然后递归调用左右子树，此时我们将一棵二叉树全整的创建出来了。
4．用先根的方法遍历一棵二叉树
先访问根结点，打印出它里面的信息，然后递归调用左子树和右子树。
5．用中根的方法遍历一棵二叉树
先递归调用左子树，打印出里面的信息，在打印出根结点信息，然后递归调用右子树，打印出里面的信息。
6．用后根的方法遍历一棵二叉树
先递归调用左子树，打印出里面的内容，然后递归调用右子树，打印出里面的内容，然后是根结点的内容。
7.打印出我们创建的二叉树的树型结构
先递归调用右子树，如果结点不为空的话，空格数加5，如果为空的话，就打印出右子树的内容，然后递归调用左子树。
8．打印出二叉树的叶子结点
如果当前结点的左右子树都为空的话，就打印出此结点的信息，如果左子树不为空的话，递归调用左子树，如果右子树不为空的话，递归调用右子树。
9．释放我们所申请的所有结点空间
如果当前的左子树不为空，则遍历左子树，如果右子树不为空的话，则遍历右子树，如果都不位空的话，分别调用左右子树，如果左右都为空的话，就释放左右结点空间，并将当前结点置为空。
10．主函数的安排：
先创建好我们要的二叉树，之后，我们就可以对此而二树进行多种操作，我们定义了6种集合操作，并对用户输入的信息进行检测，正确的提示出错信息，如果选择的是我们定义的操作之一的话，对应的我们设置出不同的case语句。
如果我们选择的是释放所有的结点空间的话，我们需要屏蔽掉所有的菜单信息，提示用户重新创建一棵二叉树，并对它进行重新操作。
如果我们选择退出，但是没有选择释放掉所有的节点空间时，我们需要考虑到此类的情形，应调用voidfreeAllNodes（PBinTreeNodepbnode）自动的释放掉所有的结点空间，正常的退出。
四、用户使用说明：
当用户还没有创建二叉树时，提示用户输入数据：
Pleaseinputchartothebinatree,@toexitcurrentnode:
Pleaseinputachar:
这时用户用键盘输入，每输入一个字符回车一次,输入为a-z或者是A-Z之间的字符，用‘@’字符作为结束当前结点的标识符
当用户，创建了二叉树之后，出现控制菜单：
Pleasechoosethemodeyouwanttooperatewiththebinatree:
1.display2.preOrder3.inOrder4.postOrder5.leaves6.freenodes0toexit:
此时用户可以选择操作：
1.自动的打印出树型结构2.先根遍历3.中根遍历4.后根遍历
5.打印叶子结点6.释放所有结点空间0.退出
五、测试结果：
1．测试完全二叉树的情形：
输入（每输入一个字符回车一次）：
ABC@@D@@EF@@G@@
自动的打印出树型结构：
Displaythebinatreedatadirectly:
G
E
F
A
D
B
C
三种遍历方式和叶子结点，测试如下：
先根：
DatainpreOrder:
ABCDEFG
中根：
DataininOrder:
CBDAFEG
后根：
DatainpostOrder:
CDBFGEA
打印叶子结点：
Leaves:
CDFG
释放所有结点空间：
Freeallnodes:
Allnodehavebeenfreedsuccessfully.
自动提示创建一棵新的二叉树：
Nowcreatinganewbinatree...
Pleaseinputchartothebinatree,@toexitcurrentnode:
Pleaseinputachar:
2测试非完全二叉树的情形
输入（每输入一个字符回车一次）：
ABCD@@@@@
自动的打印出树型结构：
A
B
C
D
三种遍历方式和叶子结点，测试如下：
先根：
DatainpreOrder:
ABCD
中根：
DataininOrder:
DCBA
后根：
DatainpostOrder:
DCBA
打印叶子结点：
Leaves:
D
释放所有结点空间：
Freeallnodes:
Allnodehavebeenfreedsuccessfully.
自动提示创建一棵新的二叉树：
Nowcreatinganewbinatree...
Pleaseinputchartothebinatree,@toexitcurrentnode:
Pleaseinputachar:
如果我们想结束此次的操作，退出本程序，就可以输入0，程序自动的释放所有的结点空间：
Pleasechoosethemodeyouwanttooperatewiththebinatree:
1.display2.preOrder3.inOrder4.postOrder5.leaves6.freenodes0toexit:
0
Dealingwiththelastjob,tofreeallnodes
Allnodehavebeenfreedsuccessfully
六、附录：
#include
#include
#include
#defineNULL0
#defineDataTypechar
typedefstructBinTreeNode*PBinTreeNode;
typedefPBinTreeNode*PBinTree;
structBinTreeNode
{DataTypeinfo;
PBinTreeNodellink;
PBinTreeNoderlink;
};
PBinTreeNodeCreate_BinTree（void）;
PBinTreeCreate_BinTreeRoot（void）
{PBinTreepbtree;
pbtree=（PBinTree）malloc（sizeof（structBinTreeNode））;
if（pbtree==NULL）pbtree=（PBinTree）realloc（pbtree,sizeof（structBinTreeNode））;
*pbtree=Create_BinTree（）;
return（pbtree）;
}
PBinTreeNodeCreate_BinTreeNode（void）
{PBinTreeNodepbnode;
pbnode=（PBinTreeNode）malloc（sizeof（structBinTreeNode））;
if（pbnode==NULL）pbnode=（PBinTreeNode）realloc（pbnode,sizeof（structBinTreeNode））;
elsepbnode->llink=pbnode->rlink=（PBinTreeNode）NULL;
return（pbnode）;
}
intisalphabet（chari）
{
if（i>='a'&&i<='z'||i>='A'&&i<='Z'||i=='@'）
return1;
elsereturn0;
}
PBinTreeNodeCreate_BinTree（void）
{PBinTreeNodepbnode;
DataTypei;
printf（"Pleaseinputachar:
\t"）;
fflush（stdin）;
scanf（"%c",&i）;
fflush（stdin）;
while（!
isalphabet（i））
{
printf（"Sorry,yourinputcharisnotinalphabet,pleaseinputagain:
"）;
scanf（"%c",&i）;
fflush（stdin）;
}
if（i=='@'）pbnode=NULL;
else
{
pbnode=（PBinTreeNode）malloc（sizeof（structBinTreeNode））;
if（pbnode==NULL）
{
printf（"Outofspace!
\n"）;
returnpbnode;
}
pbnode->info=i;
pbnode->llink=Create_BinTree（）;
pbnode->rlink=Create_BinTree（）;
}
returnpbnode;
}
voidoutputTree（PBinTreeNodepbnode,inttotalSpace）
{inti;
if（pbnode!
=NULL）
{
totalSpace+=5;
outputTree（pbnode->rlink,totalSpace）;
for（i=0;iprintf（"%c\n",pbnode->info）;
outputTree（pbnode->llink,totalSpace）;
}
}
voidpreOrder（PBinTreeNodepbnode）
{
if（pbnode==NULL）return;
printf（"%c\t",pbnode->info）;
preOrder（pbnode->llink）;
preOrder（pbnode->rlink）;
}
voidinOrder（PBinTreeNodepbnode）
{
if（pbnode==NULL）return;
inOrder（pbnode->llink）;
printf（"%c\t",pbnode->info）;
inOrder（pbnode->rlink）;
}
voidpostOrder（PBinTreeNodepbnode）
{
if（pbnode==NULL）return;
postOrder（pbnode->llink）;
postOrder（pbnode->rlink）;
printf（"%c\t",pbnode->info）;
}
voidleaves（PBinTreeNodepbnode）
{
if（pbnode->llink!
=NULL&&pbnode->rlink==NULL）
leaves（pbnode->llink）;
if（pbnode->rlink!
=NULL&&pbnode->llink==NULL）
leaves（pbnode->rlink）;
if（pbnode->llink!
=NULL&&pbnode->rlink!
=NULL）
{
leaves（pbnode->llink）;
leaves（pbnode->rlink）;
}
if（pbnode->llink==NULL&&pbnode->rlink==NULL）
{
printf（"%c\t",pbnode->info）;
return;
}
}
voidfreeAllNodes（PBinTreeNodepbnode）
{
if（pbnode->llink!
=NULL&&pbnode->rlink==NULL）
freeAllNodes（pbnode->llink）;
if（pbnode->rlink!
=NULL&&pbnode->llink==NULL）
freeAllNodes（pbnode->rlink）;
if（pbnode->llink!
=NULL&&pbnode->rlink!
=NULL）
{
freeAllNodes（pbnode->llink）;
freeAllNodes（pbnode->rlink）;
}
if（pbnode->llink==NULL&&pbnode->rlink==NULL）
{
free（pbnode->llink）;
free（pbnode->rlink）;
pbnode=NULL;
return;
}
}
intmain（）
{PBinTreepbtree;
inti;
inttotalSpace=0;
printf（"Pleaseinputchartothebinatree,@toexitcurrentnode:
\n"）;
pbtree=Create_BinTreeRoot（）;
printf（"Displaythebinatreedatadirectly:
\n"）;
outputTree（*pbtree,totalSpace）;
printf（"Pleasechoosethemodeyouwanttooperatewiththebinatree:
\n"）;
printf（"1.display2.preOrder3.inOrder4.postOrder5.leaves6.freenodes0toexit:
"）;
scanf（"%d",&i）;
while（i>6||i<0）
{
printf（"\nYouchoiceisillegalpleaseinputagain:
\n"）;
printf（"1.display2.preOrder3.inOrder4.postOrder5.leaves6.freenodes0toexit:
"）;
scanf（"%d",&i）;
}
while（i!
=0）
{
while（i>6||i<0）
{
printf（"\nYouchoiceisillegalpleaseinputagain:
\n"）;
printf（"1.display2.preOrder3.inOrder4.postOrder5.leaves6.freenodes0toexit:
"）;
scanf（"%d",&i）;
}
while（i!
=0）
{
while（i>6||i<0）
{
printf（"\nYouchoiceisillegalpleaseinputagain:
\n"）;
printf（"1.display2.preOrder3.inOrder4.postOrder5.leaves6.freenodes0toexit:
"）;
scanf（"%d",&i）;
}
while（i!
=6）
{
while（i>6||i<0）
{
printf（"\nYouchoiceisillegalpleaseinputagain:
\n"）;
printf（"1.display2.preOrder3.inOrder4.postOrder5.leaves6.freenodes0toexit:
"）;
scanf（"%d",&i）;
}
switch（i）
{
case0:
printf（"\nDealingwiththelastjob,tofreeallnodes...\n"）;
freeAllNodes（*pbtree）;
printf（"Allnodehavebeenfreedsuccessfully\n"）;
exit
（1）;
getch（）;
case1:
printf（"\nDisplaybinatree:
\n"）;
outputTree（*pbtree,totalSpace）;
break;
case2:
printf（"\nDatainpreOrder:
\n"）;
preOrder（*pbtree）;
printf（"\n\n"）;
break;
case3:
printf（"\nDataininOrder:
\n"）;
inOrder（*pbtree）;
printf（"\n\n"）;
break;
case4:
printf（"\nDatainpostOrder:
\n"）;
postOrder（*pbtree）;
printf（"\n\n"）;
break;
case5:
printf（"\nLeaves:
\n"）;
leaves（*pbtree）;
printf（"\n\n"）;
}
printf（"Pleasechoosethemodeyouwanttooperatewiththebinatree:
\n"）;
printf（"1.display2.preOrder3.inOrder4.postOrder5.leaves6.freenodes0toexit:
"）;
scanf（"%d",&i）;
}
if（i==6）
{
printf（"\nFreeallnodes:
\n"）;
freeAllNodes（*pbtree）;
printf（"Allnodehavebeenfreedsuccessfully."）;
}
printf（"\n\nNowcreatinganewbinatree...\n"）;
printf（"Pleaseinputchartothebinatree,@toexitcurrentnode:
\n"）;
pbtree=Create_BinTreeRoot（）;
printf（"Displaythebinatreedatadirectly:
\n"）;
outputTree（*pbtree,totalSpace）;
printf（"Pleasechoosethemodeyouwanttooperatewiththebinatree:
\n"）;
printf（"1.display2.preOrder3.inOrder4.postOrder5.leaves6.freenodes0toexit:
"）;
scanf（"%d",&i）;
}
}
printf（"\nDealingwiththelastjob,tofreeallnodes\n"）;
freeAllNodes（*pbtree）;
printf（"Allnodehavebeenfreedsuccessfully\n"）;
getch（）;
return0;
}
七．图形界面
根据提示一步步进行操作。
升级会员 