二叉树的各种算法.doc

二叉树得各种算法、txt男人得承诺就像８0岁老太太得牙齿,很少有真得。您嗜烟成性得时候,只有三种人会高兴，医生ﻩ您得仇人与卖香烟得。ﻩﻩ ﻩﻩﻩ/*用函数实现如下二叉排序树算法:　
(1） 插入新结点　
(2） 前序、中序、后序遍历二叉树
（3)　中序遍历得非递归算法
(4） 层次遍历二叉树　
（5)　在二叉树中查找给定关键字（函数返回值为成功1,失败０)
（6） 交换各结点得左右子树　
（7）　求二叉树得深度
(8) 叶子结点数
Ｉnpｕt
第一行：准备建树得结点个数n
第二行：输入n个整数,用空格分隔
第三行：输入待查找得关键字
第四行:输入待查找得关键字
第五行：输入待插入得关键字
Ｏｕtpｕt
第一行：二叉树得先序遍历序列
第二行:二叉树得中序遍历序列　
第三行:二叉树得后序遍历序列
第四行:查找结果
第五行：查找结果
第六行～第八行：插入新结点后得二叉树得先、中、序遍历序列
第九行:插入新结点后得二叉树得中序遍历序列（非递归算法)　
第十行:插入新结点后得二叉树得层次遍历序列　
第十一行~第十三行：第一次交换各结点得左右子树后得先、中、后序遍历序列　
第十四行～第十六行:第二次交换各结点得左右子树后得先、中、后序遍历序列
第十七行：二叉树得深度
第十八行:叶子结点数
＊/
＃ｉnclude ”stdiｏ、ｈ”
＃inｃluｄe　＂malｌｏc、ｈ"
#define TRUE　1
#define　FAＬＳE　0
#define OK 1
＃ｄｅfine　ERRＯR　　0
＃ｄefine INFEＡＳIBＬE -1
＃deｆine OVERFLOW　－2
typedｅf inｔ 　Statｕs;
typeｄef int ＫｅyType；
#deｆine　STＡCK＿IＮIT_SIZE 100 // 存储空间初始分配量
#defｉne　STACKＩNＣREMENＴ　10 //　存储空间分配增量
#dｅfｉne MAXQＳＩZE 100
ｔypedeｆ int ＥlemTｙｐe；
tｙpedｅf struct　ＢiTNｏｄe{
　 ＥlemTｙpe data；
ｓｔrｕcｔ BiTNodｅ ＊lcｈiｌd，*ｒcｈild；/／左右孩子指针
} BiTNode,*ＢiTree;
Sｔatus SearchBST（BiTree　T,KｅyTypｅ ｋeｙ，ＢｉTree ｆ,BiＴree　&p）
｛
iｆ（！T）｛p=f;ｒｅturn ＦＡＬSE;}
elsｅ if（ｋey==T－>dａta){p=T；retuｒn TＲＵＥ;}
elｓｅ　if（key〈T—>ｄａta)retuｒｎ ＳeａｒchBSＴ（T—>lchｉlｄ,kｅy,T,ｐ）;
elsｅ ｒeturn(SeaｒｃhBＳT（T—〉rchild，keｙ,T，p)）；
}
Status InｓertＢSＴ(BiTreｅ　＆T,ElemType e）
｛
BiTree ｓ，p;
　 　iｆ(！SearchBＳT（Ｔ,ｅ,NULL，p))
{
ｓ＝(BｉＴree)malｌoc（siｚｅof(BiTＮodｅ));
ﻩｓ—>daｔa＝e；s－＞lchiｌd=s->rcｈild=NＵLL;
iｆ(！p)T=s；
elｓｅ if(ｅdaｔa）p－〉lchild＝s;
elsｅ ｐ—〉rｃhilｄ=s；
ﻩ rｅｔｕｒn TRUE；
ﻩ}
　elsｅ retuｒn FALSE；
}
Sｔatuｓ　PrintElｅment（ ＥｌｅmTyｐｅ e ） { // 输出元素e得值
ｐriｎtf(＂%d ”, e );
rｅturｎ ＯＫ；
}// PrinｔElemeｎｔ
Staｔus　PreOrdeｒTraverｓe( BiTree T, Status（＊Viｓit)（ElemType） ） {
　 // 前序遍历二叉树Ｔ得递归算法，对每个数据元素调用函数Vｉsiｔ。
　 //补全代码，可用多个语句
　　　 if(Ｔ）
ﻩ{
ﻩ iｆ（ViｓｉtT—〉dａta））
ﻩ ｉf（PrｅＯｒdｅrＴrａveｒｓe（T－>lchｉld，Vｉsit）)
ｉf（ＰrｅOrderTraverse(T—〉rchiｌｄ，Vｉsｉｔ))return OK;
ﻩﻩﻩｒeｔｕrn EＲROＲ；
ﻩ}
ﻩｅlse reｔurｎ　OK;
｝　//　PｒeOｒｄerTravｅrse
Ｓtａtus InＯrdeｒTraverse( BiTreｅ　T, Sｔaｔｕｓ(*Visit)(ElemTyｐe）　)
{
　　 ／/ 中序遍历二叉树T得递归算法，对每个数据元素调用函数Ｖisit.
//补全代码,可用多个语句
ﻩif(T)
{
ﻩif(InOrdeｒTravｅrse(T->lchilｄ，Ｖisit)）
ﻩﻩ ｉf（Ｖｉｓit（T-〉daｔa))
ﻩﻩ if(ＩnOrｄｅrＴraverｓe(Ｔ—＞rchilｄ，Ｖisｉt）)
ﻩﻩﻩ rｅtuｒn OK；
ﻩ ﻩ reｔuｒn ＥＲＲOR；
}
　 ｅlse rｅturn OK；
} //　IｎOｒｄeｒTraｖerse
Ｓtａtus PoｓtOrdｅｒTｒaｖerse（ ＢｉTree　Ｔ， Statuｓ(*Viｓｉｔ）（ＥｌemTyｐｅ）　） {
　 　　// 后序遍历二叉树T得递归算法，对每个数据元素调用函数Ｖｉsｉt
/／补全代码,可用多个语句
ﻩiｆ(Ｔ)
{
　 　 　if(ＰostOrdeｒTraverｓe（T-＞lchiｌd,Visit））
ｉｆ(ＰosｔOrｄｅｒＴraｖｅｒse（Ｔ—>rｃhilｄ，Visit))
ﻩﻩﻩif(Visｉt(Ｔ-＞daｔa)）rｅｔurｎ OＫ;
ﻩﻩﻩreｔurn　ERＲOR；
ﻩ｝
else returｎ　OＫ；
｝ // PostＯrdｅrTraｖerse
Ｓtaｔus　Puｔｏut（ＢiＴreｅ T）
{
PreOrdｅｒTｒaｖｅrse（Ｔ,PrｉntElement）；
ﻩprinｔｆ(＂＼n"）;
ﻩＩnＯｒｄｅrTｒaｖerse(T, PrintElemenｔ);
ｐrintｆ（"\n");
ﻩPoｓtOｒderTraverｓe（T，PrintElement);
　 printｆ（＂＼n”）；
ﻩreｔurｎ OK；
｝
//·······················非递归算法
sｔruｃt SqStａcｋ
{
　 BiTree　＊base; /／ 在栈构造之前与销毁之后,baｓｅ得值为ＮUＬＬ
　BiTreｅ　*toｐ; ／/ 栈顶指针
　　 int staｃksize； ／/ 当前已分配得存储空间,以元素为单位
｝； //　顺序栈
Status IｎiｔＳtack（SqStａck &S） 　
｛　
　 S、baｓｅ=(BｉTree ＊)ｍalloc(STACK＿INIT_SIZＥ*siｚeof（BiＴｒeｅ)）;
if(!Ｓ、ｂａse）retuｒn ERＲOR;
　 　S、top=S、base；
　 Ｓ、sｔacksize=STACK_INIT＿ＳIZE;
retｕrn ＯK;
｝
Staｔuｓ Puｓh（ＳqSｔack ＆Ｓ，BｉTree e)
｛
ｉf（(S、ｔop－S、bａse）〉=S、ｓｔａckｓize)
　 ｛
　 S、ｂase＝(BｉTree＊)reaｌlｏc（S、base，(S、stacｋsiｚe+STACKIＮCREMEＮT）＊sizeoｆ(ＢiＴree））;
ｉｆ（!Ｓ、ｂase）return　ERROR;
　S、tｏp=S、basｅ+Ｓ、stackｓiｚe;
　 　　 　S、stacksize+=STACKINCREMENＴ;
｝
　 *S、tｏp++=e；
return　OK;
}
Stａｔus Pop(SqSｔack ＆Ｓ,BiTｒee ＆e）
｛
　 if(Ｓ、ｔoｐ=＝S、baｓe)retｕrｎ ERRＯＲ;
e＝*—-S、top;
rｅturn ＯK；ﻩ
｝
Sｔａtus　SｔａckEmpｔy（SqＳtack S）
｛ // 若栈S为空栈,则返回TＲＵE，否则返回FAＬSＥ
iｆ（Ｓ、top-Ｓ、base==0)ｒｅｔｕrｎ TRUE；
ｅlsｅ returｎ FＡLSE;
　｝
Statｕs ＩnOrdeｒTrａverｓｅ1（ＢiＴree T,Status(＊Ｖisit）(ElemTｙpe ｅ），SqSｔａｃk　S)
{
BiＴree　p;
InitStａｃk(S）;ｐ=T；
ｗhilｅ（ｐ｜|！ＳtａckEmpty（S))
ﻩ｛
ﻩ if（p)｛Push(S,ｐ）；p=ｐ—〉lchｉlｄ;｝
ﻩ else
ﻩ {
ﻩ ﻩPoｐ(S,p）;
ﻩif（！Ｖisiｔ（p—>daｔａ)）reｔurn ERＲOＲ；
ﻩｐ=p-〉ｒchild；
ﻩﻩ｝
ﻩ｝
ﻩreturn OＫ;
}
//···························层次遍历
tｙpedef sｔruct
{
BiＴrｅe *bａｓe；　/／　初始化得动态分配存储空间
int fｒｏnｔ; /／　头指针，若队列不空,指向队列头元素
　 int rｅar; // 尾指针，若队列不空，指向队列尾元素得下一个位置
}SqQuｅue;
Status InｉtQuｅuｅ(SqQuｅｕe　&Q)
{
　 Ｑ、base=(BｉTｒeｅ*）mａlｌoc(MAXQSIＺＥ*sizeof(BiＴrｅe））;
　 if(!Q、bａｓe）ｒetｕrn ERＲOR；
　　 Q、froｎt=Q、rear=0;
reｔｕrｎ OK;
｝
int QuｅueLengｔｈ（SqQuｅue Q)
{
// 返回Q得元素个数
／/ 请补全代码
　　　reｔｕrｎ(Q、rear-Ｑ、ｆroｎt＋MAXQSIZE）％ＭAXQSIZＥ；ﻩ
｝
Sｔatus ＥnＱueuｅ(SqＱｕeuｅ &Ｑ，BiTree e）
｛　
// 插入元素e为Q得新得队尾元素
／/ 请补全代码
if((Ｑ、ｒear+１）%MＡXQＳIZE＝=Q、ｆront）returｎ ERROR;
Ｑ、base［Q、rear］＝e；
　Ｑ、rｅａr=（Q、rear+1）%MＡXQＳIZE；
　　 return OＫ；
｝
Status DｅQueｕe(ＳqQueuｅ　&Q,BｉTree　&e)
{
// 若队列不空，　则删除Ｑ得队头元素, 用ｅ返回其值, 并返回OK；　否则返回ERROR
//　请补全代码
　 if（Q、ｆｒｏｎt==Q、rear)reｔｕrｎ ERROR；
　　e=Q、ｂase［Q、fｒonｔ］；
　Ｑ、fｒｏnt=（Q、ｆront+1）%MAXＱSＩZE；
ｒｅturn OK；
}
Sｔａtｕs LevｅlＴraveｒse（BiTreｅ T,SｑQuｅue Q）/／层次遍历二叉树
{
ﻩIｎｉtQueｕe(Q）;
ﻩBiTｒee p；
p=Ｔ;
if（T）EnQueue（Q，T）；
// ｐrintｆ（"%ｄ”,ＱueueLenｇｔh（Q）);
wｈｉlｅ（ＱuｅueＬｅｎgth（Q）!=0)
｛
ﻩDｅQueue（Ｑ，ｐ)； /／根结点出队
ｐｒｉntｆ（"％d ＂，p－＞data）； /／输出数据
ｉf（ｐ－〉lcｈild)EnQueue(Q，p－>lchild）; 　/／左孩子进队
ﻩﻩiｆ(p—〉rchild）EnＱueｕe（Ｑ,p->ｒchｉld）；　 /／右孩子进队
ﻩ｝
ﻩreｔuｒn ＯK;
}
voｉd　Ｃhａｎgｅ(BiTree T）
{
ﻩBｉTNode *p;
iｆ(T）
ﻩ｛p=T-〉lchild；
ﻩT－>lchｉlｄ＝Ｔ－〉rcｈild；
T－>ｒcｈｉｌd=p;
ﻩCｈａngｅ（T—>lｃhｉld)；
ﻩChanｇe（T—〉rｃhild)；
｝
　 /／　return OK
｝
ｉnt BTreｅDepｔｈ（BiTｒee Ｔ）
//求由ＢT指针指向得一棵二叉树得深度
{
//ﻩint ｄｅp1,dｅｐ2；
if（Ｔ!＝ＮULL）
｛
/／计算左子树得深度
　 　　　 int ｄｅp1=BTreｅＤepth(T->ｌchilｄ）；
　//计算右子树得深度　　
　　 　 inｔ dｅｐ2=BTｒeeDepｔh（T-〉rchild）;　
　 //返回树得深度　　
　　 ｉf（dｅp1＞deｐ２)
retｕrn dｅp1+１;
　eｌse
ﻩﻩ ｒｅturn　dｅp2＋１;
ﻩ｝
eｌse retuｒn ０;
}　　
//`｀````｀｀`````叶子结点数
Sｔaｔus yezｈｉ（BiＴree T，SqQuｅｕｅ Q）
｛
int i=0；
IｎiｔQueue(Q）；
BｉTree　ｐ；
p＝T;
iｆ(Ｔ）EnQuｅｕｅ(Q,T)；
／/ﻩｐriｎtf（”%ｄ＂,QueｕeLenｇth(Ｑ））；
ﻩwhilｅ(QueueLeｎｇth(Q)！＝0）
｛
ﻩDeQｕeuｅ（Q，p）；
ﻩﻩｉf（ｐ—〉lchｉld)ＥnＱｕeue（Ｑ，p—〉lｃhilｄ）;
ﻩﻩif（p—＞rchｉld）ＥnQueue(Q，p－〉ｒcｈiｌｄ);
ﻩﻩｉf(!p-＞lchild&＆！p－〉rchild)
i++; 　
｝
ｒｅturｎ　i;
｝
inｔ　ｍaｉｎ（） //主函数
{
　 SｑSｔaｃｋ　S;
SqQueuｅ Q，Q３；
ＢiTree　Ｔ=ＮULL,f,p；
ﻩint i，ｎ，e，a，b,c；
ﻩｓcaｎf（＂％d”,&n）；
ﻩfor(ｉ=０;i〈n；i＋+)
{
ﻩﻩscanf(”%d＂,&e）;
　 　 IｎｓerｔBST（Ｔ,e）；
ﻩ｝
sｃanf（"％d＂,&a)scanf(”％d”，&b);scａnf（"％d"，&ｃ）；Putｏut（T)；
ﻩprintｆ（"％ｄ\n",ＳｅaｒchBST（T，ａ,f,p)）;
pｒintf（”％d\n"，ＳearcｈBST(Ｔ,ｂ,f，p））;
ﻩＩnｓｅrtBST(T，c)；
Putoｕｔ(Ｔ)；
ﻩInOrdeｒＴraｖeｒse1（T， PｒｉntＥｌｅment，S）;
　 prｉntｆ("\n")；
ﻩＬevelTraｖerse（T,Q）；
ｐrintf（”\n”）;
　　Chaｎｇe(T）；
Putout（T);
ﻩChａｎge(T);
ﻩPutout（T）；
priｎｔf（”％ｄ"，BTreｅDepｔh(Ｔ）)；
ﻩprintf("＼ｎ＂)；
ｐｒｉnｔf（”％d"，yezhi（T,Q３））；
prinｔf（"\n”）;
rｅturn OＫ;
}//maiｎ