實(shí)驗6：二叉樹及其應(yīng)用一、實(shí)驗?zāi)康臉涫菙?shù)據(jù)結(jié)構(gòu)中應(yīng)用極為廣泛的非線性結(jié)構(gòu)，本單元的實(shí)驗到達(dá)熟悉二叉樹的存儲結(jié)構(gòu)的特性，以及如何應(yīng)用樹結(jié)構(gòu)解決具體問題。二、問題描述首先，掌握二叉樹的各種存儲結(jié)構(gòu)和熟悉對二叉樹的根本操作。其次，以二叉樹表示算術(shù)表達(dá)式的根底上，設(shè)計一個十進(jìn)制的四那么運(yùn)算的計算器。--+/a*b-efCd如算術(shù)表達(dá)式：a+b*(c-d)-e/f三、實(shí)驗要求如果利用完全二叉樹的性質(zhì)和二叉鏈表結(jié)構(gòu)建立一棵二叉樹，分別計算統(tǒng)計葉子結(jié)點(diǎn)的個數(shù)。求二叉樹的深度。十進(jìn)制的四那么運(yùn)算的計算器可以接收用戶來自鍵盤的輸入。由輸入的表達(dá)式字符串動態(tài)生成算術(shù)表達(dá)式所對應(yīng)的二叉樹。自動完成求值運(yùn)算和輸出結(jié)果。四、實(shí)驗環(huán)境PC微機(jī)DOS操作系統(tǒng)或Windows操作系統(tǒng)TurboC程序集成環(huán)境或VisualC++程序集成環(huán)境五、實(shí)驗步驟1、根據(jù)二叉樹的各種存儲結(jié)構(gòu)建立二叉樹；2、設(shè)計求葉子結(jié)點(diǎn)個數(shù)算法和樹的深度算法；3、根據(jù)表達(dá)式建立相應(yīng)的二叉樹，生成表達(dá)式樹的模塊；4、根據(jù)表達(dá)式樹，求出表達(dá)式值，生成求值模塊；5、程序運(yùn)行效果，測試數(shù)據(jù)分析算法。設(shè)計程序代碼如下：#include<stdio.h>#include<malloc.h>#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineERROR0#defineNUMBER1#defineSIMBLE2intOP[8]={'+','-','*','/','(',')','#',0};typedefunion{ intOperator;//操作符 floatOperand;//操作數(shù) }Int_Float;//表達(dá)式樹typedefstructBinaryTreeNode{ Int_FloatData; intIsOperator; structBinaryTreeNode*RChild; structBinaryTreeNode*LChild;}BiTreeNode,*lpBiTreeNode;//棧typedefstruct{ lpBiTreeNode*base; lpBiTreeNode*top; intstacksize;}SqStack;intInitStack(SqStack&s){ s.base=(lpBiTreeNode*)malloc(STACK_INIT_SIZE*sizeof(lpBiTreeNode)); if(!s.base) return0; s.top=s.base; s.stacksize=STACK_INIT_SIZE; return1;}intPush(SqStack&s,lpBiTreeNodee){ if(s.top-s.base>=s.stacksize) { s.base=(lpBiTreeNode*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(lpBiTreeNode)); if(!s.base) return0; s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT; } *s.top=e; s.top++; return1;}intPop(SqStack&s,lpBiTreeNode&e){ if(s.top==s.base) return0; s.top--; e=*s.top; return1;}lpBiTreeNodeGetTop(SqStacks){ lpBiTreeNodee; if(s.top==s.base) returnNULL; e=*(s.top-1); returne;}intIsEmpty(SqStacks){ if(s.top==s.base) return1; else return0;}intIn(intc,int*op)//判斷c是否在op中，op為以結(jié)尾的數(shù)組{ while(*op!=0) { if(c==*op) return1; op++; } return0;}intPrecede(inttheta1,inttheta2){ inti,j; intop_look[7][7]= { {'>','>','<','<','<','>','>'}, {'>','>','<','<','<','>','>'}, {'>','>','>','>','<','>','>'}, {'>','>','>','>','<','>','>'}, {'<','<','<','<','<','=',''}, {'>','>','>','>','','>','>'}, {'<','<','<','<','<','','='} }; switch(theta1) { case'+': i=0; break; case'-': i=1; break; case'*': i=2; break; case'/': i=3; break; case'(': i=4; break; case')': i=5; break; case'#': i=6; break; default: return0; } switch(theta2) { case'+': j=0; break; case'-': j=1; break; case'*': j=2; break; case'/': j=3; break; case'(': j=4; break; case')': j=5; break; case'#': j=6; break; default: return0; } returnop_look[i][j];}intisNum(intc){ if(c>='0'&&c<='9') return1; elsereturn0;}intGetInput(Int_Float*Result)//返回值：無，1數(shù)字，2符號{ staticintbuffer=0;//緩存存儲數(shù)字后的符號 intc; Int_Floatresult; intIsNumber=0;//是否為數(shù)字 intIsFloat=0;//是否為小數(shù) inti,t=1; result.Operand=0; if(In(buffer,OP))//緩存中有符號，返回 { result.Operator=buffer; buffer=0; Result->Operator=result.Operator; returnSIMBLE;//符號 }//去前導(dǎo)空格 c=getchar(); while(c==''&&c!=10) { c=getchar(); } while(c!=''&&c!=10)//不是空格和回車 { if(isNum(c))//是數(shù)字 { IsNumber=1; c=c-48;//字符到整型 if(IsFloat==0) result.Operand=result.Operand*10+c; else { result.Operand=result.Operand*10+c; IsFloat++; } } elseif(c=='.') { if(IsFloat!=0) //兩個小數(shù)點(diǎn) { Result->Operand=0; returnERROR; } else IsFloat=1; } elseif(In(c,OP)) { if(IsNumber)//數(shù)字后接符號 { if(IsFloat==1) { Result->Operand=0; returnERROR; } else { buffer=c; for(i=0;i<IsFloat-1;i++) t*=10; Result->Operand=result.Operand/(float)t; returnNUMBER;//數(shù)字 } } else { Result->Operator=c; returnSIMBLE;//符號 } } c=getchar(); } buffer=0; if(IsNumber) { if(IsFloat==1) { Result->Operand=0; returnERROR; } else { for(i=0;i<IsFloat-1;i++) t*=10; Result->Operand=result.Operand/(float)t; returnNUMBER; } } elseif(result.Operand==0) { Result->Operand=0; returnERROR; } else { Result->Operator=result.Operator; returnSIMBLE; }}lpBiTreeNodeCreateBiTree(){ SqStackOperand;//操作數(shù) SqStackOperator;//操作符 lpBiTreeNodepNode; lpBiTreeNodetheta,a,b; Int_Floatc; printf("輸入算式，以'#'結(jié)尾\n"); intr=GetInput(&c); InitStack(Operand); InitStack(Operator); pNode=(lpBiTreeNode)malloc(sizeof(BiTreeNode)); pNode->Data.Operator='#'; pNode->IsOperator=1; pNode->LChild=NULL; pNode->RChild=NULL; Push(Operator,pNode); while(!(r==SIMBLE&&c.Operator=='#')||GetTop(Operator)->Data.Operator!='#') { if(r==ERROR) returnNULL; if(r==NUMBER)//是數(shù)字 { pNode=(lpBiTreeNode)malloc(sizeof(BiTreeNode)); pNode->Data.Operand=c.Operand; pNode->IsOperator=0; pNode->LChild=NULL; pNode->RChild=NULL; Push(Operand,pNode); r=GetInput(&c); } elseif(r==SIMBLE)//是符號 { switch(Precede(GetTop(Operator)->Data.Operator,c.Operator)) { case'<'://棧頂元素優(yōu)先權(quán)低 pNode=(lpBiTreeNode)malloc(sizeof(BiTreeNode)); pNode->Data.Operator=c.Operator; pNode->IsOperator=1; pNode->LChild=NULL; pNode->RChild=NULL; Push(Operator,pNode); r=GetInput(&c); break; case'='://'(',')'相遇，脫括號 Pop(Operator,pNode); r=GetInput(&c); break; case'>'://棧頂元素優(yōu)先權(quán)高,退棧并將運(yùn)算結(jié)果入棧 Pop(Operator,theta); Pop(Operand,b); Pop(Operand,a); theta->LChild=a; theta->RChild=b; Push(Operand,theta); break; } } } returnGetTop(Operand);}boolcalculate(lpBiTreeNodeRoot,float*result){ floatresultLchild; floatresultRchild; if(Root!=NULL) { if(Root->LChild==NULL&&Root->RChild==NULL) { *result=Root->Data.Operand; returntrue; } elseif(Root->LChild==NULL||Root->RChild==NULL) returnfalse; else { switch(Root->Data.Operator) { case'+': if(calculate(Root->LChild,&resultLchild)==false) returnfalse; if(calculate(Root->RChild,&resultRchild)==false) returnfalse; *result=resultLchild+resultRchild; break; case'-': if(calculate(Root->LChild,&resultLchild)==false) returnfalse; if(calculate(Root->RChild,&resultRchild)==false) returnfalse; *result=resultLchild-resultRchild; break; case'*': if(calculate(Root->LChild,&resultLchild)==false) returnfalse; if(calculate(Root->RChild,&resultRchild)==false) returnfalse; *result=resultLchild*resultRchild; break; case'/': if(calculate(Root->LChild,&resultLchild)==false) returnfalse; if(calculate(Root->RChild,&resultRchild)==false) returnfalse; *result=resultLchild/resultRchild; break; } } } returntrue;}intgetLeafNum(lpBiTreeNodeRoot){ intLeafnumLchild; intLeafnumRchild; if(Root!=NULL) { if(Root->LChild==NULL&&Root->RChild==NULL) return1; else { LeafnumLchild=getLeafNum(Root->LChild); LeafnumRchild=getLeafNum(Root->RChild); returnLeafnumLchild+LeafnumRchild; } } return0;}intgetDepth(lpBiTreeNodeRoot){ intLeafDepthL; intLeafDepthR; if(Root!=NULL) { if(Root->LChild==NULL&&Root->RChild==NULL) return0; else { LeafDepthL=getDepth(Root->LChild); LeafDepthR=getDepth(Root->RChil