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

数据结构之二叉树
实 验 　报 告

题目：二叉树得遍历与子树交换
　 　 　 　 指导老师：杨政宇
　 　 班级：通信１2０２
　 　 　　 　　姓名:徐江
　　 　 　 　　　 学号:０9091２1１２７
需求分析
1. 演示程序分别用多种遍历算法遍历二叉树并把数据输出.
2. 输入字符序列,递归方式建立二叉树.
3、在演示过程序中，用户敲击键盘，输入数据，即可瞧到数据得输出.
4、实现链式存储得二叉树得多种遍历算法。
遍历算法包括：
a) 中序递归遍历算法、前序递归遍历算法【选】
b) 中序遍历非递归算法
c) 先序或后序遍历非递归算法
d) 建立中序线索,并进行中序遍历与反中序遍历
５、实现二叉树得按层遍历算法
6、设计一个测试用得二叉树并创建对应得内存二叉树,能够测试自己算法得边界(包括树节点数为０、1以及>１　得不同情形）。
7、测试数据：输入数据:－＋a ＊b —ｃ　 d　 －ｅ f
概要设计
说明:本程序在递归调用中用到了链表,在非递归调用时用到了栈。
1. 栈得抽象数据类型
ADT　Sｔ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得栈顶元素.　
}
２、二叉树得抽象数据类型
ＡDT Biｎ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=｛,<ｒｏ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、主程序得流程：
void mａｉn()
｛
ﻩ初始化；
提示;
执行二叉数ADT函数；
｝
4、本程序包含三个模块
1） 主程序模块
vｏid ｍain（)｛
初始化；
｛
接受命令；
显示结果;
｝
}
2） 链表模块.递归调用时实现链表抽象数据类型.
3） 栈模块。非递归调用时实现栈得抽象数据类型。
详细设计
1、宏定义及全局变量
＃define ＴEleｍTyｐｅ char
＃deｆinｅ　ＳEｌemTypｅ BiＴｒｅｅ
＃definｅ OK 1
#define ＯVEＲFLＯW 0
＃deｆｉne ERROR ０
＃deｆｉｎｅ STACK_INIT_SIZE 100
＃deｆinｅ　STAＣＫINCＲEMENＴ 10
SqStacｋ S;
BiThｒTｒeｅ ｐre;
BｉTｈｒＴｒｅe　ｉ;
2、函数定义
int ＣrｅateBｉTｒee(BｉTree　&T)； ﻩ //创建二叉树
voiｄ　PreOｒderＴraverse_re（BiTree T,voｉd （*prｉｎt）（TElｅｍＴype e)); //先序递归遍历二叉树
voｉd InOrderTraｖｅrse（BiＴree　Ｔ，ｉnt （＊prｉnt）（ＴＥleｍType e)）;ﻩﻩ／/中序非递归遍历二叉树
void InＯrｄerTraｖeｒsｅ＿rｅ(BiTｒee T，int （*ｐrint)（TElemType ｅ)） ； ／/中序递归遍历二叉树
ｖoid PｒeOrdeｒＴraｖersｅ(ＢiTreｅ Ｔ，ｉnｔ （*pｒint）（TEleｍＴyｐe e)）; //先序非递归遍历二叉树

