二叉树的生成和遍历.docx
- 文档编号:12999536
- 上传时间:2023-06-10
- 格式:DOCX
- 页数:18
- 大小:257.52KB
二叉树的生成和遍历.docx
《二叉树的生成和遍历.docx》由会员分享,可在线阅读,更多相关《二叉树的生成和遍历.docx(18页珍藏版)》请在冰点文库上搜索。
二叉树的生成和遍历
《数据结构》
课程设计报告
———二叉树的生成和遍历
专业信息管理与信息系统
班级
小组成员汤文莹
王玉珏
张蓓蕾
张慕琦
课程设计:
二叉树的生成和遍历
一、任务描述
1.将二叉树以广义表形式存储在一个TXT文件上,通过读取TXT文件,建立二叉树;
2.求树的高度
3.实现二叉树的前序、中序和后序遍历;
4.将输出结果存储在文件内。
二、问题分析
1.设计思想
以广义表格式输入一个二叉树,将其接收至一维数组中,利用栈结构建立二叉链表树;通过先、中、后访问根结点递归算法遍历二叉树;利用队列的入队、出队操作实现二叉树的层次遍历。
例如:
a(c(,d),f(g,))建立如下图所示二叉树。
2.数据结构
定义队列数组长度
#defineQueueMaxSize20
定义栈数组长度
#defineStackMaxSize10
定义二叉树数据类型
typedefcharElemType;
structBTreeNode{
ElemTypedata;
structBTreeNode*left;
structBTreeNode*right;
}BTreeNode;
3.主要模块设计
初始化二叉树
voidInitBTree(structBTreeNode**BT)
根据a所定义的二叉树广义表字符串建立对应的存储结构
voidCreateBTree(structBTreeNode**BT,char*a)
前序遍历二叉树
voidPreorder(structBTreeNode*BT)
{
if(BT!
=NULL){
printf("%c",BT->data);/*访问根结点*/
Preorder(BT->left);/*前序遍历左子树*/
Preorder(BT->right);/*前序遍历右子树*/
}
}
中序遍历二叉树
voidInorder(structBTreeNode*BT)
{
if(BT!
=NULL){
Inorder(BT->left);/*中序遍历左子树*/
printf("%c",BT->data);/*访问根结点*/
Inorder(BT->right);/*中序遍历右子树*/
}
}
后序遍历二叉树
voidPostorder(structBTreeNode*BT)
{
if(BT!
=NULL){
Postorder(BT->left);/*后序遍历左子树*/
Postorder(BT->right);/*后序遍历右子树*/
printf("%c",BT->data);/*访问根结点*/
}
}
由指针指向的一颗二叉树的深度
intBTreeDepth(structBTreeNode*BT)
按层遍历由BT指针所指向的二叉树
voidLevelorder(structBTreeNode*BT
4.详细设计
1)二叉树的建立
其中mark的值1、2、3、4分别指str[i]为字母、‘(’、‘,’、‘)’;
tag为左、右孩子的标志;
2.二叉树的层次遍历
访问元素所指结点,若该元素所指结点的左右孩子结点非空,则该元素所指结点的左孩子指针和右孩子指针顺序入队。
函数实现
#include
#include
#defineQueueMaxSize20/*定义队列数组长度*/
#defineStackMaxSize10/*定义栈数组长度*/
typedefcharElemType;
structBTreeNode{
ElemTypedata;
structBTreeNode*left;
structBTreeNode*right;
}BTreeNode;
voidInitBTree(structBTreeNode**BT)
/*初始化二叉树,即把树根指针置空*/
{
*BT=NULL;
}
voidCreateBTree(structBTreeNode**BT,char*a)/*根据a所定义的二叉树广义表字符串建立对应的存储结构*/
{
structBTreeNode*p;
/*定义s数组作为存储根结点指针的栈使用*/
structBTreeNode*s[StackMaxSize];
/*定义top作为s栈的栈顶指针,初值为-1,表示空栈*/
inttop=-1;
/*用k作为处理结点的左子树和右子树的标记,k=1处理左子树,k=2处理右子树*/
intk;
/*用i扫描数组a中存储的二叉树广义表字符串,初值为0*/
inti=0;
/*把树根指针置为空,即从空树开始建立二叉树*/
*BT=NULL;
/*每循环一次处理一个字符,直到扫描到字符串结束\0为止*/
while(a[i])
{
switch(a[i])
{
case'':
/*对空格不做任何处理*/
break;
case'(':
if(top==StackMaxSize-1)
{
printf("栈空间太小,需增加StackMaxSize!
\n");
exit
(1);
}
top++;
s[top]=p;
k=1;
break;
case')':
if(top==-1)
{
printf("二叉树广义表字符串错!
\n");
exit
(1);
}
top--;
break;
case',':
k=2;
break;
default:
p=(structBTreeNode*)malloc(sizeof(structBTreeNode));
p->data=a[i];
p->left=p->right=NULL;
if(*BT==NULL)
*BT=p;
else
{
if(k==1)
s[top]->left=p;
else
s[top]->right=p;
}
}/*switchend*/
/*为扫描下一个字符串修改i值*/
i++;
}
}
voidPrintBTree(structBTreeNode*BT)
/*输出二叉数的广义表表示*/
{
/*数为空时自然结束递归,否则执行如下操作*/
if(BT==NULL)
{
/*输出根结点的值*/
printf("%c",BT->data);
/*输出左、右子树*/
if(BT->left!
=NULL||BT->right!
=NULL)
{
printf("(");/*输出左括号*/
PrintBTree(BT->left);/*输出左子树*/
if(BT->right!
=NULL)
PrintBTree(BT->right);/*输出右子树*/
printf(")");/*输出右括号*/
}
}
}
voidPreorder(structBTreeNode*BT)
{
if(BT!
=NULL){
printf("%c",BT->data);/*访问根结点*/
Preorder(BT->left);/*前序遍历左子树*/
Preorder(BT->right);/*前序遍历右子树*/
}
}
voidInorder(structBTreeNode*BT)
{
if(BT!
=NULL){
Inorder(BT->left);/*中序遍历左子树*/
printf("%c",BT->data);/*访问根结点*/
Inorder(BT->right);/*中序遍历右子树*/
}
}
voidPostorder(structBTreeNode*BT)
{
if(BT!
=NULL){
Postorder(BT->left);/*后序遍历左子树*/
Postorder(BT->right);/*后序遍历右子树*/
printf("%c",BT->data);/*访问根结点*/
}
}
voidLevelorder(structBTreeNode*BT)/*按层遍历由BT指针所指向的二叉树*/
{
structBTreeNode*p;
/*定义队列所使用的数组空间,元素类型为指向结点的指针类型*/
structBTreeNode*q[QueueMaxSize];
/*定义队首指针和队尾指针,初始均置0表示空队*/
intfront=0,rear=0;
/*将树根指针进队*/
if(BT!
=NULL){
rear=(rear+1)%QueueMaxSize;
q[rear]=BT;
}
/*当队列非空时执行循环*/
while(front!
=rear){
/*使队首指针指向队首元素*/
front=(front+1)%QueueMaxSize;
/*删除队首元素,输出队首元素所指结点的值*/
p=q[front];
printf("%c",p->data);
/*若结点存在左孩子,则左孩子指针结点进队*/
if(p->left!
=NULL)
{
rear=(rear+1)%QueueMaxSize;
q[rear]=p->left;
}
/*若结点存在右孩子,则右孩子指针结点进队*/
if(p->right!
=NULL)
{
rear=(rear+1)%QueueMaxSize;
q[rear]=p->right;
}
}
}
intBTreeDepth(structBTreeNode*BT)/*求由指针指向的一颗二叉树的深度*/
{
if(BT==NULL)
return0;/*对于空树,返回0并结束递归*/
else
{/*计算左子树的深度*/
intdep1=BTreeDepth(BT->left);
/*计算右子树的深度*/
intdep2=BTreeDepth(BT->right);
/*返回树的深度*/
if(dep1>dep2)
returndep1+1;
else
returndep2+1;
}
}
voidmenu()//窗体显示菜单
{
printf("\n====>请在下列序号中选择一个并输入:
\n");
printf("
(1)---重新输入二叉树\n");
printf("
(2)---前序遍历二叉树\n");
printf("(3)---中序遍历二叉树\n");
printf("(4)---后序遍历二叉树\n");
printf("(5)---广度优先遍历二叉树\n");
printf("(6)---显示二叉树深度\n");
printf("(0)---退出\n");
}
voidWrong()//错误提示
{
printf("\n=====>按键错误!
\n");
getchar();//保留错误信息的显示
}
voidmain()
{
/*定义指向二叉树节点的操作,并用指针作为树根指针*/
structBTreeNode*bt;
/*定义一个用于存放二叉树广义表的字符数组*/
charb[50];
/*定义ElemType类型的对象X和指针对象px*/
ElemTypex,*px;
/*初始化二叉树,即置树根bt为空*/
InitBTree(&bt);
/*从键盘向字符数组b输入二叉树广义表标识的字符串*/
printf("输入二叉树广义表字符串:
\n");
printf("输入格式为:
a(c(m,d(s,z)),e(t(h,k),b(i))\n");
scanf("%s",b);
/*建立以bt作为树根指针的二叉树的链接存储结构*/
CreateBTree(&bt,b);
menu();
while(10)//界面的显示实现
{
intp;
scanf("%d",&p);
switch(p)
{
case0:
printf("===>谢谢使用!
\n");
getchar();
break;
case1:
printf("请重新输入二叉树广义表字符串:
\n");
printf("输入格式为:
a(c(m,d(s,z)),e(t(h,k),b(i))\n");
scanf("%s",b);
/*建立以bt作为树根指针的二叉树的链接存储结构*/
CreateBTree(&bt,b);
printf("\n");
getchar();
break;
case2:
/*以广义表形式输入二叉树*/
PrintBTree(bt);
printf("\n");
/*前序遍历以bt为树根指针的二叉树*/
printf("前序:
");
Preorder(bt);
printf("\n");
getchar();
break;
case3:
/*以广义表形式输入二叉树*/
PrintBTree(bt);
printf("\n");
/*中序遍历以bt为树根指针的二叉树*/
printf("中序:
");
Inorder(bt);
printf("\n");
getchar();
break;
case4:
/*以广义表形式输入二叉树*/
PrintBTree(bt);
printf("\n");
/*后序遍历以bt为树根指针的二叉树*/
printf("后序:
");
Postorder(bt);
printf("\n");
getchar();
break;
case5:
/*以广义表形式输入二叉树*/
PrintBTree(bt);
printf("\n");
/*接层遍历以bt为树根指针的二叉树*/
printf("广度优先:
");
Levelorder(bt);
printf("\n");
getchar();
break;
case6:
/*以广义表形式输入二叉树*/
PrintBTree(bt);
printf("\n");
/*求出以bt为树根指针的二叉树的深度*/
printf("二叉树的深度:
");
printf("%d\n",BTreeDepth(bt));
getchar();
break;
default:
Wrong();
printf("\n请按任意键继续...");
getchar();
break;
}
}
}
3、运行结果
四、设计总结
二叉树是数据结构的的基本内容。
虽然程序规模不大,经过查找资料,参考网上以及课本上的实例,仍免不了各种错误的出现。
编程过程需要很大的毅力和耐心,而且要有良好的思维和扎实的专业基础知识,所以我们需要不断的学习,发现自身不足之处并改正它,逐步提高自己。
程序设计让我们懂了许课程设计究竟是什么意思了,要用我们的双手编写出一个个程序来为他人带来方便。
其中也遇到了现实中的一些问题,比如说,数据量很的问题,这在程序的各种算法上提出了很严的要求,数据量大就需要的时间就多,相应的效率问题也很重要。
在银行、通信、军事上如果一个程序在运算大量数据上能提高一点效率那么它就能节省许多的时间和金钱。
这也就是一个创造吧。
在以后的程序设计中都应该好好思考这个问题。
有一高效率才是最好程序。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 生成 遍历