大数据结构 二叉树遍历实验报告材料.doc

大数据结构 二叉树遍历实验报告材料.doc

ID:48870627

大小:393.00 KB

页数:21页

时间:2020-02-03

大数据结构 二叉树遍历实验报告材料.doc_第1页
大数据结构 二叉树遍历实验报告材料.doc_第2页
大数据结构 二叉树遍历实验报告材料.doc_第3页
大数据结构 二叉树遍历实验报告材料.doc_第4页
大数据结构 二叉树遍历实验报告材料.doc_第5页
资源描述:

《大数据结构 二叉树遍历实验报告材料.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、实用文档数据结构之二叉树实验报告题目:二叉树的遍历和子树交换指导老师:杨政宇班级:通信1202姓名:徐江学号:0909121127实用文档需求分析1.演示程序分别用多种遍历算法遍历二叉树并把数据输出。2.输入字符序列,递归方式建立二叉树。3.在演示过程序中,用户敲击键盘,输入数据,即可看到数据的输出。4.实现链式存储的二叉树的多种遍历算法。遍历算法包括:a)中序递归遍历算法、前序递归遍历算法【选】b)中序遍历非递归算法c)先序或后序遍历非递归算法d)建立中序线索,并进行中序遍历和反中序遍历5.实现二叉树的按层

2、遍历算法6.设计一个测试用的二叉树并创建对应的内存二叉树,能够测试自己算法的边界(包括树节点数为0、1以及>1的不同情形)。7.测试数据:输入数据:-+a*b-cd-ef概要设计说明:本程序在递归调用中用到了链表,在非递归调用时用到了栈。1.栈的抽象数据类型ADTStack{数据对象:D={ai

3、ai∈char,i=1,2,3……..}数据关系:R={

4、ai-1,ai∈D,i=2,3…..}基本操作:InitStack(&S)操作结果:构造一个空栈StackEmpty(S)初始条件:栈S已存

5、在。操作结果:若S为空栈,则返回OK,否则返回ERROR。Push(&S,e)初始条件:栈S已存在。操作结果:插入元素e为新的栈顶元素。Pop(&S,&e)初始条件:栈S已存在且非空。操作结果:删除S的栈顶元素,并用e返回其值。GetTop(S,&e)初始条件:栈S已存在且非空。操作结果:用e返回S的栈顶元素。}实用文档2.二叉树的抽象数据类型ADTBinaryTree{数据对象D:D是具有相同特性的数据元素的集合。数据关系R:若D=Φ,则R=Φ,称BinaryTree为空二叉树;若D≠Φ,则R={H},H是

6、如下二元关系;(1)在D中存在惟一的称为根的数据元素root,它在关系H下无前驱;(2)若D-{root}≠Φ,则存在D-{root}={D1,Dr},且D1∩Dr=Φ;(3)若D1≠Φ,则D1中存在惟一的元素x1,∈H,且存在D1上的关系H1⊆H;若Dr≠Φ,则Dr中存在惟一的元素xr,∈H,且存在上的关系Hr⊆H;H={,,H1,Hr};(4)(D1,{H1})是一棵符合本定义的二叉树,称为根的左子树;(Dr,{Hr})是一棵符合本定

7、义的二叉树,称为根的右子树。基本操作:CreateBiTree(&T)初始条件:给出二叉树T的定义。操作结果:按要求构造二叉树T。PreOrderTraverse_re(T,print())初始条件:二叉树T存在,print是二叉树全部结点输出的应用函数。操作结果:先序递归遍历T,对每个结点调用函数print一次且仅一次。一旦print()失败,则操作失败。InOrderTraverse(T,print())初始条件:二叉树T存在,print是二叉树全部结点输出的应用函数。操作结果:中序非递归遍历T,对每个结

8、点调用函数print一次且仅一次。一旦printf()失败,则操作失败。InOrderTraverse_re(T,print())初始条件:二叉树T在在,print是二叉树全部结点输出的应用函数。操作结果:中序递归遍历T,对每个结点调用函数print一次且仅一次。一旦printf()失败,则操作失败。PreOrderTraverse(T,print())初始条件:二叉树T存在,print是二叉树全部结点输出的应用函数。操作结果:先序非递归遍历T,对每个结点调用函数print一次且仅一次。一旦print()失败

9、,则操作失败。Levelorder(T)初始条件:二叉树T在在。操作结果:分层遍历二叉树T,并输出。InOrderThreading(Thrt,T);初始条件:二叉树T在在。操作结果:中序遍历二叉树,并将其中序线索化。InOrderTraverse_Thr(T,print);实用文档初始条件:二叉树T在在。操作结果:中序非递归遍历二叉线索树TInThreading(p);初始条件:结点p在在。操作结果:结点p及子树线索化。3.主程序的流程:voidmain(){初始化;提示;执行二叉数ADT函数;}4.本程序

10、包含三个模块1)主程序模块voidmain(){初始化;{接受命令;显示结果;}}2)链表模块。递归调用时实现链表抽象数据类型。3)栈模块。非递归调用时实现栈的抽象数据类型。详细设计1.宏定义及全局变量#defineTElemTypechar#defineSElemTypeBiTree#defineOK1#defineOVERFLOW0#defineERROR0#defineSTACK_INIT_S

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。