数据结构之二叉树实验报告题目：二叉树得遍历与子树交换指导老师：杨政宇班级：通信１2０２姓名:徐江学号:０9091２1１２７需求分析演示程序分别用多种遍历算法遍历二叉树并把数据输出.输入字符序列,递归方式建立二叉树.3、在演示过程序中，用户敲击键盘，输入数据，即可瞧到数据得输出.4、实现链式存储得二叉树得多种遍历算法。遍历算法包括：中序递归遍历算法、前序递归遍历算法【选】中序遍历非递归算法先序或后序遍历非递归算法建立中序线索,并进行中序遍历与反中序遍历５、实现二叉树得按层遍历算法6、设计一个测试用得二叉树并创建对应得内存二叉树,能够测试自己算法得边界(包括树节点数为０、1以及>１得不同情形）。7、测试数据：输入数据:－＋a＊b—ｃd－ｅf概要设计说明:本程序在递归调用中用到了链表,在非递归调用时用到了栈。栈得抽象数据类型ADTSｔack{数据对象：D=｛ａi|ai∈chaｒ，i=１，2,３……、、}数据关系:R=｛〈ａi－１,ai＞｜ai-1,ai∈D,i＝２，3…、、｝基本操作:InitStａｃk(＆Ｓ）操作结果：构造一个空栈SｔackＥmｐtｙ（S）ﻩ初始条件:栈S已存在.操作结果:若S为空栈,则返回ＯK，否则返回ERROR。Puｓh（＆S，e）ﻫ初始条件:栈S已存在。操作结果:插入元素e为新得栈顶元素。Pop（&Ｓ，&e）ﻩ初始条件:栈S已存在且非空.ﻫﻩ操作结果:删除S得栈顶元素，并用e返回其值。GetTｏｐ（S,＆ｅ)ﻫﻩ初始条件:栈S已存在且非空.ﻩ操作结果:用e返回S得栈顶元素.}２、二叉树得抽象数据类型ＡDTBiｎaryＴｒee｛数据对象D:D就是具有相同特性得数据元素得集合。ﻫﻩ数据关系Ｒ：ﻩﻩ若D=Φ，则R=Φ,称BinａrｙＴrｅe为空二叉树;ﻫﻩﻩ若D≠Φ,则Ｒ={H}，H就是如下二元关系；（1）在D中存在惟一得称为根得数据元素ｒｏot,它在关系H下无前驱;（2)若Ｄ-｛ｒoot｝≠Φ，则存在Ｄ—{ｒooｔ｝＝｛Ｄ1,Ｄr｝，且D1∩Dr=Φ；ﻩﻩ(３）若D1≠Φ，则Ｄ1中存在惟一得元素ｘ１,〈ｒｏot,x１〉∈H，且存在Ｄ1上得ﻩﻩ关系Ｈ1⊆H；若Dｒ≠Φ,则Dr中存在惟一得元素ｘr，＜ｒoot，xr〉∈H，且ﻩﻩ存在上得关系Hr⊆Ｈ;H=｛<rooｔ，x1>,<ｒｏot，ｘr>,H1，Ｈｒ}；ﻫﻩﻩ(4)（D1,｛H1｝)就是一棵符合本定义得二叉树,称为根得左子树;(Dｒ，｛Hr｝)就是一ﻩ棵符合本定义得二叉树,称为根得右子树。基本操作:ﻩＣｒeａteBiTree(＆T)ﻩ初始条件：给出二叉树T得定义。ﻫ操作结果：按要求构造二叉树T。ﻩPｒeOrdｅrTｒaverse_re（T,ｐrｉnｔ(）)初始条件：二叉树Ｔ存在，ｐrint就是二叉树全部结点输出得应用函数。ﻩﻩ操作结果:先序递归遍历T，对每个结点调用函数prｉnt一次且仅一次.一旦ﻩﻩﻩpｒｉnt()失败，则操作失败.InＯrderＴraversｅ（Ｔ,pｒｉnｔ（))ﻩﻩ初始条件:二叉树T存在，pｒint就是二叉树全部结点输出得应用函数。ﻩﻩ操作结果:中序非递归遍历Ｔ，对每个结点调用函数pｒｉnt一次且仅一次。一ﻩﻩ旦ｐriｎtf（）失败,则操作失败。InOrderTraｖersｅ_re（Ｔ，pｒint（））ﻩ初始条件：二叉树Ｔ在在,print就是二叉树全部结点输出得应用函数。操作结果:中序递归遍历T，对每个结点调用函数prｉnt一次且仅一次。一旦ﻩﻩprintf（)失败，则操作失败。PreＯrderTｒavｅrse(T,pｒint（）)初始条件：二叉树T存在，priｎt就是二叉树全部结点输出得应用函数。ﻫ操作结果：先序非递归遍历T，对每个结点调用函数prｉnt一次且仅一次。一ﻩ旦prinｔ()失败，则操作失败.Ｌｅｖelｏrder（T）初始条件：二叉树T在在。操作结果：分层遍历二叉树T，并输出。IｎＯｒｄerTｈreadｉng（Thｒt，T);初始条件：二叉树Ｔ在在.操作结果:中序遍历二叉树，并将其中序线索化。InOｒderTrａverse_Thr（T,print）；初始条件:二叉树T在在.操作结果：中序非递归遍历二叉线索树ＴＩnThrｅaｄing（ｐ）;初始条件：结点ｐ在在。操作结果：结点ｐ及子树线索化。3、主程序得流程：voidmａｉn()｛ﻩ初始化；提示;执行二叉数ADT函数；｝4、本程序包含三个模块主程序模块vｏidｍain（)｛初始化；｛接受命令；显示结果;｝}链表模块.递归调用时实现链表抽象数据类型.栈模块。