中綴表達(dá)式生成二叉樹(shù)，大概應(yīng)該有遞規(guī)，迭代，和編譯原理中的自頂向下的預(yù)測(cè)分析法等。

遞規(guī)，迭代的思路每次讀出一個(gè)數(shù)字，一個(gè)運(yùn)算符，比較當(dāng)前運(yùn)算符和之前符號(hào)的優(yōu)先級(jí)，進(jìn)行相關(guān)的操作。

自頂向下的預(yù)測(cè)分析法，做了下，實(shí)在忘記的差不多了，先占個(gè)位。以后完成。

?

tree.c

#include "head.h"struct Node * CreateNodesetV(int number,char opr,int type) {struct nodeData db;db.numberValue=number;db.operatorValue=opr;db.symbolType=type;struct Node * myNode=malloc(sizeof(struct Node));CreateNode(db,myNode);return myNode; };void CreateNode(struct nodeData nd,struct Node * myN) {myN->NData.numberValue=nd.numberValue;myN->NData.operatorValue=nd.operatorValue;myN->NData.symbolType=nd.symbolType;myN->lchilden='\0';myN->rchilden='\0'; };char insertNode(struct Node * myNode,struct Node * father,char lr) {char result='Y';if(lr=='L'){if(father->lchilden=='\0'){father->lchilden=myNode;}else{result='N';}}else{if(father->rchilden=='\0'){father->rchilden=myNode;}else{result='N';}}return result; }//原來(lái)樹(shù)的遍歷也就是遞歸.我去,我說(shuō)自己怎么老是不得要領(lǐng).根源在于沒(méi)想明白遞歸函數(shù). void visitTree(struct Node * Root) {if(Root->lchilden!='\0'){visitTree(Root->lchilden);}else{//終止遞歸的確定事件,是無(wú)事件. }if(Root->NData.symbolType==1){printf("%d",Root->NData.numberValue);}else{printf("%c",Root->NData.operatorValue);}if(Root->rchilden!='\0'){visitTree(Root->rchilden);}else{//終止遞歸的確定事件,是無(wú)事件. } }

//所以如果用遞歸來(lái)做運(yùn)算必須是后序遍歷，要等左右樹(shù)都有結(jié)果了，才用符號(hào)。 //其實(shí)我們的心算和筆算，也是后續(xù)遍歷。int visitTree_2(struct Node * Root) {int lvalue;int rvalue;int result;if(Root->lchilden!='\0'){lvalue=visitTree_2(Root->lchilden);}else{return Root->NData.numberValue;}if(Root->rchilden!='\0'){rvalue=visitTree_2(Root->rchilden);}else{return Root->NData.numberValue;}switch (Root->NData.operatorValue){case '+':{result=lvalue+rvalue;break;}case '-':{result=lvalue-rvalue;break;}case '*':{result=lvalue*rvalue;break;}case '/':{result=lvalue/rvalue;break;}}return result; }

?

head.h

?

//treestruct nodeData {int symbolType; //1: number 2: operatorint numberValue;char operatorValue; };struct Node {struct nodeData NData;struct Node * lchilden;struct Node * rchilden; };char insertNode(struct Node * myNode,struct Node * father,char lr); struct Node * CreateNodesetV(int number,char opr,int type); void CreateNode(struct nodeData nd,struct Node * myN); void visitTree(struct Node * Root);

?

1）迭代方法

main.c

　　基本思路就是我們手工畫(huà)圖的步驟。寫(xiě)成代碼而已。

