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

数据结构之二叉树实验报告题目:二叉树的遍历和子树互换指导老师：杨政宇班级：通信1２０2姓名:徐江学号：需求分析演示程序分别用多种遍历算法遍历二叉树并把数据输出。输入字符序列，递归方式建立二叉树。3.在演示过程序中，用户敲击键盘，输入数据,即可看到数据的输出。４.实现链式存储的二叉树的多种遍历算法。遍历算法涉及：中序递归遍历算法、前序递归遍历算法【选】中序遍历非递归算法先序或后序遍历非递归算法建立中序线索，并进行中序遍历和反中序遍历5.实现二叉树的按层遍历算法６.设计一个测试用的二叉树并创建相应的内存二叉树，可以测试自己算法的边界(涉及树节点数为０、1以及>１的不同情形）。7.测试数据:输入数据：－+a*b-ｃd-ef概要设计说明:本程序在递归调用中用到了链表,在非递归调用时用到了栈。栈的抽象数据类型ADTStacｋ{数据对象：D={ai｜ai∈char,ｉ=1，2,３……..｝数据关系：R＝{<ａi-１,ａｉ>|ａi-１,aｉ∈D，ｉ=2,３…..}基本操作:IｎｉtＳtａck(&S)操作结果：构造一个空栈ＳtackEｍpty（S)

ﻩ初始条件:栈S已存在。ﻫ 操作结果:若S为空栈,则返回OK,否则返回ＥRRＯＲ。Push(&S，e)

ﻩ初始条件:栈S已存在。

操作结果:插入元素ｅ为新的栈顶元素。

ﻩPｏｐ(&S，＆ｅ)

初始条件：栈S已存在且非空。ﻫ

ﻩ操作结果:删除S的栈顶元素，并用ｅ返回其值。GｅtToｐ（S，&e)ﻫﻩ初始条件：栈S已存在且非空。

ﻩ操作结果:用e返回S的栈顶元素。｝2.二叉树的抽象数据类型ＡDTBinａｒyTree{ 数据对象D：D是具有相同特性的数据元素的集合。ﻫ 数据关系R：

若D＝Φ，则R=Φ,称BinaryTreｅ为空二叉树;ﻫﻩ 若D≠Φ，则R={H}，H是如下二元关系；

ﻩﻩ（1)在D中存在惟一的称为根的数据元素root,它在关系Ｈ下无前驱；ﻫ ﻩ(２)若D－{root}≠Φ，则存在D-｛root}＝{D1,Dr},且Ｄ１∩Dr＝Φ；

ﻩ (3)若D1≠Φ，则D1中存在惟一的元素ｘ1，＜roｏt，x１>∈H,且存在D1上的 ﻩﻩ关系H1⊆Ｈ;若Ｄr≠Φ，则Dr中存在惟一的元素ｘr，＜rｏot，xr＞∈H,且ﻩﻩ ﻩ存在上的关系Hr⊆Ｈ；H={<root,x1>,<root,xr＞,H1,Ｈr｝;

ﻩﻩ（4）（Ｄ１,{H1｝)是一棵符合本定义的二叉树，称为根的左子树；(Dｒ,{Hr})是一 ﻩﻩﻩ棵符合本定义的二叉树，称为根的右子树。ﻩ基本操作：

CrｅatｅBiTrｅe（&T)ﻫ ﻩ初始条件:给出二叉树T的定义。

ﻩﻩ操作结果：按规定构造二叉树T。ﻩPrｅＯｒｄerＴrａｖeｒse_ｒe（Ｔ，ｐｒint())ﻫﻩﻩ初始条件：二叉树T存在,ｐrint是二叉树所有结点输出的应用函数。

ﻩ操作结果:先序递归遍历Ｔ，对每个结点调用函数prｉnｔ一次且仅一次。一旦ﻩ ﻩﻩ priｎt(）失败,则操作失败。 InＯｒderTrａversｅ(T,priｎｔ())ﻫﻩﻩ初始条件:二叉树T存在,ｐrint是二叉树所有结点输出的应用函数。ﻫﻩﻩ操作结果:中序非递归遍历T，对每个结点调用函数ｐriｎt一次且仅一次。一 ﻩ ﻩ旦ｐrintf()失败，则操作失败。IｎOrderTravｅrse_re(T，ｐｒint())ﻩ 初始条件：二叉树T在在,priｎt是二叉树所有结点输出的应用函数。操作结果：中序递归遍历Ｔ，对每个结点调用函数print一次且仅一次。一旦 ﻩ prｉntf()失败，则操作失败。PreOrdｅrTraｖｅrse(T，print（))初始条件：二叉树Ｔ存在,priｎｔ是二叉树所有结点输出的应用函数。

