二叉樹的基本操作及應用

實驗報告實驗報告（三）實驗題目二叉樹的基本操作及應用實驗時間6月10日實驗地點B07-B214實驗成績實驗性質□應用性□設計性□綜合性教師評閱：評閱教師簽名：一、實驗目的1熟悉二叉樹的存儲構造和對二叉樹的基本操作。2掌握對二叉樹前序、中序、后序遍歷操作的具體實現(xiàn)。3學習運用遞歸辦法編寫對二叉樹這種遞歸數(shù)據(jù)構造進行解決的算法。4會應用二叉樹的基本操作解決簡樸的實際問題二、實驗內容和規(guī)定(闡明算法的時間復雜度)1基于二叉鏈表的存儲格式，輸入二叉樹的先序序列，用*代表空節(jié)點，如ABD**CE**F**建立二叉樹，然后中序遍歷二叉樹，輸出節(jié)點的值。2針對建好的二叉樹，編寫遞歸程序，求樹中葉子節(jié)點個數(shù)。3針對建好的二叉樹，編寫遞歸程序，求二叉樹的高度。4針對建好的二叉樹，試編寫二叉樹的前序非遞歸遍歷算法。三、重要設計思想與算法（此處不夠可加頁，或在背面書寫）該實驗重要涉及一下幾個函數(shù)，算法核心分別在各函數(shù)中。建立樹的構造。typedef structBiTNode{ charelement; Treelchild,rchild;};//B數(shù)的基本結點輸入ABD**CE**F***TreeCreateBTree(void)//能夠返回一種Tree指針{ TreepTree; charval; scanf("%c",&val); printf("%c",val); if(val=='*'||val=='^p')returnNULL;//根據(jù)輸入字符先序建樹 else//*代表空 { pTree=(Tree)malloc(sizeof(structBiTNode)); if(pTree==NULL) { printf("內存分派失??！"); exit(-1);//避免程序不懂得空間不夠用了 } pTree->element=val; pTree->lchild=CreateBTree(); pTree->rchild=CreateBTree();//遞歸，NLR地創(chuàng)立結點 } returnpTree;};數(shù)葉結點個數(shù)intCountLeaf(TreeT){ if(T==NULL)return0; if(!T->lchild&&!T->rchild) { return1;//兩個兒子都空則闡明是葉子，返回1 } else { returnCountLeaf(T->lchild)+CountLeaf(T->rchild);//數(shù)左右子樹總共的葉結點 } };3.數(shù)樹的深度intCountLevel(TreeT){ if(!T)return0; else { intLeft=CountLevel(T->lchild);intRight=CountLevel(T->rchild); return1+(Left>Right?Left:Right);//三目運算取最大 }};//最后數(shù)得樹的最深層數(shù)，也是遞歸typedefstruct{ Treeelements[MAXSIZE];//注意這里放的是指針 inttop;}Stack;//這是一種用于裝Tree指針的棧4.這是用非遞歸實現(xiàn)先序遍歷的voidPreOrder(TreeT){StackS; Treep; InitStack(&S);//造一種棧待會兒用 p=T;//用p指針來不停解決結點操作while(p||!IsEmpty(S)) {while(p) { printf("%c",p->element);//只要不空則把p指的數(shù)據(jù)輸出 Push(&S,p);p=p->lchild;//繼續(xù)往左邊找 }//一旦停下來闡明找到了空結點，則開始往上一層的右邊找一下 if(!IsEmpty(S)) {//棧非空 p=Pop(&S);//退棧，找到剛剛說的上一層 p=p->rchild;//找右邊了 } }//只要while還循環(huán)闡明沒有遍歷完，現(xiàn)在再一次從剛剛的右邊執(zhí)行先序遍歷};四、實驗成果（設計文檔、文稿寄存途徑，能夠截圖描述實驗成果）#include<stdio.h>#include"3.h"intmain(void)//改主程序對應上圖成果{ TreepTree; inti,j; pTree=CreateBTree();//創(chuàng)立二叉樹pTree i=CountLeaf(pTree); printf("Thereare%dleaves!",i);//遞歸程序數(shù)葉節(jié)點 j=CountLevel(pTree); printf("Thereare%dlevels!",j);//遞歸程序數(shù)層數(shù) PreOrder(pTree);//按照前序遍歷輸出該書的元素 return0;}五、實驗分析總結本次實驗采用二叉樹存儲了一系列的字符串，通過函數(shù)TreeCreateBTree(void)得到一種根據(jù)輸入創(chuàng)立的二叉樹構造，時間復雜度是O（n）；通過函數(shù)intCountLeaf(TreeT)遞歸返回葉子個數(shù)，時間復雜度O(n)；通過intCountLevel(TreeT)返回最深途徑得到樹的深度，時間復雜度O（n）；；最后用voidPreOrder(TreeT)實現(xiàn)非遞歸寫法的二叉樹先序遍歷，時間復雜度為O(n).總而言之，由于都是要遍歷B數(shù)的每個節(jié)點，因此程序執(zhí)行的時間長度和輸入的字符串長度n是線性增加的。他們的時間復雜度都是O(n).這次實驗，我更深刻的理解了B數(shù)的基本性質如遞歸性，運用遞歸，我們能夠很方便的寫出多個對樹的操作；熟悉了創(chuàng)立樹，遍歷樹的基本辦法；體會了算法的代碼實現(xiàn)