每次取一個(gè)數(shù)字和操作符，對(duì)比操作符和之前操作符的優(yōu)先順序。狀1，大于，則符號(hào)為之前樹(shù)的右子樹(shù)，數(shù)字為符號(hào)的左子樹(shù)。狀2，小于，則數(shù)字為之前樹(shù)的右字樹(shù)，之前樹(shù)為符號(hào)的左子樹(shù)。 直至最后，只有一個(gè)數(shù)字符，此數(shù)字為之前符號(hào)的右子樹(shù)， int main() {char * expression="2+3*5-4/2";//每次取一個(gè)數(shù)字和操作符，對(duì)比操作符和之前操作符的優(yōu)先順序。//狀1，大于，則符號(hào)為之前樹(shù)的右子樹(shù)，數(shù)字為符號(hào)的左子樹(shù)。//狀2，小于，則數(shù)字為之前樹(shù)的右字樹(shù)，之前樹(shù)為符號(hào)的左子樹(shù)。//直至最后，只有一個(gè)數(shù)字符，此數(shù)字為之前符號(hào)的右子樹(shù)，char preOpe='#';struct Node * PreNode='\0';struct Node * RootNode='\0';int i=0;int strLen=getStrLen(expression);while(i<strLen){if(i==0)// {int cNumber=expression[i]-48;i++;char cOperator=expression[i];i++;struct Node * LeftC=CreateNodesetV(cNumber,' ',1);struct Node * Root=CreateNodesetV(0,cOperator,2);insertNode(LeftC,Root,'L');preOpe=cOperator;PreNode=Root;RootNode=Root;}else{if(i+2<strLen)//get a number and operator {int cNumber=expression[i]-48;i++;char cOperator=expression[i];i++;if(lHeight(preOpe,cOperator)==1){struct Node * numberNode=CreateNodesetV(cNumber,' ',1);struct Node * OpeNode=CreateNodesetV(0,cOperator,2);insertNode(OpeNode,PreNode,'R');insertNode(numberNode,OpeNode,'L');preOpe=cOperator;PreNode=OpeNode;}else if (lHeight(preOpe,cOperator)==0){struct Node * numberNode=CreateNodesetV(cNumber,' ',1);struct Node * OpeNode=CreateNodesetV(0,cOperator,2);insertNode(RootNode,OpeNode,'L');insertNode(numberNode,PreNode,'R');preOpe=cOperator;PreNode=OpeNode;RootNode=OpeNode;}}else//last char {int cNumber=expression[i]-48;i++;struct Node * numberNode=CreateNodesetV(cNumber,' ',1);insertNode(numberNode,PreNode,'R');}}}if(RootNode!='\0'){visitTree(RootNode);printf("\nresult:%d",visitTree_2(RootNode));}return 0; }int getStrLen(char * c) {int i=0;while(c[i]!='\0'){i++;}return i; }int lHeight(char oldc,char newl) {if(oldc=='+'||oldc=='-'){if(newl=='*'||newl=='/'){return 1;}}else if(oldc=='#'){return 1;}return 0; }

?

2） 遞規(guī)方式。

? ? ?尾遞規(guī)一般是可以用循環(huán)迭代來(lái)表示。所以這里遞規(guī)其實(shí)并不是很體現(xiàn)優(yōu)勢(shì)。

　　只是可以鍛煉下遞規(guī)的思路，遞規(guī)是：把問(wèn)題難度逐層降低，以至到達(dá)某個(gè)層次（一般0或1），是個(gè)確定的操作不需要遞規(guī)，那么這個(gè)層次的上層的操作也變成了確定操作。以至最終解決問(wèn)題。

　　這里一樣的思路：一個(gè)表達(dá)式很長(zhǎng)，我只能解決一個(gè)數(shù)字，一個(gè)操作符，并把他放到之前的樹(shù)上。剩下的表達(dá)式也就是遺留的問(wèn)題讓下層去做。下層能做的事和上面一樣。以至到最后，只剩下一個(gè)數(shù)字，只能防到右葉，遺留的問(wèn)題，到這里終結(jié)。

mian.c

void CreateTree(char * expression,struct Node * PreNode,char preOpe); struct Node * Root='\0'; int main() {char * expression="2+3*5-4/2";char preOpe='#';struct Node * PreNode='\0';int strLen=getStrLen(expression);CreateTree(expression,PreNode,preOpe);if(Root!='\0'){visitTree(Root);printf("\nresult:%d",visitTree_2(Root));}return 0; }void CreateTree(char * expression,struct Node * PreNode,char preOpe) {int strLen=getStrLen(expression);if(strLen>1){int cNumber=expression[0]-48;char cOperator=expression[1];if(lHeight(preOpe,cOperator)==1){struct Node * numberNode=CreateNodesetV(cNumber,' ',1);struct Node * OpeNode=CreateNodesetV(0,cOperator,2);if(preOpe!='#'){insertNode(OpeNode,PreNode,'R');insertNode(numberNode,OpeNode,'L');preOpe=cOperator;PreNode=OpeNode;}else{insertNode(numberNode,OpeNode,'L');preOpe=cOperator;PreNode=OpeNode;Root=OpeNode;}}else if (lHeight(preOpe,cOperator)==0){struct Node * numberNode=CreateNodesetV(cNumber,' ',1);struct Node * OpeNode=CreateNodesetV(0,cOperator,2);insertNode(Root,OpeNode,'L');insertNode(numberNode,PreNode,'R');preOpe=cOperator;PreNode=OpeNode;Root=OpeNode;}CreateTree(expression+2,PreNode,preOpe);}else{int cNumber=expression[0]-48;struct Node * numberNode=CreateNodesetV(cNumber,' ',1);insertNode(numberNode,PreNode,'R');} }

3）自頂向下的預(yù)測(cè)分析。

? ? 做了下，沒(méi)出來(lái)。以后看看。

轉(zhuǎn)載于:https://www.cnblogs.com/lsfv/p/5516278.html

總結(jié)

以上是生活随笔為你收集整理的中缀表达式生成二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。