二叉樹求表達式的值.doc

內(nèi)蒙古工業(yè)大學信息工程學院（一）實驗?zāi)康?本實驗以二叉樹的創(chuàng)建與訪問算法設(shè)計作為實驗內(nèi)容，掌握樹型結(jié)構(gòu)的實現(xiàn)方法，培養(yǎng)解決負責問題的能力。（二）實驗內(nèi)容 1、編寫生成二叉樹的函數(shù)， 二叉樹的元素從鍵盤輸入；2、編寫在二叉樹中輸入表達方式的函數(shù)；3、編寫在二叉樹中實現(xiàn)表達方式的值的函數(shù)；4、編寫遍歷并輸出二叉樹的函數(shù)。(三）實驗要求1、掌握樹型結(jié)構(gòu)的機器內(nèi)表示；2、掌握樹型結(jié)構(gòu)之上的算法設(shè)計與實現(xiàn)；3、列表對比分析兩種數(shù)據(jù)結(jié)構(gòu)的相應(yīng)操作的時間復雜度、空間復雜度，闡明產(chǎn)生差異的原因。(四)實驗設(shè)計思路 實驗采用遞歸創(chuàng)建二叉樹的表達,并實現(xiàn)了后序遍歷二叉數(shù)表達式,既逆波蘭表達式的輸出,編寫函數(shù)計算表達式的值,并輸出。對實驗題目進行細分,逐一實現(xiàn)函數(shù)預(yù)期的功能,如下圖，先序輸入創(chuàng)建二叉樹表達式:+*-99#89#2#/66#3#輸出結(jié)果：4+2 /*662399=89 實驗報告(一)部分算法流程圖 1先序創(chuàng)建二叉樹表達式(五)程序清單#include#include#include#define len 20#define NULL 0struct treechar datalen;tree *lchild,*rchild;void createtree(tree *&tre)/創(chuàng)建二叉樹char chlen; scanf(%s,ch);getchar();if(strcmp(ch,#)=0)tre=NULL;else tre=(tree *)malloc(sizeof(tree); strcpy(tre-data,ch); createtree(tre-lchild); createtree(tre-rchild);void inputtree(tree *tre)/輸出二叉樹if(tre!=NULL)printf(%s,tre-data);if(tre-lchild!=NULL|tre-rchild!=NULL)printf();inputtree(tre-lchild);if(tre-rchild!=NULL)printf(,);inputtree(tre-rchild);printf();void traversetree(tree *tre)/后續(xù)遍歷 if(tre!=NULL) traversetree(tre-lchild); traversetree(tre-rchild); printf(%s,tre-data); void inordertravers(tree *tre)/中續(xù)遍歷 if(tre!=NULL) traversetree(tre-lchild); printf(%s,tre-data); traversetree(tre-rchild); double solution(tree *tre)/二叉樹表達式求值if(tre-lchild=NULL&tre-rchild=NULL&tre-data0=0&tre-data0data); elseswitch(tre-data0) case*:return solution(tre-lchild)*solution(tre-rchild); case-:return solution(tre-lchild)-solution(tre-rchild); case+:return solution(tre-lchild)+solution(tre-rchild); case/:returnsolution(tre-lchild)/solution(tre-rchild); int main()tree *tre;double sum; int ch;doprintf(選擇下面功能n);printf(1.先序創(chuàng)建二叉數(shù)表達式 n);printf(2.后序遍利二叉數(shù)表達式 n);printf(3.求二叉數(shù)表達式的數(shù)值 n);printf(4.中序遍利二叉數(shù)表達式 n);printf( 5.退出二叉數(shù) n);printf(n);scanf(%d,&ch);switch(ch) case 1: printf(輸入創(chuàng)建的二叉樹：n);getchar(); createtree(tre);inputtree(tre); printf(n);break; case 2: printf(后序遍歷的二叉樹：n); traversetree(tre);printf(n);break; case 3: sum=solution(tre);printf(二叉樹表達式的值為=%lfn,sum);break; case 4: printf(中序遍歷的二叉樹：n); inordertravers(tre);printf(n);break; case 5: break;while(ch!=5); return 0;（六）實驗結(jié)果選擇下面功能1.先序創(chuàng)建二叉數(shù)表達式2.后序遍利二叉數(shù)表達式3.求二叉數(shù)表達式的數(shù)值4.中序遍利二叉數(shù)表達式 5.退出二叉數(shù)1輸入創(chuàng)建的二叉樹：+*-99#89#2#/66#3#+(*(-(99,89),2),/(66,3)選擇下面功能1.先序創(chuàng)建二叉數(shù)表達式2.后序遍利二叉數(shù)表達式3.求二叉數(shù)表達式的數(shù)值4.中序遍利二叉數(shù)表達式 5.退出二叉數(shù)2后序遍歷的二叉樹：9989-2*663/+選擇下面功能1.先序創(chuàng)建二叉數(shù)表達式2.后序遍利二叉數(shù)表達式3.求二叉數(shù)表達式的數(shù)值4.中序遍利二叉數(shù)表達式 5.退出二叉數(shù)4中序遍歷的二叉樹：9989-2*+663/選擇下面功能1.先序創(chuàng)建二叉數(shù)表達式2.后序遍利二叉數(shù)表達式3.求二叉數(shù)表達式的數(shù)值4.中序遍利二叉數(shù)表達式 5.退出二叉數(shù)3二叉樹表達式的值為=42.000000選擇下面功能1.先序創(chuàng)建二叉數(shù)表達式2.后序遍利二叉數(shù)表達式3.求二叉數(shù)表達式的數(shù)值4.中序遍利二叉數(shù)表達式 5.退出二叉數(shù)5請按任意鍵繼續(xù). . .（七）實驗遇到的問題 二叉樹的遞歸創(chuàng)建只能先序