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

《数据结构-二叉树遍历实验报告.doc》由会员分享，可在线阅读，更多相关《数据结构-二叉树遍历实验报告.doc（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、数为、1以及得不同情形）。7、测试数据：输入数据:a b d f 概要设计说明:本程序在递归调用中用到了链表,在非递归调用时用到了栈。1. 栈得抽象数据类型ADTSack数据对象：D=i|aicha，i=，2,、数据关系:R= i ,ai ai -1,aiD,i，3、基本操作:InitStk(） 操作结果：构造一个空栈Sackmt（ S ） 初始条件:栈S已存在. 操作结果:若S为空栈,则返回K，否则返回ERROR。 Puh（ S， e） 初始条件:栈S已存在。 操作结果:插入元素e为新得栈顶元素。 Pop（ &，&e） 初始条件:栈S已存在且非空. 操作结果:删除S得栈顶元素，并用e返回其值

3、。 GetT（S, ) 初始条件:栈S已存在且非空. 操作结果:用e返回S得栈顶元素.、二叉树得抽象数据类型DT Biaryee 数据对象D:D就是具有相同特性得数据元素得集合。 数据关系： 若D=，则R=,称Binrre为空二叉树; 若D,则=H，H就是如下二元关系； （1）在D中存在惟一得称为根得数据元素ot,它在关系H下无前驱; （2)若-oot，则存在oo1,r，且D1Dr=； (）若D1，则1中存在惟一得元素,ot,xH，且存在1上得关系1 H；若D,则Dr中存在惟一得元素r，oot，xrH，且 存在上得关系Hr;H=,H1，； (4)（D1,H1)就是一棵符合本定义得二叉树,称为根

4、得左子树;(D，Hr)就是一 棵符合本定义得二叉树,称为根得右子树。 基本操作: eteBiTree(T) 初始条件：给出二叉树T得定义。 操作结果：按要求构造二叉树T。 PeOrdrTaverse_re（ T, rn(） ) 初始条件：二叉树存在，rint就是二叉树全部结点输出得应用函数。 操作结果:先序递归遍历T，对每个结点调用函数prnt一次且仅一次.一旦 pnt()失败，则操作失败. Inrderravers（, pn（) ) 初始条件:二叉树T存在，pint就是二叉树全部结点输出得应用函数。 操作结果:中序非递归遍历，对每个结点调用函数pnt一次且仅一次。一 旦ritf（）失败,则操

5、作失败。InOrderTraers_re（，pint（）初始条件：二叉树在在,print就是二叉树全部结点输出得应用函数。操作结果:中序递归遍历T，对每个结点调用函数prnt一次且仅一次。一旦 printf（)失败，则操作失败。 PrerderTavrse(T,pint（）) 初始条件：二叉树T存在，prit就是二叉树全部结点输出得应用函数。 操作结果：先序非递归遍历T，对每个结点调用函数prnt一次且仅一次。一 旦prin()失败，则操作失败. elrder（T）初始条件：二叉树T在在。操作结果：分层遍历二叉树T，并输出。IerTreadng（Tht，T);初始条件：二叉树在在.操作结果:中

6、序遍历二叉树，并将其中序线索化。InOderTrverse_Thr（ T, print）；初始条件:二叉树T在在.操作结果：中序非递归遍历二叉线索树nThraing（）;初始条件：结点在在。操作结果：结点及子树线索化。3、主程序得流程：void mn()初始化；提示;执行二叉数ADT函数；4、本程序包含三个模块1） 主程序模块vid ain（)初始化；接受命令；显示结果;2） 链表模块.递归调用时实现链表抽象数据类型.3） 栈模块。非递归调用时实现栈得抽象数据类型。详细设计1、宏定义及全局变量define EleTy chardeinEemTyp Bidefin OK 1#define VEF

7、LW 0dene ERROR de STACK_INIT_SIZE 100deinSTAINCEMEN 10SqStac S;BiThTe re;BTe;2、函数定义int rateBTee(BTree&T)；/创建二叉树voiPreOderraverse_re（BiTree T,vod （*prt）（TElype e);/先序递归遍历二叉树vod InOrderTrarse（Biree，nt （prnt）（leType e)）;/中序非递归遍历二叉树void InrerTraesr(BiTee T，int （*rint)（TElemType )） ；/中序递归遍历二叉树oid PeOrder

