数据结构二叉树实验报告Word格式文档下载.docx
- 文档编号:6547781
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:17
- 大小:47.75KB
数据结构二叉树实验报告Word格式文档下载.docx
《数据结构二叉树实验报告Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《数据结构二叉树实验报告Word格式文档下载.docx(17页珍藏版)》请在冰点文库上搜索。
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,用字符@为我们结束当前结点左或者右结点的字符,然后递归调用左右子树,此时我们将一棵二叉树全整的创建出来了。
先访问根结点,打印出它里面的信息,然后递归调用左子树和右子树。
先递归调用左子树,打印出里面的信息,在打印出根结点信息,然后递归调用右子树,打印出里面的信息。
先递归调用左子树,打印出里面的内容,然后递归调用右子树,打印出里面的内容,然后是根结点的内容。
7.打印出我们创建的二叉树的树型结构
先递归调用右子树,如果结点不为空的话,空格数加5,如果为空的话,就打印出右子树的内容,然后递归调用左子树。
如果当前结点的左右子树都为空的话,就打印出此结点的信息,如果左子树不为空的话,递归调用左子树,如果右子树不为空的话,递归调用右子树。
如果当前的左子树不为空,则遍历左子树,如果右子树不为空的话,则遍历右子树,如果都不位空的话,分别调用左右子树,如果左右都为空的话,就释放左右结点空间,并将当前结点置为空。
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...
2测试非完全二叉树的情形
ABCD@@@@@
ABCD
DCBA
D
如果我们想结束此次的操作,退出本程序,就可以输入0,程序自动的释放所有的结点空间:
Dealingwiththelastjob,tofreeallnodes
Allnodehavebeenfreedsuccessfully
六、附录:
#include<
stdio.h>
stdlib.h>
conio.h>
#defineNULL0
#defineDataTypechar
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'
Z'
||i=='
@'
)
return1;
elsereturn0;
{PBinTreeNodepbnode;
DataTypei;
printf("
\t"
);
fflush(stdin);
scanf("
%c"
&
i);
while(!
isalphabet(i))
{
Sorry,yourinputcharisnotinalphabet,pleaseinputagain:
"
}
if(i=='
)pbnode=NULL;
else
pbnode=(PBinTreeNode)malloc(sizeof(structBinTreeNode));
if(pbnode==NULL)
Outofspace!
\n"
returnpbnode;
pbnode->
info=i;
llink=Create_BinTree();
rlink=Create_BinTree();
returnpbnode;
{inti;
if(pbnode!
=NULL)
totalSpace+=5;
outputTree(pbnode->
rlink,totalSpace);
for(i=0;
i<
totalSpace;
i++)printf("
"
%c\n"
pbnode->
info);
llink,totalSpace);
voidpreOrder(PBinTreeNodepbnode)
if(pbnode==NULL)return;
%c\t"
preOrder(pbnode->
llink);
rlink);
if(pbnode==NULL)return;
inOrder(pbnode->
if(pbnode==NULL)return;
postOrder(pbnode->
pbnode->
if(pbnode->
llink!
=NULL&
rlink==NULL)
leaves(pbnode->
rlink!
llink==NULL)
=NULL)
llink==NULL&
return;
freeAllNodes(pbnode->
free(pbnode->
pbnode=NULL;
return;
intmain()
inti;
inttotalSpace=0;
Pleaseinputchartothebinatree,@toexitcurrentnode:
pbtree=Create_BinTreeRoot();
outputTree(*pbtree,totalSpace);
%d"
while(i>
6||i<
0)
\nYouchoiceisillegalpleaseinputagain:
while(i!
=0)
while(i>
6||i<
while(i!
=6)
switch(i)
case0:
\nDealingwiththelastjob,tofreeallnodes...\n"
freeAllNodes(*pbtree);
Allnodehavebeenfreedsuccessfully\n"
exit
(1);
getch();
case1:
\nDisplaybinatree:
break;
case2:
\nDatainpreOrder:
preOrder(*pbtree);
\n\n"
case3:
\nDataininOrder:
inOrder(*pbtree);
case4:
\nDatainpostOrder:
postOrder(*pbtree);
case5:
\nLeaves:
leaves(*pbtree);
if(i==6)
\nFreeallnodes:
Allnodehavebeenfreedsuccessfully."
\n\nNowcreatinganewbinatree...\n"
\nDealingwiththelastjob,tofreeallnodes\n"
return0;
七.图形界面
根据提示一步步进行操作。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 二叉树实验报告 二叉 实验 报告