完整word版树形数据结构及其应用word文档良心出品.docx
- 文档编号:9534768
- 上传时间:2023-05-19
- 格式:DOCX
- 页数:19
- 大小:183.40KB
完整word版树形数据结构及其应用word文档良心出品.docx
《完整word版树形数据结构及其应用word文档良心出品.docx》由会员分享,可在线阅读,更多相关《完整word版树形数据结构及其应用word文档良心出品.docx(19页珍藏版)》请在冰点文库上搜索。
完整word版树形数据结构及其应用word文档良心出品
淮海工学院计算机工程学院
实验报告书
课程名:
《数据结构》
题目:
树形数据结构及其应用
班级:
学号:
姓名:
实验2树形数据结构
实验目的和要求
1.熟练掌握二叉树的二叉链表存储结构;二叉树的常用遍历方法:
按层遍历、先序递归遍历、中序递归和非递归遍历、后序递归遍历。
2.掌握按先序遍历顺序输入数据,递归建立二叉树的方法。
3.掌握建立哈夫曼树的方法,实现哈夫曼编码。
实验环境
TurboC或VC++
实验学时
4学时,必做实验
实验题目
1.[问题描述]建立一棵用二叉链表方式存储的二叉树,并对其进行遍历(先序、中序和后序),打印输出遍历结果。
[基本要求]从键盘接受输入先序序列,以二叉链表作为存储结构,建立二叉树(以先序来建立)并对其进行遍历(先序、中序、后序),然后将遍历结果打印输出。
要求采用递归和非递归两种方法实现。
[测试数据]ABCффDEфGффFффф(其中ф表示空格字符)
输出结果为:
先序:
ABCDEGF
中序:
CBEGDFA
后序:
CGBFDBA
2.已知二叉树按照二叉链表方式存储,编写算法,要求实现二叉树的竖向显示(竖向显示就是二叉树的按层显示)。
[提示]:
(1)参习题6.20,实现逐层遍历
(2)队中保存每个结点的打印位置,其左、右子的距离
3.如题1要求建立好二叉树,按凹入表形式打印二叉树结构,如图6.34所示。
A
BC
DE
图6.34
F
主要数据结构
1.
typedefcharDataType;
typedefstructNode
{
DataTypedata;
structNode*LChild;
structNode*RChild;
}BiTNode,*BiTree;
2.
ypedefBiTreeQueueElementType;
typedefstruct
{
QueueElementTypeelement[MAXSIZE];/*队列的元素空间*/
intfront;/*头指针指示器*/
intrear;/*尾指针指示器*/
}SeqQueue;
3.voidInitQueue(SeqQueue*Q)/*初始化操作*/
4.intEnterQueue(SeqQueue*Q,QueueElementTypex)/*入队操作*/
5.intDeleteQueue(SeqQueue*Q,QueueElementType*x)/*出队操作*/
6.intLayerOrder(BiTreebt)
7.InitQueue(Q);/*初始化空队列Q*/
8.voidCreateBiTree(BiTree*bt)
9.voidPreOrder(BiTreeroot)//先序遍历二叉树
10.voidInOrder(BiTreeroot)//中序遍历二叉树
11.voidPostOrder(BiTreeroot)//后序遍历二叉树
12.intCreateBiTree(BiTree&T)//创建一棵非空二叉树
13.voidPrintTree(BiTreeBoot,intnLayer)/*打印二叉树*/
主要算法
1.用递归和非递归进行遍历(先序、中序、后序)
2.按图进行遍历
3.用队列编写二叉链表存储:
初始化、入队、出队
运行结果
1.递归
非递归
2.
3.
实验体会
1.代码可能有点冗长,对后序线索二叉树求后继节点实现的不是很好。
2.这次任务量有点大,实现的函数太多,全部放在一个文件里不利于维护与修改。
附源代码
1.递归:
#include
#include
#include
typedefcharDataType;
typedefstructNode
{
DataTypedata;
structNode*LChild;
structNode*RChild;
}BiTNode,*BiTree;
voidCreateBiTree(BiTree*bt)
{
charch;
ch=getchar();
if(ch=='')*bt=NULL;
else
{
*bt=(BiTree)malloc(sizeof(BiTNode));
(*bt)->data=ch;
CreateBiTree(&(*bt)->LChild);
CreateBiTree(&(*bt)->RChild);
}
}
voidVisit(charch)
{
printf("%c",ch);
}
voidPreOrder(BiTreeroot)//先序遍历二叉树
{
if(root!
=NULL)
{
Visit(root->data);
PreOrder(root->LChild);
PreOrder(root->RChild);
}
}
voidInOrder(BiTreeroot)//中序遍历二叉树
{
if(root!
=NULL)
{
InOrder(root->LChild);
Visit(root->data);
InOrder(root->RChild);
}
}
voidPostOrder(BiTreeroot)//后序遍历二叉树
{
if(root!
=NULL)
{
PostOrder(root->LChild);
PostOrder(root->RChild);
Visit(root->data);
}
}
voidmain()
{
BiTreeT;
CreateBiTree(&T);
printf("先序遍历序列为:
");
PreOrder(T);
printf("\n中序遍历序列为:
");
InOrder(T);
printf("\n后序遍历序列为:
");
PostOrder(T);
getch();
}
非递归:
#include
usingnamespacestd;
#defineOK1
#defineERROR0
#defineOVERFLOW-2
typedefint
SElemType;
typedefstructNode
{
chardata;
structNode*LChild;
structNode*RChild;
}BiTNode,*BiTree;
typedefstruct
{
BiTNode*a[100];
inttop;
}Sqstack;
voidpush(Sqstack*s,BiTNode*x)
{
if(s->top==100)
cout<<"stackoverflow!
"< else { s->top++; s->a[s->top]=x; } } BiTNode*pop(Sqstack*s,BiTNode*x) { if(s->top==0) { cout<<"stackunderflow! "< return(NULL); } else { x=s->a[s->top]; s->top--; return(x); } } intCreateBiTree(BiTree&T)//创建一棵非空二叉树 { charch; cin>>ch; if(ch=='.')T=NULL; else { if(! (T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data=ch; CreateBiTree(T->LChild); CreateBiTree(T->RChild); }returnOK; } voidPreorder(BiTreeT)//先序递归操作遍历二叉树 { if(T) { cout< Preorder(T->LChild); Preorder(T->RChild); } } voidInorder(BiTreeT)//中序非递归操作遍历二叉树 { Sqstacks; BiTNode*p; s.top=0; push(&s,T); while(s.top! =0) { while(s.a[s.top]! =NULL) { p=s.a[s.top]; push(&s,p->LChild); } p=pop(&s,T); if(s.top! =0) { p=pop(&s,T); cout< push(&s,p->RChild); } } } voidPostorder(BiTreeT)//后序非递归操作遍历二叉树 { if(T) { Postorder(T->LChild); Postorder(T->RChild); cout< } } voidmain() { BiTreeT; cout<<"输入要创建树的顺序: "; CreateBiTree(T); cout<<"先序遍历的结果: "; Preorder(T); cout<<"\n"; cout<<"中序遍历的结果: "; Inorder(T); cout<<"\n"; cout<<"后序遍历的结果: "; Postorder(T); cout<<"\n"; } 2.typedefstructNode { DataTypedata; structNode*LChild; structNode*RChild; }BiTNode,*BiTree; 按照右根左方式遍历 孩子兄弟表示树,然后先根遍历。 #include"stdio.h" #include #include #defineTRUE1 #defineFALSE0 #defineERROR0 #defineOK1 #defineMAXSIZE50/*队列的最大长度*/ TypedefcharDataTpye typedefstructNode { DataTypedata; structNode*LChild; structNode*RChild; }BiTNode,*BiTree; typedefBiTreeQueueElementType; typedefstruct { QueueElementTypeelement[MAXSIZE];/*队列的元素空间*/ intfront;/*头指针指示器*/ intrear;/*尾指针指示器*/ }SeqQueue; /*初始化操作*/ voidInitQueue(SeqQueue*Q) { /*将*Q初始化为一个空的循环队列*/ Q->front=Q->rear=0; } /*入队操作*/ intEnterQueue(SeqQueue*Q,QueueElementTypex) { /*将元素x入队*/ if((Q->rear+1)%MAXSIZE==Q->front)/*队列已经满了*/ return(FALSE); Q->element[Q->rear]=x; Q->rear=(Q->rear+1)%MAXSIZE;/*重新设置队尾指针*/ return(TRUE);/*操作成功*/ } /*出队操作*/ intDeleteQueue(SeqQueue*Q,QueueElementType*x) { /*删除队列的队头元素,用x返回其值*/ if(Q->front==Q->rear)/*队列为空*/ return(FALSE); *x=Q->element[Q->front]; Q->front=(Q->front+1)%MAXSIZE;/*重新设置队头指针*/ return(TRUE);/*操作成功*/ } intIsEmpty(SeqQueue*Q) { /*提取队列的队头元素,用x返回其值*/ if(Q->front==Q->rear)/*队列为空*/ return(TRUE); else return(FALSE);/*操作成功*/ } intLayerOrder(BiTreebt) { SeqQueue*Q; BiTreep; Q=(SeqQueue*)malloc(sizeof(SeqQueue)); //p=(BiTree*)malloc(sizeof(BiTree)); InitQueue(Q);/*初始化空队列Q*/ if(bt==NULL) returnERROR;/*若二叉树bt为空树,则结束遍历*/ EnterQueue(Q,bt);/*若二叉树bt非空,则根结点bt入队,开始层次遍历*/ while(! IsEmpty(Q))/*若队列非空,则遍历为结束,继续进行*/ { DeleteQueue(Q,&p);/*队头元素出队并访问*/ printf("%c",p->data); if(p->LChild) EnterQueue(Q,p->LChild);/*若p的左孩子非空,则进队*/ if(p->RChild) EnterQueue(Q,p->RChild);/*若p的右孩子非空,则进队*/ }/*while*/ returnOK; }/*LayerOrder*/ voidmain() { BiTreeT; printf("按扩展先序遍历序列建立二叉树,请输入序列: \n"); CreateBiTree(&T); printf("层次遍历输出结点为: "); LayerOrder(T); getch(); } 3. #include #include #include typedefcharDataType; typedefstructNode { DataTypedata; structNode*LChild; structNode*RChild; }BiTNode,*BiTree; voidCreateBiTree(BiTree*bt) { charch; ch=getchar(); if(ch=='')*bt=NULL; else { *bt=(BiTree)malloc(sizeof(BiTNode)); (*bt)->data=ch; CreateBiTree(&(*bt)->LChild); CreateBiTree(&(*bt)->RChild); } } voidVisit(charch) { printf("%c",ch); } voidPreOrder(BiTreeroot) { if(root! =NULL) { Visit(root->data); PreOrder(root->LChild); PreOrder(root->RChild); } } voidInOrder(BiTreeroot) { if(root! =NULL) { InOrder(root->LChild); Visit(root->data); InOrder(root->RChild); } } voidPostOrder(BiTreeroot) { if(root! =NULL) { PostOrder(root->LChild); PostOrder(root->RChild); Visit(root->data); } } voidPrintTree(BiTreeBoot,intnLayer) { if(Boot==NULL)return; PrintTree(Boot->RChild,nLayer+1); for(inti=0;i printf(""); printf("%c\n",Boot->data); PrintTree(Boot->LChild,nLayer+1); } voidmain() { BiTreeT; CreateBiTree(&T); printf("先序遍历序列为: "); PreOrder(T); printf("\n中序遍历序列为: "); InOrder(T); printf("\n后序遍历序列为: "); PostOrder(T); printf("\n"); PrintTree(T,0); getch();}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 完整 word 树形 数据结构 及其 应用 文档 良心 出品