数据结构 二叉树遍历实验报告

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

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

2、包括树节点数为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已存在。操作结果：若S为空栈，则返回OK，否则返回ERROR。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S

5、,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。}2.二叉树的抽象数据类型ADTBinaryTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系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，

6、ot,x1>∈H，且存在D1上的关系H1⊆H；若Dr≠Φ，则Dr中存在惟一的元素xr，∈H，且存在上的关系Hr⊆H；H={,,H1,Hr}；（4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。基本操作：CreateBiTree(&T)初始条件：给出二叉树T的定义。操作结果：按要求构造二叉树T。PreOrderTraverse_re(T,print())初始条件：二叉树T存在，print是二叉树全部结点输出的应用函数。操作结果：先序递归遍历T，对每个

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

8、)初始条件：二叉树T存在，print是二叉树全部结点输出的应用函数。操作结果：先序非递归遍历T，对每个结点调用函数print一次且仅一次。一旦print()失败，则操作失败。Levelorder(T)初始条件：二叉树T在在。操作结果：分层遍历二叉树T，并输出。InOrderThreading(Thrt,T);初始条件：二叉树T在在。操作结果：中序遍历二叉树，并将其中序线索化。InOrderTraverse_Thr(T,print);初始条件：二叉树T在在。操作结果：中序非递归遍历二叉线索树TInThreading(p);初始条件：结点p在在。操作结果：结点p及子树线索化。3

9、.主程序的流程：voidmain(){初始化;提示;执行二叉数ADT函数;}4.本程序包含三个模块1）主程序模块voidmain(){初始化；{接受命令；显示结果；｝｝2）链表模块。递归调用时实现链表抽象数据类型。3）栈模块。非递归调用时实现栈的抽象数据类型。详细设计1.宏定义及全局变量#defineTElemTypechar#defineSElemTypeBiTree#defineOK1#defineOVERFLOW0#defineERROR0#defineSTACK_INIT_SIZE100#defineSTA