二叉树的所有算法C语言.docx
《二叉树的所有算法C语言.docx》由会员分享，可在线阅读，更多相关《二叉树的所有算法C语言.docx（14页珍藏版）》请在冰点文库上搜索。
二叉树的所有算法C语言
二叉树的所有算法（C语言）
实验6
实验目的:
1、掌握二叉树的所有算法
2、熟悉计算机英语和术语
实验步骤:
1、二叉树算法的模拟
2、完型填空
3、翻译
具体要求:
一、设计一个完整的程序，实现二叉树的各种算法要求:
/*用函数实现如下二叉排序树算法:
（1）插入新结点
（2）前序、中序、后序遍历二叉树（3）中序遍历的非递归算法
（4）层次遍历二叉树
（5）在二叉树中查找给定关键字（函数返回值为成功1,失败0）
（6）交换各结点的左右子树
（7）求二叉树的深度
（8）叶子结点数
输入:
第一行:
准备建树的结点个数n
第二行:
输入n个整数，用空格分隔第三行:
输入待查找的关键字
第四行:
输入待查找的关键字
第五行:
输入待插入的关键字
输出:
第一行:
二叉树的先序遍历序列
第二行:
二叉树的中序遍历序列
第三行:
二叉树的后序遍历序列
第四行:
查找结果
第五行:
查找结果
第六行~第八行:
插入新结点后的二叉树的先、中、序遍历序列
第九行:
插入新结点后的二叉树的中序遍历序列（非递归算法）
代码:
#include"stdio.h"#include"malloc.h"#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;typedefintKeyType;
#defineSTACK_INIT_SIZE100//存储空间初始分配量
#defineSTACKINCREMENT10//存储空间分配增量
#defineMAXQSIZE100
typedefintElemType;
typedefstructBiTNode{
ElemTypedata;
structBiTNode*lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
StatusSearchBST（BiTreeT,KeyTypekey,BiTreef,BiTree&p）
{
if（!
T）{p=f;returnFALSE;}
elseif（key==T->data）{p=T;returnTRUE;}
elseif（keydata）returnSearchBST（T->lchild,key,T,p）;
elsereturn（SearchBST（T->rchild,key,T,p））;}
StatusInsertBST（BiTree&T,ElemTypee）{
BiTrees,p;
if（!
SearchBST（T,e,NULL,p））
{
s=（BiTree）malloc（sizeof（BiTNode））;
s->data=e;s->lchild=s->rchild=NULL;
if（!
p）T=s;
elseif（edata）p->lchild=s;
elsep->rchild=s;
returnTRUE;
}
elsereturnFALSE;
}
StatusPrintElement（ElemTypee）{//输出元素e的值
printf（"%d",e）;
returnOK;
}//PrintElement
StatusPreOrderTraverse（BiTreeT,Status（*Visit）（ElemType））{
//前序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。
//补全代码,可用多个语句
if（T）
{
if（Visit（T->data））
if（PreOrderTraverse（T->lchild,Visit））
if（PreOrderTraverse（T->rchild,Visit））returnOK;
returnERROR;
}
elsereturnOK;
}//PreOrderTraverse
StatusInOrderTraverse（BiTreeT,Status（*Visit）（ElemType））
{
//中序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。
//补全代码,可用多个语句
if（T）
{
if（InOrderTraverse（T->lchild,Visit））
if（Visit（T->data））
if（InOrderTraverse（T->rchild,Visit））
returnOK;
returnERROR;
}
elsereturnOK;
}//InOrderTraverse
StatusPostOrderTraverse（BiTreeT,Status（*Visit）（ElemType））{
//后序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。
//补全代码,可用多个语句
if（T）
{
if（PostOrderTraverse（T->lchild,Visit））
if（PostOrderTraverse（T->rchild,Visit））
if（Visit（T->data））returnOK;
returnERROR;
}
elsereturnOK;
}//PostOrderTraverse
StatusPutout（BiTreeT）
{
PreOrderTraverse（T,PrintElement）;
printf（"\n"）;
InOrderTraverse（T,PrintElement）;
printf（"\n"）;
PostOrderTraverse（T,PrintElement）;
printf（"\n"）;
returnOK;
}
//?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
非递归算法
structSqStack
{
BiTree*base;//在栈构造之前和销毁之后，base的值为NULL
BiTree*top;//栈顶指针
intstacksize;//当前已分配的存储空间，以元素为单位
};//顺序栈
StatusInitStack（SqStack&S）{
S.base=（BiTree*）malloc（STACK_INIT_SIZE*sizeof（BiTree））;
if（!
S.base）returnERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}
StatusPush（SqStack&S,BiTreee）{
if（（S.top-S.base）>=S.stacksize）
{
S.base=（BiTree*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（BiTree））;
if（!
S.base）returnERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
returnOK;
}
StatusPop（SqStack&S,BiTree&e）{
if（S.top==S.base）returnERROR;
e=*--S.top;
returnOK;
}
StatusStackEmpty（SqStackS）
{//若栈S为空栈，则返回TRUE，否则返回FALSE
if（S.top-S.base==0）returnTRUE;
elsereturnFALSE;
}
StatusInOrderTraverse1（BiTreeT,Status（*Visit）（ElemTypee）,SqStackS）
{
BiTreep;
InitStack（S）;p=T;
while（p||!
StackEmpty（S））
{
if（p）{Push（S,p）;p=p->lchild;}
else
{
Pop（S,p）;
if（!
Visit（p->data））returnERROR;
p=p->rchild;
}
}
returnOK;
}
//?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
层次遍历
typedefstruct
{
BiTree*base;//初始化的动态分配存储空间
intfront;//头指针,若队列不空,指向队列头元素
intrear;//尾指针,若队列不空,指向队列尾元素的下一个位置
}SqQueue;
StatusInitQueue（SqQueue&Q）{
Q.base=（BiTree*）malloc（MAXQSIZE*sizeof（BiTree））;
if（!
Q.base）returnERROR;
Q.front=Q.rear=0;
returnOK;
}
intQueueLength（SqQueueQ）{
//返回Q的元素个数
//请补全代码
return（Q.rear-Q.front+MAXQSIZE）%MAXQSIZE;
}
StatusEnQueue（SqQueue&Q,BiTreee）{
//插入元素e为Q的新的队尾元素
//请补全代码
if（（Q.rear+1）%MAXQSIZE==Q.front）returnERROR;
Q.base[Q.rear]=e;
Q.rear=（Q.rear+1）%MAXQSIZE;
returnOK;
}
StatusDeQueue（SqQueue&Q,BiTree&e）{
//若队列不空,则删除Q的队头元素,用e返回其值,并返回OK;否则返回ERROR
//请补全代码
if（Q.front==Q.rear）returnERROR;
e=Q.base[Q.front];
Q.front=（Q.front+1）%MAXQSIZE;
returnOK;
}
StatusLevelTraverse（BiTreeT,SqQueueQ）//层次遍历二叉树
{
InitQueue（Q）;
BiTreep;
p=T;
if（T）EnQueue（Q,T）;
//printf（"%d",QueueLength（Q））;
while（QueueLength（Q）!
=0）
{
DeQueue（Q,p）;//根结点出队
printf（"%d",p->data）;//输出数据
if（p->lchild）EnQueue（Q,p->lchild）;//左孩子进队
if（p->rchild）EnQueue（Q,p->rchild）;//右孩子进队
}
returnOK;
}
voidChange（BiTreeT）
{
BiTNode*p;
if（T）
{p=T->lchild;
T->lchild=T->rchild;
T->rchild=p;
Change（T->lchild）;
Change（T->rchild）;
}
//returnOK;
}
intBTreeDepth（BiTreeT）
//求由BT指针指向的一棵二叉树的深度{
//intdep1,dep2;
if（T!
=NULL）
{
//计算左子树的深度
intdep1=BTreeDepth（T->lchild）;
//计算右子树的深度
intdep2=BTreeDepth（T->rchild）;
//返回树的深度
if（dep1>dep2）
returndep1+1;
else
returndep2+1;
}
elsereturn0;
}
//`````````````叶子结点数
Statusyezhi（BiTreeT,SqQueueQ）
{
inti=0;
InitQueue（Q）;
BiTreep;
p=T;
if（T）EnQueue（Q,T）;//printf（"%d",QueueLength（Q））;
while（QueueLength（Q）!
=0）
{
DeQueue（Q,p）;
if（p->lchild）EnQueue（Q,p->lchild）;
if（p->rchild）EnQueue（Q,p->rchild）;
if（!
p->lchild&&!
p->rchild）
i++;
}
returni;
}
intmain（）//主函数
{
SqStackS;
SqQueueQ,Q3;
BiTreeT=NULL,f,p;
inti,n,e,a,b,c;
scanf（"%d",&n）;
for（i=0;i{
scanf（"%d",&e）;
InsertBST（T,e）;
}
scanf（"%d",&a）;scanf（"%d",&b）;
scanf（"%d",&c）;Putout（T）;
printf（"%d\n",SearchBST（T,a,f,p））;
printf（"%d\n",SearchBST（T,b,f,p））;
InsertBST（T,c）;
Putout（T）;
InOrderTraverse1（T,PrintElement,S）;
printf（"\n"）;
LevelTraverse（T,Q）;
printf（"\n"）;
Change（T）;
Putout（T）;
Change（T）;
Putout（T）;
printf（"%d",BTreeDepth（T））;
printf（"\n"）;
printf（"%d",yezhi（T,Q3））;
printf（"\n"）;
returnOK;
}//main
完型填空
TherearemanykindsofComputerlanguages.Atypicalimperativelanguagecontainsan
（1）_sublanguagewhichapproximatesthemathematicalabstractionsof"timeless"functionsappliedto"space-less"values,wheretheactualoperationsequencesanduseOf
storagespaceduring
expressionevaluationareorganizedbehindthe
（2）.
Inthissetting,valuesaredatastructuresoflowvolume,typicallyafewcomputerwordsorless,whichmeansthatanillusionof（3）
canberealizedbyhavingintermediate
re-suitsduringexpressionevalutionstoredatthe
discretionofthelanguageimplementation,and
effectingpa-rameter（4）and（5）operationsthroughvaluecopying.
（1）A.applicativeB.mandatory
C.applicationD.voluntary
（2）A.screenB.background
C.foregroundD.scenes
（3）A.spacefulB.spacelessness
C.spacelessD.space
（4）A.transportationB.tranverse
C.transmissionD.translation
（5）A.assignmentB.dispatch
C.valueD.design
四翻译
QueryByExample（QBE）
Indatabasemanagementprograms,aquerytechnique,developedbyIBMforuseintheQBEprogram,thatpromptsyoutotypethesearchcriteriaintoatemplateresemblingthedatarecord.Theadvantageofquery-by-exampleretrievalisthatyoudon’tneedtolearnaquerylanguagetoframeaquery.Whenyoustartthesearch,theprogrampresentsascreenthatlistsallthedatafieldsthatappearoneverydatarecord;enterinformationthatrestrictsthesearchtojustthespecifiedcriteria.The
fieldsliftbland,however,willmatchanything.
QueryLanguage
Indatabasemanagementprograms,aretrievalanddata-editinglanguageyouusetospecifywhatinformationtoretrieveandhowtoarrangetheretrievedinformationon-screenorwhenprinting.Thedot-promptlanguageofdBASEisafull-fledgedquerylanguage,asisStructuredQueryLanguage（SQL）,whichisusedforminicomputerandmainframedatabasesandisgrowinginpopularityintheworldofpersonalcomputers.Theidealquerylanguageisanaturallanguage,suchasEnglish.ARPAnet
Awideareanetwork（WAN）.AnetworkthatconnectedDepartmentofDefenseresearchsitesacrossAmerica.Createdin1969withfundingfromtheAdvancedResearchProjectsAgency（ARPA）.Undergoingconstantresearchanddevelopmentintheearly-tomid-1970s,ARPAnetservedasthetestbedforthedevelopmentofTCP/IP（theprotocolsthatmaketheInternetpossible）.AMajorgoaloftheARPAnetprojectwastoincreasethemilitary'scommandandcontrolcapabilitybyenablingcommunicationacrossavarietyofphysicallydissimilarmedia,includingsatellites.Analliedgoalwastocreatearobust
networkcapableofwithstandingoutages,suchasthosethatmightresultfromanuclearexchange.ARPAnetmettheseobjectives,butitalsosurpriseditscreators:
ItwasfoundinshortorderthatmostARPAnetuserspreferredtousethenetwork
forcommunication,suchaselectronicmailanddiscussiongroups.Initially,theARPAnetwasavailableonlytogovernmentresearchinstitutesandtouniversitiesholdingDepartmentofDefense（DoD）researchcontracts.In1983,ARPAnetwasdividedintoahigh-securitymilitarynetwork（Milnet）andanARPAnetthatwasrecastasaresearchanddevelopmentnetwork.AlthoughitformedthefoundationoftheInternet,itwasdecommissionedin1990.
升级会员 