8、aers(iTre ，n （*pint）（TEleye e)）;/先序非递归遍历二叉树int rit(TElempe ）；/打印元素void InitStac（qtc &S);/栈得初始化void Pop(Sqck &S,SElemTpee)；oidPush(qtacS,SElemype &e)；nt tacEmpty(SqStack S）；int Gto（Sack S，Eemype &e）；vid Leveloder（ree T） ；vo nOrerhreing(Bihrree h，BiThrTreT)；it InOrderTravese_Th(BiThrTree T, it （nt)（TE

9、lemTypee）;void InTradin（BiTrreep）;3、二叉树链表数据结构:ypeefruct BiodeElemTyp da；strutBiTNoe *lc ，*rchild；PoneT LTag , Rg;BiTNoe ,*iTree ， BiThrd , *BThrTre； 基本操作:）构造二叉树Tint CreateiTe(BiTree T)chah；saf（c，ch）;i（ch= ）T=UL；ei（！（T(iTNoe ）maloc（izeo（iTode）)）return EROR；Tdat=ch;if(eateBire（Tchl)）T-Tag=Link;if (reB

10、iTre(Tchld） Tag=Lnk；reurn O；b）先序递归遍历二叉数,并输出全部结点值。vi PrderTraversere（BiTree,int （*print)(TEleType e)if（T）if(rin(Tdaa)） eOderTraers_e（lchild，prit）;Orererse_re（Trchl,pit);retun ;elseretun ；c)中序非递归遍历二叉树T,并输出全部结点值vidIOrderTavers(BiTreT,in (*prn）（TElemTpe e)）Sqtack S;S、bsULL；S、t=NU；SElemTyp p=NULL；itSack（

11、S）;Pu(S,);whle（！StakEmpt()）while(GTp（S,p)&p)Pus（S,pcild)；Pp(S，p）；if（!StakEpty（）)Pop（S，p）；print（pdat)；sh（S,-rcild）；retrn；d）中序递归遍历二叉树T，并输出全部结点值vo InderTrerse_re(BiTre T,it（int）（TEemTypee) if(T) nrderTraverse_r（-child,prin)； r（Tda); nrderTersr（Thil,pi）; e)中序遍历二叉树T，并将其中序线索化,Thr指向头结点 id nOrdeThreding（ihT

12、ree rt,BihrTree ）Tht=（BiTrT)allc(sieof（BiTrNod)）；TrtLTagLink；/建头结点Thrt-RTa=hread；hr-childhr；/右指针回指f（！T)Thrlchld=Trt；elseTtlchil=；pre=Th；Theding();/中序遍历进行中序线索化rechild=Thrt;reRTgThread；/最后一个结点线索化Trrchild=re；i=Thrt;/InrdeTheading)结点p线索化void InThreading(ThTre ) if （p) nTheading（pchld)； / 左子树线索化 if(!-lch

13、ild） / 建前驱线索 T= hea； lchld = pr; if (!prerhil) /建后继线索 reRTg =Thed； rhild = p； pr= p； / 保持pre指向p得前驱 Inheading(pchid）； 右子树线索化 /IThreain)/中序遍历线索化二叉树int IOrerTavere_hr(BiTh T， int（prin)（TleTy e）BiTre p=NU；p=Tlchid;hi（!=T）whe（Lag=Link)pchild；f(！pt（p-ata）rerERR；while(RTag=e prchild！=T）p=prchild；prit（paa）;

14、p=prhid；etrOK；4、栈数据结构：tpde trcSElemTye*b;ElmType to;int tackize；SqSack;基本操作：a）创建一个空栈void IitStack（SStackS)S、ase(ElemTy*）maloc（STCK_INITSIZE*sieo(SlmTpe)）;S、top=S、bae;/初始为空S、tacsiz=SAK_NT_SIZE；un;)栈顶插入元素voi ush(SqSak&S，SleTp )if(S、oS、ase、staksze)S、as（SElemType)raloc（、bae，(SACK_IITSIZE+STACKEMEN)sizeo

15、f(ElemTyp）;S、oS、be+、stacksize;S、staksize+=STAKINCREENT；S、to+=e；c）栈顶删除元素vod p（SStk &，ElemType &e）if（S、top=、bse）etun；e=-、top;return；d)判断栈就是否为空栈int Stackmpy(Stack S）f（、p=S、base)reurnOK；eserturn ROR；）返回S得栈顶元素inteTo（SqStk S，SEemyp ）if(、top=S、ase)reurnERROR；e(S、top1）；reurnOK；、主函数voi ai(）nta；BiTre T；BiTrTr

16、ee Tht；rntf(”*”）；pintf（”* 实验12二叉树得遍历 n”)；printf（”1、实现二叉树得不同遍历算法与二叉树得中序线索化算法 *n)；in（”* a） 中序递归遍历算法; *）;pnt（ b) 先序递归遍历算法; *n)；rf（”* c） 中序遍历得非递归算法; *);printf(”* d) 先序或后序遍历非递归算法之一； *n）;prt（ e） 建立中序线利用线索进行中序遍历与反中序遍历。 n”)；prntf（”* 2、 实现二叉树得按层遍历算法. n）;printf（*n);rntf（n选择操作：nt1、先序与中序遍历算法2、中序线索得中序遍历与反中序遍历算法n

