二叉树的基本操作实现及其应用.docx
- 文档编号:2078901
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:13
- 大小:64.01KB
二叉树的基本操作实现及其应用.docx
《二叉树的基本操作实现及其应用.docx》由会员分享,可在线阅读,更多相关《二叉树的基本操作实现及其应用.docx(13页珍藏版)》请在冰点文库上搜索。
二叉树的基本操作实现及其应用
目录
一、实验目的1
二、实验内容1
三、实验步骤1
㈠、数据结构与核心算法的设计描述1
㈡、函数调用及主函数设计2
㈢程序调试及运行结果分析3
㈣实验总结3
四、主要算法流程图及程序清单3
1、主要算法流程图:
3
2、程序清单4
实验三二叉树的基本操作实现及其应用
一、实验目的
1.熟悉二叉树结点的结构和对二叉树的基本操作。
2.掌握对二叉树每一种操作的具体实现。
3.学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。
4.会用二叉树解决简单的实际问题。
二、实验内容
题目一设计程序实现二叉树结点的类型定义和对二叉树的基本操作。
该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。
1按先序次序建立一个二叉树,
2按(A:
先序B:
中序C:
后序)遍历输出二叉树的所有结点
以上比做,以下选做
3求二叉树中所有结点数
4求二叉树的深度
三、实验步骤
㈠、数据结构与核心算法的设计描述
1)二叉树结构类型定义:
typedefstructBiTNode
{
chardata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
2)队列节点定义:
typedefstructQNode
{
BiTreebt;
structQNode*next;
}QNode,*QueuePtr;
3)队列类型定义:
structLinkQueue队列类型定义
{
QueuePtrfront;//队头指针
QueuePtrrear;//队尾指针
};
4)初始化二叉树,即把二叉树置空:
voidBiTreeInit(BiTree&T)
5)按先序建立一个二叉树:
StatusCreateBiTree(BiTree&T)
按先序次序输入二叉树中结点值(一个字符),空格字符表示空树。
构造二叉链表表示的二叉树T。
6)StatusPreOrderTraverse(BiTreeT)//先序遍历二叉树
7)StatusInOrderTraverse(BiTreeT)//中序遍历二叉树
8)StatusPostOrderTraverse(BiTreeT)//后序遍历二叉树
9)voidout(BiTreeT)//从左到右,从上到下遍历二叉树
10)voidnodesum(BiTree&T)//二叉树节点总数
11)intDepth(BiTreeT)//返回二叉树的深度
12)voidInitQueue(LinkQueue&Q)//构造一个空队列Q
13)EnQueue(LinkQueue&Q,BiTree&e)//进队
14)DeQueue(LinkQueue&Q,BiTree&e)//出队
15)StatusemptyQueue(LinkQueue&Q)//判断队列是否空
㈡、函数调用及主函数设计
㈢程序调试及运行结果分析
1.先序建立二叉树时,应用getchar()函数,从流中读入字符;
2.上下左右依次遍历二叉树时,判断结束的条件是栈是否空;
3.队列节点的数据域应定义成二叉树型的;
4.求节点总数时,计数n应定义成全局变量。
5.求深度的k也应是全局变量。
㈣实验总结
以前只是学一些零碎的东西,通过做实验,让我们把这些零碎的东西拼接成一个小小的程序。
让我们在做实验时对整体的把握得以提高。
这次实验既培养了自己的动手能力,又加深了对知识的认识,同时使自己有了解决问题的思路和方法。
在这次实验的过程中,我知道了一些如何查找错误的方法,掌握了一些关于如何调试来解决自己的代码编译错的技巧。
自己在以后的学习过程中加强锻炼,多写写,多练练,把书本上的知识应用到实际问题中去,达到所学以用。
通过这次实验,我对二叉树更加了解,还有跟队列的结合,是我对知识有更深的应用。
四、主要算法流程图及程序清单
1、主要算法流程图:
否
否
从上到下,从左到右遍历二叉树图
2、程序清单
#include
#include
#include
#defineStatusint
#defineOVERFLOW1
#defineOK1
#defineERROR0
intn=0,k;
typedefstructBiTNode//二叉树节点定义
{
chardata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
typedefstructQNode//队列节点定义
{
BiTreebt;
structQNode*next;
}QNode,*QueuePtr;
structLinkQueue//队列类型定义
{
QueuePtrfront;//队头指针
QueuePtrrear;//队尾指针
};
voidInitQueue(LinkQueue&Q)//构造一个空队列Q
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!
Q.front)exit(OVERFLOW);//存储空间分配失败
Q.front->next=NULL;
}
StatusemptyQueue(LinkQueue&Q)//判断队列是否空
{
if(Q.front==Q.rear)
return1;
else
return0;
}
voidEnQueue(LinkQueue&Q,BiTree&e)//进队
{
QueuePtrp=(QueuePtr)malloc(sizeof(QNode));
if(!
p)exit(OVERFLOW);
p->bt=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
voidDeQueue(LinkQueue&Q,BiTree&e)//出队
{
if(Q.front==Q.rear)return;
QueuePtrp=Q.front->next;
e=p->bt;
Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
free(p);
}
voidCreateBiTree(BiTree&T)//先序建立二叉树
{
charch;
ch=getchar();
if(ch=='')T=NULL;
else
{
if(!
(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
StatusVisit(chare)
{
cout< returnOK; } StatusPreOrderTraverse(BiTreeT)//先序遍历二叉树 { if(T) { if(Visit(T->data)) if(PreOrderTraverse(T->lchild)) if(PreOrderTraverse(T->rchild)) returnOK; returnERROR; } elsereturnOK; } StatusInOrderTraverse(BiTreeT)//中序遍历二叉树 { if(T) { if(InOrderTraverse(T->lchild)) if(Visit(T->data)) if(InOrderTraverse(T->rchild)) returnOK; returnERROR; } elsereturnOK; } StatusPostOrderTraverse(BiTreeT)//后序遍历二叉树 { if(T) { if(PostOrderTraverse(T->lchild)) if(PostOrderTraverse(T->rchild)) if(Visit(T->data)) returnOK; returnERROR; } elsereturnOK; } voidout(BiTreeT)//从左到右,从上到下遍历二叉树 { LinkQueueQ; InitQueue(Q); EnQueue(Q,T); cout< while(! emptyQueue(Q)) { DeQueue(Q,T); if(T->lchild) { EnQueue(Q,T->lchild); cout< } if(T->rchild) { EnQueue(Q,T->rchild); cout< } } } voidnodesum(BiTree&T)//二叉树节点总数 { if(T) { n++; nodesum(T->lchild); nodesum(T->rchild); } } intDepth(BiTreeT)//返回二叉树的深度 { if(T) { intdepthLeft=Depth(T->lchild); intdepthRight=Depth(T->rchild); k=1+(depthLeft>depthRight? depthLeft: depthRight); } elsek=0; returnk; } voidmain() { cout<<"1.先序建立一个二叉树"< cout<<"2.先序遍历二叉树"< cout<<"3.中序遍历二叉树"< cout<<"4.后序遍历二叉树"< cout<<"5.从上到下,从左到右遍历二叉树"< cout<<"6.二叉树总结点数"< cout<<"7.二叉树深度"< cout<<"其他键退出"< cout<<"请选择你的功能: "< inta; charb; BiTreeT; do { cin>>a; switch(a) { case1: CreateBiTree(T);break; case2: PreOrderTraverse(T);break; case3: InOrderTraverse(T);break; case4: PostOrderTraverse(T);break; case5: out(T);break; case6: nodesum(T);cout< case7: cout< default: exit(0); } cout<<"继续操作请输入Y并选择功能(其他键退出): "< cin>>b; }while(b=='Y'); }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 基本 操作 实现 及其 应用
![提示](https://static.bingdoc.com/images/bang_tan.gif)