算法與數(shù)據(jù)結(jié)構(gòu)實驗報告二叉樹實驗報告

1、算法與數(shù)據(jù)結(jié)構(gòu)實驗報告二叉樹課程名稱：算法與數(shù)據(jù)結(jié)構(gòu)實驗項目名稱：滿二叉樹的建立與遍歷實驗時間：2014年11月29日班級：電科1301姓名：侯煒 學(xué)號：1402130126實驗?zāi)康模菏煜な褂镁€性表結(jié)構(gòu)，設(shè)計并理解多項式算法。實驗環(huán)境：Visual C+6.0，win7實驗步驟：1 建立基本數(shù)據(jù)結(jié)構(gòu)及程序架構(gòu)2 設(shè)計多項式各類操作的算法3 調(diào)試程序，修改錯誤4 總結(jié)得失實驗結(jié)果：成功使用中序輸入建立二叉樹并進行相應(yīng)的遍歷輸出。實驗心得： 隊列結(jié)構(gòu)作用之一：用于儲存“臨時數(shù)據(jù)”以便后續(xù)輸出 滿二叉樹是僅僅輸入一次遍歷順序就得出結(jié)果的先決條件具體實驗步驟：1 建立基本數(shù)據(jù)結(jié)構(gòu)及程序架構(gòu)1.1數(shù)據(jù)結(jié)

2、構(gòu)確定所需要的對二叉樹進行抽象的數(shù)據(jù)類型：樹節(jié)點。建立數(shù)據(jù)結(jié)構(gòu)如下：/-數(shù)據(jù)結(jié)構(gòu)typedef struct treenodechar data;struct treenode* ltree;struct treenode* rtree;Tnode;/-1.2主程序架構(gòu)建立了一個全局變量數(shù)組queue用作隊列，函數(shù)指針fp用以調(diào)用操作函數(shù)，scree100數(shù)組用以儲存輸入的字符串。主要函數(shù)聲明如下：/-Tnode* finit(Tnode*tf,int flo);/中序建立void transver(Tnode* tf,int flo,fp kf,int n);/層序遍歷 tf為樹節(jié)點 flo

3、為層數(shù) kf為回調(diào)函數(shù) n為標(biāo)識層數(shù)：0為全部遍歷 其他n為輸出第n層void ordtra(Tnode* tf,fp kf,int flo);/先序遍歷void follow(Tnode* tf,fp kf,int flo);/后序遍歷Tnode*pus_pop(Tnode*tf,int k);/隊列操作函數(shù)：k=0時為出隊 1為入隊int ana(char sz);/分析二叉樹層數(shù)void visit(Tnode*k);/回調(diào)訪問函數(shù)int ifpopcorn();/判斷隊列是否為空（未用）void inintque();/初始化隊列int flag(int n,int i);/層數(shù)顯示標(biāo)

4、記主函數(shù)階段，循環(huán)顯示主界面：建立多項式、多項式操作以及顯示多項式?！据斎敫袷健浚航⒍鏄洌憾鏄鋽?shù)據(jù)：按中序遍歷順序輸入（只支持滿二叉樹）輸出某一層：輸入層數(shù)，按回車即可。二設(shè)計算法2.1 建立二叉樹評價： 處理scree存儲的中序輸入的字符串，實現(xiàn)思想：以中序遍歷的方法，遞歸建立。代碼如下：Tnode* finit(Tnode* tf,int flo)/中序建立if(!flo)return NULL;if(*scree='0')return NULL;tf=(Tnode*)malloc(sizeof(Tnode);/為當(dāng)前節(jié)點申請空間tf->ltree=finit(

5、tf->ltree,flo-1);/遞歸 中序是先左再中后右tf->data=*printc;/賦值 printc為指向scree字符串（輸入的中序序列）printc+;/指針后移tf->rtree=finit(tf->rtree,flo-1);/遞歸return tf;/返回樹節(jié)點2.2遍歷算法評價：利用遞歸算法遍歷。算法思想：遞歸。實現(xiàn)代碼如下：void ordtra(Tnode* tf,fp kf,int flo)/先序遍歷/printf("%c",tf->data);if(!tf|!flo)return;kf(tf);/回調(diào)函數(shù)（其實就

6、是printf()）ordtra(tf->ltree,visit,flo-1);ordtra(tf->rtree,visit,flo-1);void follow(Tnode* tf,fp kf,int flo)/后序遍歷/printf("%c",tf->data);if(!tf|!flo)return;follow(tf->ltree,visit,flo-1);follow(tf->rtree,visit,flo-1);kf(tf);return ;2.3 層序遍歷評價：實現(xiàn)對每一層（或者指定層）進行遍歷輸出。算法思想：建立一個隊列，循環(huán)思想

7、如下：在循環(huán)前將當(dāng)頭節(jié)點入隊，進入循環(huán)后，先出隊一個，輸出，同時判斷左右子樹是否存在，存在則分別入隊，進入下一次循環(huán)。這樣下去，可以把每一層都輸出。同時會有一個i變量，用于判斷循環(huán)邊界以及是否輸入某層。（形參n為顯示層數(shù)參數(shù)，如果為0則全部輸出，此外輸出第n層）。void transver(Tnode* tf,int flo,fp kf,int n)int i=0;if(!tf)return NULL;inintque();/初始化隊列pus_pop(tf,1);/樹頭入隊while(i<pow(2,flo)-1)/只要i還小于最大的結(jié)點樹就繼續(xù)循環(huán)i+;/“指向”下一個節(jié)點tf=pus

8、_pop(tf,0);/出隊if(flag(n,i)kf(tf);/flag作用為：如果標(biāo)記變量n為0 那么就返回1 如果為其他數(shù)字則需要判斷i是否在第n層 否則返回0if(tf->ltree)pus_pop(tf->ltree,1);/左子樹存在的話就入隊if(tf->rtree)pus_pop(tf->rtree,1);/右子樹存在的話就入隊printf("n");int flag(int n,int i)if(n=0)return 1;if(pow(2,n-1)-1)<i&&(pow(2,n)-1)>=i)return 1;/在第n層范圍內(nèi)return 0;2.4 其他函數(shù)2.4.1 隊列的入隊和出隊函數(shù)Tnode*pus_pop(Tnode*tf,int k)i