int ｐriｎt(TElemＴｙpe ｅ）；ﻩ //打印元素
void InitStacｋ（ＳqＳtａcｋ &S); ﻩ //栈得初始化
void Pop(SqＳｔａck &S,SElemTｙpe　＆e)；
ｖoid　Push(ＳqＳtacｋ　＆S,SElemＴype &e)；
ｉnt ＳtacｋEmpty(SqStack S）；
int GｅtＴoｐ（SｑＳｔack S，ＳEｌemＴype &e）；
vｏid Leveloｒder（ＢｉＴree T） ；
voｉｄ ＩnOrｄerＴhreａｄing(BiＴhrＴree ＆Ｔhｒｔ，BiThrTrｅe　T)；
iｎt InOrderTraveｒse_Thｒ(BiThrTree T, iｎt （＊ｐｒｉnt)（TElemType　e））;
void InTｈrｅadinｇ（BiTｈrＴree　p）;
3、二叉树链表
数据结构:
ｔypeｄef　ｓｔruct BiＴＮode{
ﻩＴElemTypｅ dａｔa；
ﻩstruｃt　BiTNoｄe *lcｈｉｌｄ ，*rchild；
PoｉnｔeｒTａｇ LTag , RＴａg;
｝BiTNoｄe ,　*ＢiTree ， BiThrＮｏdｅ , *BｉThrTreｅ；
基本操作:
ａ）构造二叉树T
int CreateＢiTｒeｅ(BiTree ＆T)
｛
ﻩchaｒ　ｃh；
ﻩsｃaｎf（＂％c"，＆ch）;
ﻩiｆ（ch=＝’ ’）
ﻩ T=ＮULＬ；
eｌｓｅ
{
ﻩ iｆ（！（T＝(ＢiTNoｄe ＊）malｌoc（ｓizeoｆ（ＢiTＮode）)））
ﻩ return EＲROR；
ﻩT－>datａ=ch;
ﻩﻩif　(ＣｒeateBiＴrｅe（T－＞ｌchｉlｄ)）　T-＞ＬTag=Link;
ﻩﻩif (ＣrｅａｔeBiTreｅ(T—>ｒchｉld）） T—〉ＲＴag=Lｉnk；
ﻩ｝
ﻩreｔurn OＫ；
｝
b）先序递归遍历二叉数Ｔ,并输出全部结点值。
vｏiｄ PrｅＯｒderTraverse＿re（BiTree　Ｔ,int （*print)(TEleｍType e))
｛
if（T）
ﻩ｛
ﻩif(ｐrinｔ(T—>daｔa)）
ﻩ ＰｒeOｒderTraｖersｅ_ｒe（Ｔ—>lchild，priｎt）;
ﻩﻩＰｒｅOrｄeｒＴrａｖerse_re（T—〉rchｉlｄ,pｒiｎt);
ﻩretuｒn ;
｝
else
retuｒn ；
}
c)中序非递归遍历二叉树T,并输出全部结点值
vｏid　IｎOrderTｒaversｅ(BiTreｅ　T,inｔ (*prｉnｔ）（TElemTｙpe e)）
{
ﻩSqＳtack S;
S、bａsｅ＝ＮULL；S、tｏｐ=NUＬＬ；
SElemTypｅ p=NULL；
ＩｎitSｔack（S）;
ﻩPuｓｈ(S,Ｔ);
whｉle（！StaｃkEmptｙ(Ｓ)）
ﻩ｛
ﻩﻩwhile(GｅｔTｏp（S,p)&&p)
Pusｈ（S,p—＞ｌcｈild)；
ﻩPｏp(S，p）；
ﻩﻩif（!StaｃkEｍpty（Ｓ）)
ﻩ ｛
ﻩﻩ Pop（S，p）；
ﻩprint（p—＞datａ)；
ﻩﻩＰｕsh（S,ｐ-〉rcｈild）；
ﻩ}
ﻩ｝
ﻩretｕrn；
｝
d）中序递归遍历二叉树T，并输出全部结点值
voｉｄ InＯｒderTrａｖerse_re(BiTrｅe T,iｎt　（＊ｐｒint）（TEｌemType　e))
{
　if(T)
｛ 　
　 　ＩnＯrderTraverse_rｅ（Ｔ->ｌchild,prinｔ)；
　 ｐrｉｎｔ（T－〉daｔａ); 　
　 　　 ＩnＯrderTｒａｖersｅ＿rｅ（T—＞ｒｃhilｄ,pｒiｎｔ）;
　 　 }　
　｝
e)中序遍历二叉树T，并将其中序线索化,Thrｔ指向头结点
ｖｏid ＩnOrdeｒThreａding（ＢiＴhｒTree ＆Ｔｈrt,BiＴhrTree Ｔ）
｛
ﻩThｒt=（BiTｈrTｒｅｅ)ｍallｏc(siｚeof（BiTｈrNodｅ)）；
ﻩTｈrt—>LTag＝Link；//建头结点
Thrt->RTaｇ=Ｔhread；
ﻩＴhrｔ-〉ｒchild＝Ｔhrｔ；//右指针回指
ﻩｉf（！T)
ﻩThrｔ—〉lchｉld=Tｈrt；
else
{
Tｈｒt－>lchilｄ=Ｔ；
pre=Thｒｔ；
ﻩﻩＩｎThｒeａding(Ｔ);／/中序遍历进行中序线索化
ﻩﻩｐre—〉ｒchild=Thrt;
ﻩﻩｐre—>RTａg＝Thread；//最后一个结点线索化
ﻩ Tｈrｔ－＞rchild=ｐre；
}
i=Thrt;
｝//InＯrdeｒThｒeading
ｆ)结点p线索化
void InThreading(ＢｉThｒTreｅ ｐ) ｛　
　 if （p) {
　　　ﻩＩnThｒeading（p—>ｌchｉld)； 　 ／/ 左子树线索化
　 ﻩif　(!ｐ-〉lchild） ／/ 建前驱线索
　　 ﻩ ｛　ｐ—＞ＬTａｇ　= Ｔhｒeaｄ；　 ｐ—〉lchｉld = prｅ; }
　　　ﻩif (!pre—〉rｃhilｄ) //　建后继线索
　 　ﻩ ｛ ｐre－〉RTａg =　Thｒeａd； 　ｐｒｅ－>rｃhild = p；　｝
　 prｅ　= p； 　 　　　 　 　 // 保持pre指向p得前驱
ﻩInＴhｒeading(p—>ｒchiｌd）； ／／ 右子树线索化
　 }ﻩ
} ／/　IｎThreaｄinｇ
ｇ)//中序遍历线索化二叉树
int IｎOrｄerTｒaverｓe_Ｔhr(BiThｒＴｒｅｅ T， int　（＊prinｔ)（TＥleｍTyｐｅ e））
{
ﻩBiTｈｒＴreｅ p=NUＬＬ；
ﻩp=T—>lchiｌd;
ﻩｗhiｌｅ（ｐ!=T）
｛
whｉｌe（ｐ—〉LＴag＝=Link)
ﻩ p＝ｐ－〉ｌchild；
ｉf(！pｒｉｎt（p->ｄata））
ﻩ reｔｕrｎ　ERRＯＲ；
ﻩwhile(ｐ—>RTag==Ｔｈｒeａｄ ＆＆　p—>rchild！=T）
{
ﻩ p=p—〉rchild；
ﻩ priｎt（p—〉ｄaｔa）;
ﻩ ｝
ﻩ p=p—＞rｃhiｌd；
｝
ﻩｒetｕrｎ　OK；
}
4、栈
数据结构：
tｙpｅdeｆ ｓtrｕcｔ{
ﻩﻩSElemTyｐe　*bａｓｅ;
ＳElｅmType ＊toｐ;
int ｓtackｓize；
｝SqSｔack;
基本操作：
a）创建一个空栈
void IｎitStack（SｑStack　＆S)
{
S、ｂase＝(ＳElemTyｐｅ*）malｌoc（STＡCK_INIT＿SIZE*siｚeoｆ(SＥlｅmTｙpe)）;
ﻩS、top=S、baｓe;ﻩ /／初始为空
ﻩS、ｓtacｋsizｅ=SＴAＣK_ＩNＩT_SIZE；
ﻩｒｅｔuｒn;
}
ｂ)栈顶插入元素
voiｄ Ｐush(SqSｔaｃk　&S，SＥleｍTｙpｅ ＆ｅ)
{
ﻩif(S、ｔoｐ－S、ｂase〉＝Ｓ、staｃksｉze)
ﻩ{
ﻩﻩS、ｂasｅ＝（SElemType＊)rｅalｌoc（Ｓ、baｓe，(SＴACK_IＮIT＿SIZE+STACKＩＮＣＲEMENＴ)＊sizeof(ＳElemTypｅ））;
S、ｔoｐ＝S、bａｓe+Ｓ、stacksize;
ﻩﻩS、staｃksize+=STAＣKINCREＭENT；
ﻩ}
＊S、toｐ++=e；
｝
c）栈顶删除元素
voｉd Ｐｏp（SｑStａｃk &Ｓ，ＳElemType &e）
｛
ﻩif（S、top＝=Ｓ、bａse）
ｒetuｒn；
ﻩe=＊--Ｓ、top;
ﻩreturn；
｝
d)判断栈就是否为空栈
int StackＥmpｔy(ＳｑStack S）ﻩﻩ
｛
ｉf（Ｓ、ｔｏp＝=S、base)
reｔurn　OK；
eｌse
rｅturn ＥＲROR；
｝
ｅ）ｅ返回S得栈顶元素
int　ＧeｔToｐ（SqStａｃk S，SEｌemＴypｅ ＆ｅ）
{
if(Ｓ、top==S、ｂase)
ﻩreｔurn　ERROR；
ﻩe＝＊(S、top—1）；
reｔurn　OK；
}
５、主函数
voiｄ ｍaiｎ(）
｛ｉnt　ｆｌaｇ；
BiTreｅ T；
BiTｈrTree Thｒt；
ｐrｉntf(”*＊*＊＊***＊＊＊**＊*＊*＊＊***＊*＊*＊*＊＊*＊＊＊**＊＊*＊*＊＊＊＊＊***＊＊**＊\ｎ”）；
ﻩpｒintf（”** 　 实验12　　二叉树得遍历 　 　 ＊＊\n”)；
printf（”＊＊　1、　实现二叉树得不同遍历算法与二叉树得中序线索化算法 **＼n")；
ｐｒinｔｆ（”*＊ a） 中序递归遍历算法; 　 　 　 　 　　 　　　　 **\ｎ"）;
ﻩpｒｉntｆ（＂＊＊ b) 先序递归遍历算法;　　　 　 　　　 　　 　 　 *＊\n")；
ｐrｉｎｔf（”＊* c） 中序遍历得非递归算法; 　 　 　 　　　 　　 *＊\ｎ＂);
ﻩprintf(”＊* 　d) 先序或后序遍历非递归算法之一； 　 　　 　　 *＊＼n"）;
prｉｎtｆ（＂＊＊　 e） 建立中序线利用线索进行中序遍历与反中序遍历。 ＊＊\n”)；
ﻩprｉntf（”＊* 2、 实现二叉树得按层遍历算法. 　 　　 　 　 　＊＊\n"）;
ﻩprintf（"＊＊＊＊*＊＊＊*＊**＊＊＊*＊**＊*＊＊＊＊**＊***＊＊**＊*＊***＊*＊＊*＊***＊*＊＊＊*＊＊\n＂);
ﻩｐrｉntf（"＼n选择操作：\n\t1、先序与中序遍历算法＼ｎ\ｔ2、中序线索得中序遍历与反中序遍历算法\n\t3、按层遍历算法\n请选择：”)；
ﻩｓcanf（"％ｄ",&flag）；
ﻩswitｃh(flag）
ﻩ｛　 　ｃase 1: ﻩ
ﻩ ｐｒｉntf（"前序递归创建二叉树（空格 表示此结点为空)：\n”）;
ﻩﻩ ｇetｃhaｒ（）；
ﻩ CreateBｉTree(T)；
ﻩ ﻩprｉntf("中序递归遍历输出：＂）;
ﻩ ﻩInＯrderＴraverｓe_re（T，ｐriｎｔ）；
ﻩﻩｐrｉｎtｆ("\n前序递归遍历输出：”）；
ﻩﻩ ＰreOrｄｅrTraｖerse_re（T,prｉnt）;
ﻩprintf("\ｎ中序非递归遍历输出:");
ﻩ InOrｄerTrａvｅｒse(T，prｉnt)；
ﻩ ﻩ prｉntf（”＼n前序非递归遍历输出：”）;
ﻩ ﻩＰreOrderTraverｓe(T，prｉnt);　
ﻩﻩ ｐrintｆ(”\n"）；
ﻩﻩ bｒｅaｋ；
ﻩcase 2： pｒｉntf（”前序递归创建二叉树(空格 表示此结点为空)：\ｎ＂）；
ﻩﻩﻩﻩgeｔcｈar(）;
ﻩ CreaｔeBｉTree（T）;
ﻩ ﻩｐrintf(＂\n中序遍历线索化二叉树：”);
ﻩ ﻩInＯrdeｒTｈreading（Thｒｔ ， T）；
ﻩ ﻩﻩInOrderTraveｒse_Thr（Thrｔ　， prｉnt);
ﻩﻩﻩ break;
ﻩﻩcase 3:　printf(”前序递归创建二叉树（空格　表示此结点为空）：\ｎ")；
ﻩ getchar(）；
ﻩ ﻩ CrｅatｅBiTｒｅe(Ｔ);
ﻩprintf(”＼n按层遍历输出:"）；
ﻩﻩ Levｅlorder(T）;
ｐrintf(”\ｎ"）;
ﻩﻩﻩ break;
ﻩﻩdefault：rｅｔuｒｎ；
}}
6. 函数间调用关系
main
InOrderTraverse_re
CreateBitree
PreOrderTraverse_re
InOrderTraverse

PreOrderTraverse
InOrderThreading
InOrderTraverse_Thr
Threading
Stack操作

调试分析
1、二叉树得分层遍历，开始时想用队列来做,但考虑到比较麻烦,因而改为数组模拟队列,简单易懂，课后可自行尝试用队列来做。
２.  在线索化二叉树时考虑到如果将两种存储结构分开将导致两个类型得指针不能互相传值,造成许多麻烦。比较两种存储结构发现，线索二叉树比二叉树多了两个标志域LＴaｇ,Rtaｇ。于就是把两种存储结构合并为ＢiThrNode，并在建立二叉树时把LTag,Rtａg均置为Liｎｋ。程序正常运行。
　３、进入演示程序BｉTree、ｃpp，完成编译,连接（即按下Ctｒl F5)进入演示界面,或直接打开执行文件BiTrｅe、eｘe，产生如下图所示得界面：

⒈ 用户需根据用户提示信息操作，输入二叉树（以空格表示空结点)，输入完成后按回车键,屏幕上打印出对应于该二叉树得各种遍历结果.如下图:

六、 测试结果
输入:－+a *ｂ -c d　　－e f
屏幕输出：
中序递归遍历输出:a＋b*c—d
前序递归遍历输出：+a＊ｂ-ｃd
中序非递归遍历输出:a＋b＊c－d
前序非递归遍历输出:+ａ＊b-ｃｄ
按层遍历输出:+ａ＊b-cd
中序遍历线索化二叉树:a+b＊c－d
七、 附录
BiＴrｅe、cｐｐ
BiTree、ｅxe
＃iｎclｕdｅ＜stｄｉo、h>
＃include＜stdlib、h>
＃deｆｉne　QEｌｅmType BiＴNoｄe
＃ｄefinｅ TElemTｙｐe char
＃defｉne OK　1
#defiｎｅ ＯVERFＬOＷ 0
＃definｅ ＥRROＲ 0
＃defｉne STACK_IＮIＴ_SＩＺE 100
＃dｅfｉne STＡCKINCREMＥNT １0
typeｄef enum PointerＴag{Liｎk,Thread}；ﻩ／/Lｉnk==０，指针，Thread==1,线索
tyｐeｄef　ｓtｒuｃt BiTNode{
TElemTyｐe　data;
struct　BiTNode ＊ｌchiｌd ，＊rchｉld；
ﻩPointerTａg　LTaｇ　， RＴａg；
｝BiＴNode　, ＊ＢiＴrｅｅ ， ＢiThrNode , ＊ＢiThrＴｒｅe; ﻩ//二叉树
＃ｄefｉｎe ＱＥlｅｍTｙｐe　ＢｉTＮｏde
＃define SElemType ＢiTｒee
ｔypedef　struct{
ＳＥlemType ＊base;
ﻩＳＥlemType ＊top;
int　ｓtａcｋsizｅ;
}SqSｔack;
／/全局变量
SqSｔack S
ＢiThrTｒee pre;
BiＴhrTree i；
/＊函数声明*/ 　 　　 　　 　
ｉnt CreateBiＴree（BiTｒeｅ &T）; ﻩ ﻩ ﻩ //创建二叉树
void PreOrｄerTrａverｓｅ_re(BiTree　T，ｖoid （＊print)(TEｌｅmＴyｐe e));ﻩ//先序递归遍历二叉树
void　ＩnOrderＴravｅrse(BiTreｅ T，inｔ　（＊pｒｉnt）（TElｅmＴype e));ﻩ ／/中序非递归遍历二叉树
void ＩnＯrderTｒavｅrsｅ_re(BiＴｒｅe T,ｉnt　(＊print)(TElｅmType ｅ）） ；ﻩ/／中序递归遍历二叉树
ｖoid PｒeOｒｄeｒＴｒaveｒse(BiTreｅ T,iｎt (*priｎt）（TElemTｙpe e）)； ﻩ//先序非递归遍历二叉树
ｉnt pｒｉnｔ（TＥlemTyｐｅ　e);ﻩ ／/打印元素
vｏid　ＩnitStacｋ（SｑStａｃk ＆Ｓ)； ／/栈得初始化
voｉd　Pop（SqＳtack &S，SEleｍType &e)；
void Push(ＳqＳtacｋ ＆S,SElemTypｅ ＆e);
iｎｔ SｔａckEｍpty(SqＳtａck S）;
ｉnt　GetTop（ＳｑStａck S，SＥｌemＴypｅ ＆e)；
ｖｏid　Lｅvｅlorｄer(BiTree T） ；
voiｄ ＩnOrｄeｒThｒeadinｇ（BｉThrTree ＆Thｒｔ，BｉＴhrＴrｅｅ　T）;
int　InOrdｅrTraverｓe_Ｔｈｒ(BｉThｒTree Ｔ,　inｔ （＊priｎt）（TElemType e）);
void ＩnＴｈreadiｎｇ（ＢｉTｈrTrｅe　p)；
/＊二叉树得创建递归创建＊/
int　CｒeａteBｉTree（BｉTｒee ＆Ｔ)
｛
ﻩｃｈａr ch；
ﻩｓcanf（＂%c”，＆ch)；
iｆ（cｈ=＝’　’）
ﻩT=NＵLL；
ﻩelsｅ
｛
iｆ（!(T=（BiTNode *）maｌlｏc(sizeｏf(ＢiＴNode)）)）
ﻩ ﻩreturｎ　ＥRＲOR；
ﻩＴ-〉data=cｈ；
if （CrｅaｔeBiＴｒｅe(Ｔ—>lchild）) T－>LTaｇ=Link;
ﻩif (CｒeaｔｅＢiTree(Ｔ—〉rcｈilｄ）） T->ＲＴaｇ=Link；
ﻩ}
retuｒn ＯＫ；
｝
/＊＊＊**＊＊＊＊＊**＊＊＊*＊＊＊*＊*＊＊*＊＊＊＊**＊＊＊＊＊****＊**/
/* 　 　　 　先序递归遍历输出　 　 　 　＊/　
　／*＊＊＊*＊*****＊＊＊＊*＊*＊*****＊**********＊*＊*＊＊**／
ｖoｉd　PreOrderTravｅｒse_rｅ(BiTree　Ｔ,int　（＊print)(TElemTyｐe　e））
{
ﻩif（T)
ﻩ{
ﻩﻩif(pｒint（T-〉dａtａ))
ﻩ ＰreOrdeｒTｒａveｒse＿re(T-＞ｌchild，ｐrinｔ)；
ﻩ ﻩPrｅOｒdeｒTraveｒse_re(T-＞ｒchｉlｄ，pｒinｔ)；
reｔurｎ ；
ﻩ｝
ﻩelｓe
ﻩﻩrｅturn ；
｝
　／＊****＊＊＊**＊＊＊＊*＊*＊＊＊＊*＊**＊＊＊*＊＊＊*＊*＊＊***＊＊*/
　／＊ 　 　 　 中序非递归遍历输出 　 　 ＊/
　/＊＊＊＊**＊＊*＊**＊＊**＊*＊＊＊＊＊＊*＊*＊*＊＊＊＊*＊＊＊*＊＊**＊/
void InＯrderTraｖerse（BiTree T,inｔ （*prinｔ）(TElｅmTｙｐｅ e）)
｛
ﻩSqStack S;
Ｓ、base＝ＮUＬL;Ｓ、ｔoｐ=ＮULL；
SElemTyｐｅ p=NUＬL；
ﻩInitＳｔack（Ｓ)；
Push（S,Ｔ）；
ﻩwhiｌe（!StackEmpty（S）)
ﻩ｛
ﻩﻩｗｈｉlｅ（GetTop（S，p)&＆p）
ﻩ ﻩＰush（S，p-＞lchiｌｄ);
ﻩ Pｏp（S，p）；
ﻩﻩif（!StaｃｋＥｍptｙ（S))
ﻩ {
ﻩ Poｐ（S，p);
ﻩ ﻩpｒiｎt（ｐ—＞ｄaｔａ)；
ﻩ Pusｈ（S，ｐ—＞ｒcｈｉld）；
ﻩ ｝
ﻩ｝
ﻩrｅｔurn；
｝
　/＊**＊＊＊＊＊*＊*＊*＊＊*＊＊*＊*＊＊＊＊＊*＊*＊*＊*＊****＊＊＊＊*/　
/* 　 　 　 　中序递归遍历输出　　 　　 ＊/
／***＊**＊**＊***＊＊＊＊****＊*****＊**＊＊＊＊＊**＊＊*＊＊＊/
void InOrderTrａveｒsｅ_re（BiTｒee　Ｔ，int (*print）(TElemTyｐe e））　　
｛　
　if（T）
{
　 InOrderTraverse_rｅ(T－〉lcｈild，priｎt)；
　 ｐrint（T—〉dａtａ）；
　 　 ＩnOｒderTraverｓe＿re(T->rchilｄ，print）；
　 　　}
　　 retｕrn ;
｝
　／**＊***＊＊*＊***＊＊＊＊＊＊*＊*＊＊*＊**＊＊＊***＊＊**＊＊＊**/
/＊ 　　　 按照前序非递归遍历二叉树：栈 */
/＊＊**＊＊＊＊**＊＊*＊**＊*＊＊**＊**＊*＊＊*＊＊＊*＊＊＊＊＊*＊**/ 　　
void　PｒeＯｒdeｒＴrａveｒse（BｉTｒee T，int　(＊pｒint)(TEｌeｍTypｅ e））　
｛ 　
SｑＳtack　Ｓ；
ﻩS、base=ＮULL；S、tｏｐ=NULL；
SElemType p=T；／/ｐ指向当前访问得结点
IｎitStaｃｋ（S）;　
　 wｈile（p｜｜!SｔａckEmpty（S）)
　 ｛
　 　 iｆ（p) 　
　 　　 ｛
　 　 pｒint（p-〉daｔa）； 　
　 　 　 　　　 Pusｈ（Ｓ,p）;　
　 　 　 　 p=ｐ—＞ｌｃhilｄ;
　　 　 }
　 　 else
　 　 　 　 　{
　　　 　 　 　 Pｏp(S,p）； 　
　 　　　 p=p－＞ｒchiｌd;
　　 　　 } 　
　 ｝
　reｔｕrn;　
　｝
ｖoid ＩｎOrderTｈreaｄing（BiＴhｒTreｅ &Thrｔ，BiThrＴrｅe　T)
//中序遍历二叉树Ｔ,并将其中序线索化，Thrt指向头结点
{
Thrt＝（BiThｒTree）ｍalloc(sｉzeof（ＢiTｈrＮｏｄe））；
Tｈrt－〉LTag=Lｉｎｋ;／/建头结点
ﻩTｈrt—＞RTag=Ｔhrｅaｄ;
Ｔｈrt—〉rchilｄ=Thrｔ;／/右指针回指
ﻩｉf（!T)
Ｔｈrｔ—〉ｌchiｌｄ=Tｈrt;
ｅlse
ﻩ｛
ﻩ Ｔhrt->lchilｄ＝Ｔ;
ﻩﻩpre＝Ｔhrt；
ﻩﻩInThreadiｎg(Ｔ)；／／中序遍历进行中序线索化
ﻩﻩｐre—＞rchild=Ｔｈrt;
ﻩﻩprｅ—>RＴag＝Threaｄ；//最后一个结点线索化
ﻩ Thrt-＞rｃhild=pre；
}
ｉ=Thrt;
}/／InＯrdｅｒThrｅaｄｉng
voiｄ　InＴｈreading(BiThrTreｅ p) {
　 if　(p）　｛
InTｈreａding（ｐ->ｌｃhｉld)；　 /／　左子树线索化
　 　if　(！p—〉lｃhild) // 建前驱线索
{ ｐ-〉LＴag = Threaｄ； p－〉lchilｄ = ｐre； }
　iｆ　(！prｅ-〉rｃhｉld） //　建后继线索
{　ｐre->RTag =　Thrｅad; ｐｒｅ->rchiｌd = p； }
pre　= p； 　　　 　　 　　 //　保持ｐre指向p得前驱
　 InＴhreａｄinｇ(ｐ->rchild）; // 右子树线索化
　　｝
｝ ／／ IｎＴｈreadinｇ
ｉnt IｎOrｄerTraｖerse＿Thr(BiTｈｒTrｅe　T，　int （＊prｉnt)(TEｌｅｍTｙpｅ　ｅ)）
／／中序遍历线索化后得二叉树
{
BiTｈrＴree p=NULL;
ﻩp＝Ｔ-＞lｃhilｄ；
wｈiｌｅ(ｐ!=T)
ﻩ｛
ﻩ whｉlｅ（p－＞LTag＝=Link）
ﻩ ｐ=p->lｃhild；
ﻩﻩif(!prｉnt(p—〉ｄatａ)）
ﻩﻩ ｒeｔｕrn EＲROR；
ﻩwｈile（p->RTag==Tｈreａd ＆& p－>rｃhild！=T）
ﻩ ｛
ﻩﻩp=p—>rchiｌd；
ﻩ ｐｒｉnt(p－〉data）；
ﻩﻩ｝
ﻩｐ=p－〉rchiｌd；
}
ﻩｒetｕrn OＫ；
｝
/＊**********＊＊**＊＊**＊＊＊＊**＊＊以下为辅助函数＊＊＊*＊＊*＊****＊***＊*＊***＊＊＊＊＊*＊＊*＊＊＊*＊*＊*/
iｎt prinｔ（TＥlemTｙｐｅ ｅ）
{
printｆ（"％c”，e)；
ﻩreturn OK;
｝
／＊栈函数＊/
/＊栈得初始化＊/
vｏid IｎｉtStacｋ（SqStａｃｋ　＆S)
｛
ﻩS、ｂaｓe=（SElemＴｙｐe＊)malｌoc（STＡCK_INIＴ＿SIZE＊sｉｚeｏｆ(SElemTypｅ))；
S、ｔop=S、base;ﻩﻩ//初始为空
S、stacksｉｚe=ＳＴACK_INＩT_SIZE;
ﻩｒeturn；
｝
／*栈顶插入元素＊/
voｉd Pusｈ(SqＳｔacｋ &Ｓ,ＳEｌemＴype　＆e）
｛
ﻩiｆ(S、top-S、bａsｅ>=S、staｃksize)
ﻩ｛
S、bａse＝(ＳElemType*)realloｃ（Ｓ、base，（ＳTACK_ＩＮIT_SIＺＥ+STACKINCＲEＭENT）＊sｉzeof（ＳＥlｅmＴype)）;
S、top＝S、baｓe+S、stacｋsize；
ﻩS、ｓtaｃｋｓiｚe+=STACKINCREMENＴ;
｝
ﻩ*S、top＋＋=e;
}
/＊栈顶删除元素＊/
void　Pｏp(SqStａｃk ＆Ｓ，SElemTypｅ　＆e）
{
if(S、top=＝S、ｂａse）
ﻩ rｅtｕrn;
e=＊-—S、tｏｐ;
ﻩretｕrｎ；
}
iｎt ＳtａcｋＥmpty（ＳqSｔａck S） ﻩﻩ／*若栈为空栈,则返回ＯK否则返回ERROR＊/
｛
ﻩiｆ(S、top==S、ｂase)
ﻩreturn OK;
else
ﻩ rｅturn　ＥRROR；
｝
int　GetＴｏp（SqSｔack S，SElｅｍＴype　＆e）
{
iｆ(Ｓ、top＝=Ｓ、baｓe）
ﻩ reｔurn ERROＲ;
ﻩｅ＝*（Ｓ、top-1）；
ﻩｒｅturn OK;
}
　／＊＊＊＊**＊＊＊＊*＊*＊＊*＊＊＊＊＊**＊＊**＊＊＊＊**＊＊＊****＊＊＊＊＊＊****＊*＊＊＊＊*＊*＊/
　/＊ 　 　 　 按层次顺序建立一棵二叉树　 　 　 　 */　
/＊＊*＊＊*＊**＊＊*＊＊＊＊***＊＊**＊*＊＊＊*＊＊＊＊＊******＊＊＊＊***＊＊*＊＊＊＊***＊＊＊／　
void　Levｅlｏrｄer(BｉTrｅe Ｔ）
｛
　 inｔ i，ｊ;
　 BiTNoｄe *q[20],＊ｐ； /＊q[２0]用于模拟队列,存储入队得结点＊/
　　 p＝Ｔ；
ｉf（p!＝NULL）　
｛
　　 ｉ=1；q［i］＝p;ｊ=2；
｝ /＊i为队首位置,j为队尾位置*/
　 whｉle（i!＝j)　
　 ｛
ｐ=q[ｉ];