17、t3、按层遍历算法n请选择：”)；canf（,&flag）；swith(flag） ase 1:ntf（前序递归创建二叉树（空格 表示此结点为空)：n”）;etha（）；CreateBTree(T)；prntf(中序递归遍历输出：）;Inrderravere_re（T，ri）；rt(n前序递归遍历输出：”）；reOrrTraerse_re（T,prnt）;printf(中序非递归遍历输出:);InOrerTrvse(T，prnt)；prntf（”n前序非递归遍历输出：”）;reOrderTravere(T，prnt); rint(”n）；ba；case 2：pntf（”前序递归创建二叉树(空格

18、 表示此结点为空)：）；gecar(）;CreaeBTree（T）;rintf(n中序遍历线索化二叉树：”);InrdeTreading（Th ， T）；InOrderTravese_Thr（Thr， prnt);break;case 3:printf(”前序递归创建二叉树（空格表示此结点为空）：)；getchar(）；CratBiTe();printf(”n按层遍历输出:）；Levlorder(T）;rintf(”）;break;default：ru；6. 函数间调用关系mainInOrderTraverse_reCreateBitreePreOrderTraverse_reInOrderT

19、raversePreOrderTraverseInOrderThreadingInOrderTraverse_ThrThreadingStack操作调试分析1、二叉树得分层遍历，开始时想用队列来做,但考虑到比较麻烦,因而改为数组模拟队列,简单易懂，课后可自行尝试用队列来做。. 在线索化二叉树时考虑到如果将两种存储结构分开将导致两个类型得指针不能互相传值,造成许多麻烦。比较两种存储结构发现，线索二叉树比二叉树多了两个标志域La,Rta。于就是把两种存储结构合并为iThrNode，并在建立二叉树时把LTag,Rtg均置为Li。程序正常运行。、进入演示程序BTree、pp，完成编译,连接（即按下Ct

20、l F5)进入演示界面,或直接打开执行文件BiTre、ee，产生如下图所示得界面： 用户需根据用户提示信息操作，输入二叉树（以空格表示空结点)，输入完成后按回车键,屏幕上打印出对应于该二叉树得各种遍历结果.如下图:六、 测试结果输入:+a * -c de f 屏幕输出：中序递归遍历输出:ab*cd前序递归遍历输出：+a-d中序非递归遍历输出:abcd前序非递归遍历输出:+b-按层遍历输出:+b-cd中序遍历线索化二叉树:a+bcd七、 附录Bire、cBiTree、xeicldsto、hincludestdlib、hdeneQEmType BiNoeefin TElemTe chardefne

21、 OK1#defi VERFO 0defin RRO 0defne STACK_II_SE 100dfne STCKINCREMNT 0typeef enum PointeragLik,Thread；/Lnk=，指针，Thread=1,线索tyeeftut BiTNodeTElemTyedata;structBiTNode chid ，rchld；PointerTgLTa， Rg；BiNode, ir ， iThrNode , iThre;/二叉树efe lTeTdedefine SElemType iTeeypedefstructlemType base;lemType top;inttcs

22、iz;SqSack;/全局变量SqSack S;iThrTee pre;BihrTree i；/函数声明*/ nt CreateBiree（BiTe &T）;/创建二叉树void PreOrerTrver_re(BiTreeT，oid （print)(TEmye e);/先序递归遍历二叉树voidnOrderravrse(BiTre T，in（pnt）（TElmype e);/中序非递归遍历二叉树void nrderTavrs_re(Bie T,nt(print)(TElmType ） ；/中序递归遍历二叉树oid PeOeavese(BiTre T,it (*prit）（TElemTpe e

23、）)；/先序非递归遍历二叉树nt pn（TlemTye);/打印元素vidnitStac（SStk )；/栈得初始化vodPop（Sqtack &S，SEleType &e)；void Push(qtac S,SElemTyp e);i SckEpty(Sqtck S）;ntGetTop（Stck S，Semyp e)；idLvlorer(BiTree T） ；voi nOreTheadin（BThrTree Th，BhrrT）;intInOrdrTravere_(BThTree ,in （prit）（TElemType e）);void nreadi（TrTrep)；/二叉树得创建递归创建/

24、intCeteBTree（BTee )r ch；canf（%c”，ch)；i（c=）T=NLL；elsi（!(T=（BiTNode *）malc(sizef(iNode)）)）returROR；-data=c；if （CraeBie(lchild）) TLTa=Link;if (CeaiTree(rcil） T-a=Link；retun ； /*/ /* 先序递归遍历输出 /*odPreOrderTravse_r(BiTree,int（print)(TElemTyee）if（T)if(pint（T-dt) reOrdeTvesere(T-child，rin)；PrOdeTravese_re(T

25、-chl，pin)；reur ；elerturn ；*/ 中序非递归遍历输出 / /*/void InrderTraerse（BiTree T,in （*prin）(TElmT e）)SqStack S;、baseUL;、o=ULL；SElemTy p=NUL；Initack（)；Push（S,）；whie（!StackEmpty（S）)l（GetTop（S，p)&p）ush（S，p-lchi);Pp（S，p）；if（!Stapt（S)Po（S，p);pit（a)；Pus（S，cld）；rurn；/*/ /* 中序递归遍历输出 / */void InOrderTrves_re（BiTee，in

26、t (*print）(TElemTye e） if（T） InOrderTraverse_r(Tlcild，prit)； rint（Tdt）； nOderTraverere(T-rchil，print）； retrn ; */ / 按照前序非递归遍历二叉树：栈 */ /*/ voidPedervese（BTee T，int(pint)(TEeTyp e） Stack；S、base=ULL；S、t=NULL；SElemType p=T；/指向当前访问得结点 IitSta（S）; wile（p!SckEmpty（S）) i（p) pint（p-daa）； Pus（,p）; p=hil; else

27、Pp(S,p）； p=pchid; rern; oid OrderTreaing（BihTre &Thr，BiThrreT)/中序遍历二叉树,并将其中序线索化，Thrt指向头结点Thrt（BiThTree）alloc(szeof（iTre）；TrtLTag=L;/建头结点TrtRTag=hra;rtrchil=Thr;/右指针回指f（!T)rchi=Trt;lsehrt-lchil;prehrt；InThreadig()；中序遍历进行中序线索化rerchild=rt;prRagThrea；/最后一个结点线索化Thrt-rhild=pre；=Thrt;/InrdThrangvoiInreadin

28、g(BiThrTre p) if(p） InTreding（-hld)； /左子树线索化 if(！plhild) / 建前驱线索 -Lag = Threa； plchil = re； i(！pr-rhld） /建后继线索 re-RTag =Thrad; -rchid = p； pre= p； /保持re指向p得前驱 Inhrein(-rchild）; / 右子树线索化 Ireadinnt IOrerTraerseThr(BiTTreT，int （prnt)(TETp)）中序遍历线索化后得二叉树BiTrree p=NULL;p-lhil；wi(!=T)whl（pLTag=Link）=p-lhil

29、d；if(!prnt(pat)）ern EROR；wile（p-RTag=Tred & prhild！=T）p=prchid；nt(pdata）；=prchid；etrn O；/*以下为辅助函数*/it prin（TlemT ）print（c”，e)；return OK;栈函数/栈得初始化/vid ItStac（SqStS)S、ae=（SEleme)maloc（STCK_INISIZEse(SElemTyp)；S、op=S、base;/初始为空S、stackse=ACK_INT_SIZE;eturn；*栈顶插入元素/vod Pus(Sqac &,Eemypee）i(S、top-S、bs=S、s

30、taksize)S、bse(ElemType*)reallo（、base，（TACK_IT_SI+STACKINCEENT）szeof（lmype)）;S、topS、bae+S、stacsize；S、taie+=STACKINCREMEN;*S、top=e;/栈顶删除元素/voidPp(SqStk ，SElemType）if(S、top=S、se）rtrn;e=-S、t;retr；it tcmpty（qSck S）*若栈为空栈,则返回K，否则返回ERROR/i(S、top=S、ase)return OK;elserturnRROR；intGetp（SqSack S，SElypee）i(、top=、bae）reurn ERRO;*（、top-1）；turn OK;*/ / 按层次顺序建立一棵二叉树 */ /*voidLevlrer(BTre ） in i，; BiTNoe *q20,； /q0用于模拟队列,存储入队得结点/ p； f（p!NULL） =1；qip;=2； /i为队首位置,j为队尾位置*/ whle（i!j) =q;