北理工数据结构实验3Word文件下载.docx
- 文档编号:8137978
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:15
- 大小:118.44KB
北理工数据结构实验3Word文件下载.docx
《北理工数据结构实验3Word文件下载.docx》由会员分享,可在线阅读,更多相关《北理工数据结构实验3Word文件下载.docx(15页珍藏版)》请在冰点文库上搜索。
数据关系R:
若D=Φ,则R=Φ,称BinaryTree为空二叉树;
若D≠Φ,则R={H},H是如下二元关系;
(1)在D中存在惟一的称为根的数据元素root,它在关系H下无前驱;
(2)若D-{root}≠Φ,则存在D-{root}={D1,Dr},且D1∩Dr=Φ;
(3)若D1≠Φ,则D1中存在惟一的元素x1,<
root,x1>
∈H,且存在D1上的关系H1⊆H;
若Dr≠Φ,则Dr中存在惟一的元素xr,<
root,xr>
∈H,且存在上的关系Hr⊆H;
H={<
<
H1,Hr};
(4)(D1,{H1})是一棵符合本定义的二叉树,称为根的左子树;
(Dr,{Hr})是一棵符合本定义的二叉树,称为根的右子树。
基本操作:
CreateTree(&
T)
操作结果:
按先序次序建立二叉链表表示的二叉树TPreOrderTraverse(T,Visit())
初始条件:
二叉树T已经存在,visit是对结点操作的应用函数
操作结果:
先序遍历二叉树T,对每个结点调用visit函数仅一次;
一旦visit()失败,则操作失败。
InOrderTraverse(T,Visit())
中序遍历二叉树T,对每个结点调用visit函数仅一次;
PostOrderTraverse(T,Visit)())
后序遍历二叉树T,对每个结点调用visit函数仅一次;
LevelOrderTraverse(
T,
Visit()
)
初始条件:
二叉树T存在,Visit是对结点操作的应用函数。
操作结果:
层次遍历T,对每个结点调用函数Visit一次且仅一次。
一
旦Visit()失败,则操作失败。
}ADTBinaryTree
(2)、宏定义
#define
ok
1
error
(3)主程序流程
主程序先调用CreateTree(BiTree&
T)函数,根据输入的先序序列构造出一棵二叉树,再依次调用PreOrderTraverse(BiTreeT,int(*visit)(chare)),InOrderTraverse(BiTreeT,int(*visit)(chare)),PostOrderTraverse(BiTreeT,int(*visit)(chare))函数,对该二叉树进行先序、中序、后序遍历并输出结果。
(4)模块调用关系
由主函数调用创建模块,再调用计算模块,由计算模块将结果输出。
(5)流程图
下面为先序遍历的流程图,中序遍历与后续遍历类似
2、详细设计
⑴数据类型设计
/*二叉链表的结点*/
typedefstructBiTNode
{
chardata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
/*队列*/
typedefBiTreeQElemType;
//定义队列元素类型
typedefstructQNode
QElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
//定义队列结点
typedefstruct
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
//定义队列数据类型
⑵操作算法设计
/*创建队列*/
intInitQueue(LinkQueue&
Q)
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!
Q.front)exit
(1);
//存储分配失败
Q.front->
next=NULL;
returnok;
}
/*插入元素e作为新的队尾元素*/
intEnQueue(LinkQueue&
Q,QElemTypee)
QNode*p=(QueuePtr)malloc(sizeof(QNode));
p)exit
(1);
p->
data=e;
Q.rear->
next=p;
Q.rear=p;
/*删除队头元素并以e返回*/
intDeQueue(LinkQueue&
Q,QElemType&
e)
if(Q.front==Q.rear)returnerror;
QNode*p=Q.front->
next;
e=p->
data;
next=p->
if(Q.rear==p)Q.rear=Q.front;
free(p);
/*建立二叉树*/
intCreateTree(BiTree&
T)
c=getchar();
if(c=='
*'
)T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
T){printf("
ERROE\n"
);
exit
(1);
T->
data=c;
CreateTree(T->
lchild);
//递归建立左子树
rchild);
//递归建立右子树
}
intVisit(chare)
{printf("
%c"
e);
/*先序遍历二叉树*/
intPreOrderTraverse(BiTreeT,int(*Visit)(charc))
if(T)
Visit(T->
data);
PreOrderTraverse(T->
lchild,Visit);
//先序遍历左子树
rchild,Visit);
//先序遍历右子树
}
}
/*中序遍历二叉树*/
intInOrderTraverse(BiTreeT,int(*Visit)(charc))
InOrderTraverse(T->
//中序遍历左子树
//中序遍历右子树
/*后序遍历二叉树*/
intPostOrderTraverse(BiTreeT,int(*Visit)(charc))
PostOrderTraverse(T->
//后序遍历左子树
//后序遍历右子树
/*层次遍历二叉树*/
intLevelOrderTraverse(BiTree&
QElemTypep;
LinkQueueq;
InitQueue(q);
if(T)EnQueue(q,T);
//队头元素进队列
while(!
(q.front==q.rear))
{DeQueue(q,p);
printf("
p->
//输出队头元素
if(p->
lchild)EnQueue(q,p->
//左子树进队列
rchild)EnQueue(q,p->
//右子树进队列
}⑶主函数设计
intmain()
BiTreeT;
输入二叉树的扩展的前序序列\n"
CreateTree(T);
二叉树的先序序列:
"
PreOrderTraverse(T,Visit);
\n"
二叉树的中序序列:
InOrderTraverse(T,Visit);
二叉树的后序序列:
PostOrderTraverse(T,Visit);
二叉树的层次遍历序列:
LevelOrderTraverse(T);
四、程序调试分析
(1)在编写的过程中对于visit的使用一直不太明白,开始我认为参数应该是一个函数的指针所以如下定义了一个函数指针的的变量
结果编译通不过报错,说函数指针Visit没有类型
后来经过不断地尝试终于弄对了,函数指针的定义和使用应该如下所示
最后我去交流,老师说其实不用非得用函数指针去做,函数的名本身也代表着函数的入口地址,也是一个指针变量,如下就可以
虽然在这次的过程中浪费了不少的时间自己转了一个大圈子,但对于一直不太明白的指针变量这次有了一个比较准确的把握,同时也学会了指针变量的具体使用还是很有收获的
(2)在完成了对于visit的正确使用时,遇到了新的问题,如下所示
感觉程序没有什么问题,老师看了也说没什么问题,问题的解决还要依赖于对于报错的提示,如上,提示说函数PreOrderTraverse()的参数不应该只有一个应该有两个,而程序上方很明显有两个参数,说明是书写有问题,在仔细一看原来是参数间的“,”写的是中文的所以当成了一个参数,这种虽然看起来是不起眼的小问题,但同时也是最难发现的,因为表面上看是没有错误的,真是花蕾大量的时间看才发现的,同时也给了我一个很重要的提示,参数少的时候要看看字符的问题,做程序一定要谨慎。
改成如下正确。
五、用户使用说明
1、本程序的运行环境为DOS操作系统
2、进入程序后,在"
输入二叉树的扩展的前序序列"
后按照拓展的前序序列(即
空子树处输入*)输入二叉树,回车后程序即运行。
3、程序运行后即在屏幕上输出计算结果。
六、程序运行结果
测试一:
书上127页的二叉树
测试二:
书上133页的二叉树
七、程序清单
#include"
stdio.h"
stdlib.h"
#defineok1
#defineerror0
/*二叉链表的结点*/
charc;
//输入的字符
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北理工 数据结构 实验