操作结果:先序非递归遍历T,对每个结点调用函数pｒｉｎｔ一次且仅一次。一ﻩ 旦priｎｔ（）失败，则操作失败。Leｖｅlorｄｅr（Ｔ)初始条件:二叉树T在在。操作结果:分层遍历二叉树Ｔ，并输出。InOrdeｒThreadｉng(Thrt,T);初始条件:二叉树T在在。操作结果:中序遍历二叉树，并将其中序线索化。IｎOｒdeｒTraｖerse_Ｔhr(T，priｎt);初始条件:二叉树Ｔ在在。操作结果：中序非递归遍历二叉线索树TInThreadinｇ（ｐ）；初始条件:结点ｐ在在。操作结果:结点p及子树线索化。3．主程序的流程:voidmain(）{ﻩ初始化; 提醒；ﻩ执行二叉数ADＴ函数;｝4．本程序包含三个模块主程序模块ｖoidmａin()｛初始化；{接受命令;显示结果；｝｝链表模块。递归调用时实现链表抽象数据类型。栈模块。非递归调用时实现栈的抽象数据类型。具体设计1.宏定义及全局变量#ｄefinｅTElemTyｐｅchａｒ#ｄefineSElｅmＴypeBｉTrｅe#defineOK1#ｄefｉneOVＥＲFLOW0＃ｄｅfｉｎeERROR0#ｄｅfineSTACK_ＩＮIＴ_SIZE1０0＃ｄefineSTACＫINCＲＥMＥＮT１0SqSｔackS；BiThrTreepｒｅ;BiThrTrｅei；2.函数定义ｉｎtCrｅａteBiTree(BiTrｅe&T)；ﻩ ﻩﻩﻩ ／/创建二叉树voidPreOrderＴravｅrsｅ_ｒe（ＢiTreeT，void(＊prinｔ)(TElemTypeｅ));ﻩ//先序递归遍历二叉树ｖoidＩnOrｄeｒTraveｒse（BｉＴreeT,ｉnｔ（＊priｎｔ)(TＥleｍTypｅｅ));ﻩﻩ//中序非递归遍历二叉树ｖoidＩｎOrdｅrTraｖerｓe_ｒe(BiTrｅeT，iｎｔ(*print)(TElｅmTｙpee)); /／中序递归遍历二叉树ｖoｉｄPｒeOrｄeｒTraｖeｒｓe(BiTreeT,inｔ（*print)(TElｅmTyｐeｅ)); //先序非递归遍历二叉树intprｉnt(TElemＴyｐee）; //打印元素voidInｉtSｔack(SqＳtack＆S）;ﻩﻩﻩ //栈的初始化voｉdＰｏｐ(ＳqSｔaｃk&S,ＳＥlemＴyｐｅ&e);voｉdPｕsh(SｑSｔack＆Ｓ,SEｌeｍTyｐe&e);intＳtacｋEｍpty（SqSｔackS);iｎtGｅtTop(ＳqＳｔaｃkS，SEleｍType＆ｅ);voidLevｅlordeｒ(BiTreeT)；ｖoidＩnＯrderThreaｄing(ＢiTｈrTree&Thrt,BiTｈｒTrｅeＴ)；intIｎＯｒderTraverse_Thr（BiThrTrｅeT,int（*prｉnt)(ＴＥｌemTypee));voiｄＩｎThreaｄiｎｇ(BｉThrTreep）;3.二叉树链表数据结构:tyｐeｄeｆstructBiＴNode{ ＴElｅmTｙpｅｄata；ﻩｓtｒucｔBiTNode*lchild,*rchiｌd;ﻩPointｅrTaｇＬTag,RＴaｇ；}BiＴNｏde,*ＢiTree,BiTｈrNoｄｅ,*BiＴhrＴｒee;ﻩ基本操作:a)构造二叉树ＴiｎtCrｅaｔｅBiＴrｅｅ(BiTreｅ&T){ charcｈ； scanｆ(＂%c"，&ch);ﻩif(cｈ＝='＇) T=NULL; ｅlｓeﻩ{ﻩﻩif(！(T=(BｉTＮode*）ｍａｌloc(siｚeof(BiTNode))）) ﻩ returnEＲROＲ;ﻩ T－>daｔａ=ch; ｉｆ(CrｅaｔeＢiＴｒee(T->lchild))Ｔ->LＴag=Liｎｋ;ﻩ if(ＣreａｔeBiＴree(T－>rchild))T->RTａｇ=Ｌinｋ;ﻩ} ｒeｔｕrｎOK;}b）先序递归遍历二叉数T，并输出所有结点值。vｏｉｄPreOrderＴraｖeｒse_ｒｅ(BiＴrｅeT,int(＊priｎt)(TElemTypee)){ﻩif（T) { if（pｒint（T->ｄａｔａ))ﻩﻩﻩPｒeOrderＴrａverse＿re(T－>ｌchild,print); ＰｒeＯrdeｒTraverｓe_ｒe(T->rchｉｌd,pｒint); ﻩrｅｔuｒn; } ｅlｓe ﻩreturn;｝c)中序非递归遍历二叉树T，并输出所有结点值voiｄInOrdeｒTraversｅ(BiTｒeｅT,ｉｎt(*prinｔ）（TElemTypｅe)){ﻩSｑStackS;ﻩＳ.base=ＮULL;S.top=NULL;ﻩＳEleｍＴypep=NULL；ﻩInitSｔａｃk(Ｓ); Ｐｕｓh（S,T);ﻩwｈiｌe（！SｔackEmpｔy(Ｓ)）ﻩ｛ whｉｌe(GetTop（Ｓ,ｐ)＆＆p)ﻩﻩﻩＰｕｓh(S,p->ｌchild); ﻩＰop(S,p);ﻩ if(!ＳtaｃkＥmpty(S)) {ﻩ Pop(S,p)；ﻩﻩﻩprｉnt（ｐ-＞ｄａｔa）;ﻩ Ｐｕsh(S,p->rcｈild); ﻩ｝ﻩ} ｒetuｒｎ;}d)中序递归遍历二叉树T,并输出所有结点值vｏｉdIｎＯrderTraverse＿re(ＢiTreｅT,int(*prｉnｔ)(TＥｌｅmTypeｅ)){iｆ(Ｔ){ＩnOrdeｒTｒaverse＿ｒe(T->ｌｃhｉlｄ,print);pｒint(T-＞daｔa）;ＩｎＯrdｅrＴｒavｅrsｅ_ｒe（T->rcｈｉｌd，print）；}}ｅ)中序遍历二叉树T,并将其中序线索化，Thrｔ指向头结点vｏidInOrderThreading(BiＴhrTree&Ｔｈrt,BｉThrＴrｅeT)｛ﻩThrt=（ＢｉThrTree)mａlloｃ（ｓiｚeof(BｉThrNode));ﻩＴhrt->ＬTａg=Lｉｎk;/／建头结点ﻩThｒt－>RTag=Threaｄ; Thｒt->rchild＝Ｔｈrｔ；//右指针回指 ｉf(!T）ﻩThrt->lｃhild=Thｒt; eｌse {ﻩ Ｔhrt->lchild=T;ﻩ pｒe=Tｈrt; IｎThrｅａding(T）;／／中序遍历进行中序线索化ﻩﻩpｒｅ->rchild=Ｔhrｔ； pｒｅ->RTag=Tｈread;//最后一个结点线索化 ﻩTｈｒt->ｒchilｄ=pｒe； ｝ ｉ=Ｔhrt;}/／ＩnOrderTｈｒeadingf)结点ｐ线索化voidInTｈrｅａdｉｎg(ＢiＴhｒTreep）{ if(p){ ＩｎThreading(p->lchiｌｄ）;//左子树线索化ﻩif(!p->lchild)//建前驱线索 ﻩ{p->LTag=Ｔhｒeａd；p－>lchilｄ=pｒｅ；}ﻩｉｆ(!prｅ->ｒｃｈilｄ）//建后继线索ﻩﻩ{pre-＞RTaｇ=Thrｅad;prｅ->rcｈild=ｐ;} ｐｒe=p;//保持pre指向p的前驱ﻩＩnThrｅading(ｐ－>rchild）；//右子树线索化ﻩ} }//InThreaｄiｎgｇ)/／中序遍历线索化二叉树inｔＩnＯrderTraversｅ_Thr(BiＴhｒTreｅT,iｎt(*prｉnt)(TElemＴypeｅ)){ﻩBiThrTreｅp＝NULＬ;ﻩp＝T->lchild；ﻩwｈile(p!=T)ﻩ{ﻩ whｉｌｅ(p->LTag==Lｉnk)ﻩ ﻩp＝p-＞ｌchiｌｄ; ｉf(!ｐｒiｎt（p->daｔａ）)ﻩﻩ rｅtｕｒｎERRＯR; ﻩwhiｌｅ(p－＞RTag==Thｒeaｄ＆&p->rcｈiｌd!=Ｔ） {ﻩﻩﻩp=ｐ－>rchｉlｄ; ﻩ pｒｉnt（p－>data); }ﻩﻩp＝p->rｃhiｌｄ;ﻩ｝ returnＯK;}4．栈数据结构：typedefsｔruｃｔ{ ﻩSEleｍType＊base;ﻩﻩSElｅｍType＊top; inｔstacｋsize；｝SｑＳｔack；基本操作:a)创建一个空栈voiｄInitStacｋ（SqＳｔack&S){ S.ｂase=（ＳEleｍType*)malloc（STACＫ＿INIT_SIZE*ｓizeoｆ(SElｅmTｙpe)); S.top=S．baｓｅ;ﻩﻩ／/初始为空 S.stacksiｚｅ＝STACK＿ＩＮIT_SIZE;ﻩretuｒｎ；｝b)栈顶插入元素voidPuｓh(SqSｔａck&S,SＥｌemＴｙpe＆e){ﻩif(S.top－S.ｂase>=S.sｔackｓｉｚe)ﻩ{ﻩﻩＳ.base=(ＳＥlｅｍTyｐe*）reallｏc（Ｓ.bａse，(STACK_INIT_SIZE+STACKＩNＣＲEMENT)＊sizeof(ＳEleｍTyｐｅ））; ﻩＳ.top=S.ｂase+S．ｓｔａcksize；ﻩﻩS．stackｓize+=ＳＴACKINCREMEＮT; } *S.top+＋=ｅ；}c)栈顶删除元素ｖｏｉdPop(SｑStack&Ｓ,SEleｍＴyｐe＆e）{ﻩiｆ(S.toｐ=＝S.base) ﻩreｔｕrｎ；ﻩe＝*－－Ｓ．top； ｒｅtuｒn；}d)判断栈是否为空栈iｎtSｔacｋEmpty（SqＳtackS) ﻩ ｛ﻩif(Ｓ.tｏp=＝Ｓ.ｂase) ﻩreturnＯK;ﻩeｌseﻩﻩrｅｔurnＥRROＲ;}e）e返回S的栈顶元素ｉntＧetToｐ(SqＳtａckＳ,SElemTyｐe&e){ﻩiｆ（S.ｔoｐ==S.baｓe)ﻩ ｒｅturnERRＯR; e=*(S．ｔop-１); ｒｅtｕrnOK;}５.主函数voidｍaiｎ（){ｉntfｌag; BiＴreeＴ; BiThrTreeTｈrt;ﻩｐrintf（"***＊*＊＊******＊***＊＊*************＊***＊***************＊*\ｎ");ﻩpriｎtf("**实验12二叉树的遍历＊*\n"); pｒinｔf("＊*１.实现二叉树的不同遍历算法和二叉树的中序线索化算法*＊\ｎ"）; printｆ("**a)中序递归遍历算法；*＊\n"）; pｒintf("＊*b)先序递归遍历算法;*＊\n");ﻩprinｔf(＂*＊c)中序遍历的非递归算法；**＼n"); ｐｒiｎtf（＂*＊d)先序或后序遍历非递归算法之一;**＼n");ﻩpriｎtf（"**e)建立中序线运用线索进行中序遍历和反中序遍历。**\n＂);ﻩpｒinｔf("*＊2.实现二叉树的按层遍历算法。＊*\n＂); pｒintf（"******＊＊***＊*＊＊****＊*****＊**＊＊**＊****＊＊*＊**＊*＊*****＊*＊＊**＊\ｎ＂); priｎtf("\n选择操作：\n\ｔ1.先序与中序遍历算法＼n\ｔ2.中序线索的中序遍历和反中序遍历算法\n\ｔ３.按层遍历算法\n请选择:"); sｃaｎｆ("%d",&ｆlａg)； switｃｈ（flag） {casｅ1:ﻩﻩ ﻩﻩﻩpｒintf（"前序递归创建二叉树（空格表达此结点为空):\ｎ");ﻩﻩ getchar();ﻩ ﻩﻩCreａteBｉTrｅｅ(T)；ﻩﻩﻩ priｎtf(＂中序递归遍历输出："); ﻩﻩInOrｄeｒTraverse_rｅ(T，print）；ﻩﻩﻩﻩｐrｉntf("＼n前序递归遍历输出:"）； ﻩﻩ ＰrｅOrderＴraｖｅrｓe_re(T,print); ﻩﻩprinｔf("\ｎ中序非递归遍历输出：");ﻩﻩ InＯrdeｒTrａverse（T,print); ﻩﻩ ｐrinｔf("＼n前序非递归遍历输出："）；ﻩﻩﻩ PreOrｄeｒTｒａverse(T,prinｔ）;ﻩﻩﻩ printf（"\n")；ﻩﻩ bｒeak; ﻩｃａse２:ﻩpｒintf(＂前序递归创建二叉树（空格表达此结点为空):\n＂); ﻩﻩgetchar（）；ﻩ ﻩ CrｅaｔｅBiTrｅe(T); ﻩ ﻩpｒinｔf("＼ｎ中序遍历线索化二叉树：");ﻩﻩ InOrdeｒＴhreaｄiｎg(Thｒt,Ｔ); ﻩInOｒdｅrTraverｓe_Ｔhr(Thrt，print)；ﻩﻩﻩ ｂreaｋ； case3:priｎｔf("前序递归创建二叉树（空格表达此结点为空）:\n");ﻩﻩﻩ ｇｅtｃｈar(）；ﻩﻩ ﻩCreateBiTｒee(Ｔ）；ﻩ ﻩ ﻩ ｐrintｆ("\ｎ按层遍历输出:")；ﻩﻩﻩ Levelorder（T);ﻩﻩﻩﻩｐriｎtf("\ｎ＂);ﻩﻩﻩﻩbreaｋ;ﻩ ｄeｆault:rｅtｕｒn; }｝函数间调用关系mainmainInOrderTraverse_reCreateBitreePreOrderTraverse_reInOrderTraversePreOrderTraverseInOrderThreadingInOrderTraverse_ThrThreadingStack操作调试分析1、二叉树的分层遍历，开始时想用队列来做，但考虑到比较麻烦，因而改为数组模拟队列,简朴易懂,课后可自行尝试用队列来做。2．

在线索化二叉树时考虑到假如将两种存储结构分开将导致两个类型的指针不能互相传值,导致许多麻烦。比较两种存储结构发现，线索二叉树比二叉树多了两个标志域LTag，Rtaｇ。于是把两种存储结构合并为BiＴhrNode,并在建立二叉树时把ＬTag，Rtag均置为Liｎk。程序正常运营。3．进入演示程序BiTｒee.cｐp，完毕编译，连接(即按下ＣtrlF5）进入演示界面，或直接打开执行文献BiＴreｅ.exe,产生如下图所示的界面：用户需根据用户提醒信息操作,输入二叉树(以空格表达空结点），输入完毕后按回车键，屏幕上打印出相应于该二叉树的各种遍历结果。如下图:测试结果输入：-+a＊ｂ－cｄ-ｅf屏幕输出:中序递归遍历输出：a+b*c-d前序递归遍历输出：＋a*ｂ-cd中序非递归遍历输出:a＋b＊c-d前序非递归遍历输出：+a＊b-cd按层遍历输出：+a＊b-ｃd中序遍历线索化二叉树：ａ＋b*ｃ-ｄ附录BiTｒee．cｐpBiＴｒee.eｘｅ#incluｄｅ<sｔdio.h>#iｎｃluｄe<ｓtdlib.h＞#defｉneＱＥlｅmTｙpeBiTNode#defiｎeTEleｍTｙpecｈaｒ#defineOK1#deｆineOVEＲFＬOW0#deｆｉneEＲROR0＃defineＳTACK_INIT＿ＳＩＺE100#ｄefineＳTACKINＣREMENT10tｙpeｄefeｎumＰointｅrＴag｛Ｌinｋ,Tｈread};ﻩ//Ｌinｋ＝=０，指针,Threａd=＝1，线索typｅdefsｔructBiTNode{ TEｌｅmTｙpedata; sｔrｕｃtBiＴNｏde*lchild,*rｃhild;ﻩＰoiｎterTaｇLTａg,ＲTａg;}BiＴNoｄe，*BiＴree,ＢiTｈrＮoｄｅ,*ＢiThrTree; ／/二叉树＃deｆｉneQＥleｍTｙpeBiTNode#ｄefineSEｌemＴypeBiTreｅｔypeｄeｆsｔrｕｃt{ SElemType＊base;ﻩＳEleｍType*top； ｉnｔstacksｉze；}SqStａck；//全局变量ＳqStａｃkS;ＢiＴhrTｒeeprｅ;BｉＴhrTrｅei;/*函数声明*/intCreatｅBiTree（ＢiTree&T);ﻩ ﻩ ﻩ/／创建二叉树voidPreOrｄｅrTraverse_re(BiTｒeeT,ｖoid(*ｐrｉnt）(TＥleｍTyｐeｅ)); /／先序递归遍历二叉树voｉdInOｒｄｅrＴraveｒse(BiTｒeeＴ,inｔ(*ｐriｎｔ)(TＥlemTypee)); ﻩ//中序非递归遍历二叉树voidIｎOｒdｅrTraverse_re(BｉＴｒeeＴ,inｔ(＊ｐrｉnt)（ＴEｌemTypeｅ)）; /／中序递归遍历二叉树voidPrｅOrdｅｒTｒaverse(BiTreeT,inｔ(*priｎt)（TEleｍＴypee));ﻩ //先序非递归遍历二叉树intprinｔ(TＥｌemTyｐｅe); ﻩ／／打印元素vｏidＩnitSｔａcｋ(SqStaｃｋ&S）;ﻩ ﻩﻩ／/栈的初始化vｏiｄPop(SqＳtａck&S,SEleｍTyｐe&e）;voiｄPush(SqStack&S,SEleｍType&ｅ)；ｉntSｔackＥｍpty（SqStackＳ);intGetＴoｐ(SqStａckＳ,ＳElemTypｅ＆e);voｉdＬｅvｅloｒdｅr(ＢｉTreeT)；ｖoidInOrdｅrThreａdｉｎg(BiThrTｒeｅ&Thrｔ,BiＴhｒＴrｅｅT);intIｎOrdｅrＴraverｓe_Thr(BiＴhrTｒeeT,inｔ(*pｒinｔ)(ＴＥlemＴypee));voｉdInThreadiｎg(ＢｉThrＴrｅｅｐ）;／*二叉树的创建递归创建*/intCreateBiＴree(BｉTree＆T){ﻩｃharｃh； ｓcanf（"%c"，&ch);ﻩｉf(ch＝='')ﻩ T=ＮULＬ;ﻩｅｌｓe ｛ﻩ if（!(T=(BiＴNode*)maｌｌoｃ（ｓizeof(ＢiＴＮoｄe)))） ﻩｒeturｎERＲOR；ﻩ T->data＝ch;ﻩ if(CreateBiTreｅ(T－>lｃhiｌd)）T->ＬTag＝Ｌｉｎk；ﻩﻩif(CｒeateＢｉTree(T->rchild))Ｔ－>RTａg＝Liｎk; }ﻩｒｅturnＯK；｝/****＊＊********＊*＊******＊********＊*＊＊****＊**／/＊先序递归遍历输出*／／＊＊*＊＊*＊***＊*＊***＊*＊********＊*****＊**＊***＊*＊／vｏidPｒeOrderTraversｅ_re(BiTreeT,int(＊ｐrint)(TEｌemＴyｐee)){ if（Ｔ） ｛ ﻩｉf(ｐｒｉnt(T->daｔa))ﻩ ﻩPｒeOrｄeｒTｒａversｅ＿rｅ(T-＞lｃhild,print）；ﻩ PreOrdeｒTrａverse_re(T->rchild，priｎt);ﻩﻩｒetｕrn； }ﻩelse return;}/***＊******＊****＊*＊＊＊＊***＊*＊**＊**＊*＊****＊*＊*//＊中序非递归遍历输出＊／/*＊*****＊**＊**＊＊************＊******＊*＊**＊＊**/voｉdIｎOrdｅｒＴｒavｅｒｓe(BiTreeT，ｉnｔ（＊print）(TＥlemTypee)){ SqSｔaｃkS; Ｓ.base=NＵLL;S．top＝ＮUＬL;ﻩSElｅmTyｐep=NＵＬL;ﻩInｉｔＳtａｃｋ(S);ﻩPｕsh(Ｓ,T）； whｉｌe(!StacｋEｍptｙ(Ｓ))ﻩ{ﻩﻩwhｉle(GetTｏp(Ｓ,p)&＆p) ﻩ Push(S,p->lchild）;ﻩﻩPop(S，p）; ｉf(!StackEmｐｔy(S)）ﻩ ｛ ﻩ Ｐop(S,ｐ);ﻩ ｐrｉnt(ｐ－>daｔa); ﻩ Ｐｕsｈ(S,p－＞rchild); } }ﻩreturn;}/**＊＊＊****＊**＊*＊**********＊***＊＊＊*****＊*****／/＊中序递归遍历输出*//＊***＊＊*＊＊***********＊＊******＊****＊*********/voidIｎOrderTｒａｖｅｒsｅ＿rｅ(BiＴreeT，iｎt(＊ｐｒiｎt)(TEｌeｍTypｅe))｛if(T){InOrｄeｒTrａverse＿re(T->lchｉｌｄ,ｐriｎt);pｒint(Ｔ->data);ＩnＯrｄeｒTｒavｅｒse_re(Ｔ->rcｈild,prinｔ)；｝ｒeｔurn;}/*******＊*******＊****＊*******＊＊*＊****＊＊*****//*按照前序非递归遍历二叉树:栈*//*＊******＊*＊**＊*****＊**＊*****＊*******＊*＊****/vｏidPreOrｄｅrTravｅrse(BiTｒeeＴ，int(*ｐrint)（TElemＴｙｐｅｅ)）{ﻩSqStａckS;ﻩＳ.bａse=ＮULL；S.tｏp=ＮUＬL； ＳElｅｍTｙpｅp=T;／/p指向当前访问的结点InitStaｃk(Ｓ);wｈｉle(p||!StacｋEmptｙ（S)){if(ｐ)｛print(ｐ->dａｔa）；Pｕｓh(Ｓ,p);p=p->lchilｄ;}else{Pop（S，ｐ）;p=p->rcｈilｄ;}}ｒeturn;}ｖoidIｎOｒｄｅrThｒeading(ＢiThrＴreｅ&Thrｔ,BｉThrＴｒeeＴ)/／中序遍历二叉树T，并将其中序线索化，Ｔhrt指向头结点{ Ｔhrｔ=(BｉＴhrTｒee)malloc(sｉzｅof(BｉThrNｏde）)；ﻩThrｔ->LTag=Liｎk;//建头结点ﻩThrt->ＲTag＝Thｒeａｄ; Thｒt－>rchild＝Tｈrt;/／右指针回指 if(!T) Ｔhrｔ-＞lchild=Thrt； ｅlｓeﻩ｛ﻩﻩTｈrt->lｃhｉld=T;ﻩ pre=Thrt;ﻩﻩInThｒｅadiｎｇ(T)；//中序遍历进行中序线索化 ﻩpｒe->rchild=Ｔhrｔ； pre－>RTａg＝Tｈｒeａd;//最后一个结点线索化 ﻩTｈｒt－>ｒchilｄ=pre; } i=Thｒt；}//InOｒｄｅrＴhｒeadingvｏidＩnThreadｉｎg(BiＴｈrTreep）{if(p)｛InThreａdinｇ(p->lchild)；//左子树线索化if(!p->lｃhilｄ）／/建前驱线索{p－>LTag=Thrｅaｄ;p->ｌｃｈｉlｄ=ｐre；}ｉｆ(！ｐre->rchｉlｄ)//建后继线索｛pre->ＲTaｇ＝Thrｅad;pｒe->rｃhild=p;}pre=p；/／保持pre指向p的前驱InThreaｄing(p->rchilｄ);//右子树线索化}｝/／ＩnThreadingiｎtInOｒderTｒａvｅrｓe_Tｈｒ（ＢiThrＴｒeeT，inｔ(＊print)（TＥlemTypee))／/中序遍历线索化后的二叉树{ﻩＢiThrTreep=NUＬＬ;ﻩp＝T->lｃｈｉld； while（p!=T) { whｉlｅ（p->LTag==Lｉnk)ﻩ ﻩp=p->lｃhilｄ;ﻩ ｉｆ(!print（ｐ->dａtａ）) ﻩrｅｔｕrnERROR; wｈｉlｅ(ｐ-＞RTag＝=Ｔhread&＆ｐ－>ｒchｉld！＝Ｔ)ﻩ {ﻩﻩ ｐ=p－>rchild; ﻩ pｒｉnt（p－>dａｔa）;ﻩ } ﻩｐ=p-＞rchｉld；ﻩ} rｅturnＯＫ;｝/****＊***＊＊*********＊*******以下为辅助函数******＊**************＊＊*＊＊****＊*＊＊***＊*/ｉｎtpriｎt(TElemTypee){ﻩpｒiｎtf("%c",ｅ）; reｔurnOK；}/＊栈函数*//＊栈的初始化*/voidInitStacｋ（ＳqStａck&Ｓ）{ﻩＳ.base=(SElemＴype*）mallｏc（STACＫ_INIＴ＿ＳIZE*ｓizｅoｆ（ＳElｅｍType）);ﻩS.top＝S.ｂaｓe; ﻩ//初始为空 Ｓ.staｃｋｓｉｚe=ＳTACK_INＩT_SIZＥ; rｅturn;}/＊栈顶插入元素*/voidPush(SqStａck&S,SElemTypｅ＆e){ ｉf(Ｓ.top-S.bａse>=S.stacｋsize)ﻩ｛ ﻩＳ.ｂase＝(SＥlｅmType*）ｒealloc（S.baｓe,(SＴＡCK＿ＩNＩT_SIZE+STＡCKＩNCＲEMENＴ）＊sizｅoｆ(SEleｍTypｅ))；ﻩ Ｓ.top=S．base+S．stackｓize;ﻩﻩS.sｔａcｋsize＋=SＴACKINCＲEMＥNT;ﻩ｝ﻩ*S．ｔoｐ++＝e;}/＊栈顶删除元素*/voidPｏp(ＳqStacｋ＆Ｓ，SElｅmTｙpe&ｅ)｛ﻩiｆ（Ｓ.ｔｏp＝＝S.ｂａｓe） rｅｔuｒn; e=*--S．top;ﻩｒｅturn;}inｔStaｃkEｍpty（ＳqＳtaｃkＳ)ﻩ ﻩ／*若栈为空栈，则返回OK，否则返回EＲROR*/{ ｉf(S.top＝=S.base） ﻩreturnOＫ;ﻩｅlｓeﻩ returｎERROR;}intGeｔTop(SqSｔacｋS,ＳEｌｅmType&ｅ){ ｉf(S.toｐ=＝S.baｓe)ﻩﻩrｅturnＥＲROＲ;ﻩe＝*(S.top-１); returnOK；}／*＊＊*****＊＊***＊***＊＊＊***＊＊**＊****＊*＊*******＊*＊*********＊*＊***／／*按层次顺序建立一棵二叉树＊／/**＊*＊＊*＊******＊＊*****＊********＊******＊*********＊＊***＊*＊****＊／vｏidＬevelordｅr(BiTｒｅeT){inｔi,j;BiＴNodｅ*q[２0],*p;/*ｑ[20]用于模拟队列,存储入队的结点*/p=T;ｉf(p!＝ＮＵＬL）{i=1;q［i]＝p;j=2;｝/*i为队首位置，j为队尾位置*／while(i!＝j){p=ｑ[i]；prｉntf("%c",ｐ->ｄata);/＊访问队首元素*/if(p－＞lｃｈild!=ＮＵLL）{ｑ［ｊ]=p-＞ｌchild；j++;}/*若队首元素左链域不为空,则将其入队列*/iｆ(p->rchｉld!＝ＮULＬ){ｑ[j］=ｐ-＞rchiｌd；j＋+；}/＊若队首元素右链域不为空,则将其入队列*/i+＋;／*将队首移到下一个位置*/}}voidmain(){ iｎｔｆｌａg； BiTreeT; BiThrTｒeeThrt; priｎｔf（"*＊****＊**＊**＊＊***＊****＊******＊******＊*＊***＊*＊＊**＊*＊*******＼ｎ")；ﻩpｒｉntf("**实验１2二叉树的遍历**\n");ﻩprｉnｔｆ("*＊1.实现二叉树的不同遍历算法和二叉树的中序线索化算法**\ｎ＂);ﻩpｒinｔｆ（"*＊ａ)中序递归遍历算法;*＊\n＂）; printf("**b)先序递归遍历算法;