數(shù)據(jù)結(jié)構(gòu)試驗-二叉樹的操作

1、v1.0可編輯可修改*實驗題目：二叉樹的操作實驗者信息：班級 ，姓名 龐文正，學(xué)號26實驗完成的時間3:00*一、實驗?zāi)康?, 掌握二叉樹鏈表的結(jié)構(gòu)和二叉樹的建立過程。2, 掌握隊列的先進(jìn)先出的運算原則在解決實際問題中的應(yīng)用。3, 進(jìn)一步掌握指針變量、指針數(shù)組、動態(tài)變量的含義。4, 掌握遞歸程序設(shè)計的特點和編程方法。二、實驗內(nèi)容已知以二叉鏈表作存儲結(jié)構(gòu)，試編寫按層次遍歷二叉樹的算法。（所謂層次遍歷，是指從二叉樹的根結(jié)點開始從上到下逐層遍歷二叉樹，在同一層次中從左到右依次訪問各個節(jié)點。）調(diào)試程序并對相應(yīng)的輸出作出分析；修改輸入數(shù)據(jù)，預(yù)期輸出并驗證輸出的結(jié)果。加 深對算法的理解。三、算法設(shè)計與編碼

2、1. 本實驗用到的理論知識總結(jié)本實驗用到的理論知識，實現(xiàn)理論與實踐相結(jié)合。總結(jié)盡量簡明扼要， 并與本次實驗密切相關(guān)，最好能加上自己的解釋。本算法要采用一個循環(huán)隊列que，先將二叉樹根結(jié)點入隊列，然后退隊列，輸出該結(jié)點；若它有左子樹，便將左子樹根結(jié)點入隊列；若它有右子樹，便將右子樹根結(jié)點入隊列，直到隊列空為止。因為隊列的特點是先進(jìn)先出，從而達(dá)到按層次順序遍歷二叉的目的。2. 算法概要設(shè)計給出實驗的數(shù)據(jù)結(jié)構(gòu)描述，程序模塊、功能及調(diào)用關(guān)系#in clude<>#in clude<>#defi ne M 100typedef struct n ode /二叉鏈表節(jié)點結(jié)構(gòu)int

3、data; / 數(shù)據(jù)域struct node *lchild,*rchild; /左孩子 右孩子鏈bitree;bitree *queM; /定義一個指針數(shù)組，說明隊列中的元素bitree指針類型11int fron t=0, rear=0; /初始化循環(huán)列隊bitree *creat() /建立二叉樹的遞歸算法bitree *t;int x;scan f("%d", &x);if(x=0) t=NULL;/以x=0表示輸入結(jié)束elset=malloc(sizeof(bitree);/動態(tài)生成節(jié)點t，分別給節(jié)點t的數(shù)據(jù)域，t->data=x;/左右孩子域賦值，

4、給左右孩子賦值時用到t->lchild=creat();/了遞歸思想t->rchild=creat();return t;void ino rder(bitree *t) /中序遍歷二叉樹的遞歸算法if(t!=NULL)ino rder(t->lchild);prin tf("%4d",t->data);ino rder(t->rchild); void enq ueue(t) /把bitree 類型的節(jié)點*t列入隊列bitree *t;if(fro nt!=(rear+1)%M) II判斷隊列是否已滿rear=(rear+1)%M;quere

5、ar=t; bitree *delqueue()if(fro nt=rear) return NULL; II判斷隊列不為空fron t=(fro nt+1)%M;return (quefr on t);void levorder(t) II層次遍歷二叉樹的算法bitree *t;bitree *p;if(t!=NULL)en queue(t); II根節(jié)點入隊while(fro nt!=rear) II當(dāng)前隊列不為空時p=delqueue(); II輸出對頭元素，并把其左右孩子入隊列。此過程prin tf("%4d",p->data); II一直遞歸，直到隊列為空i

6、f(p->lchild!=NULL) enqueue(p->lchild);if(p->rchild!=NULL) enq ueue(p->rchild);main ()bitree *root;prin tf("n");root=creat();ino rder(root); prin tf("n"); levorder(root);四、運行與測試(1) 在調(diào)試程序的過程中遇到什么問題，是如何解決的未遇到問題，只是就一個輸入框框，感覺不知道錯哪里了!(2) 設(shè)計了那些測試數(shù)據(jù)測試結(jié)果是什么(3)程序運行的結(jié)果如何1、預(yù)習(xí)思考題調(diào)

7、試好上述程序后，試著完成以下拓展內(nèi)容:(1)寫出二叉樹前序遍歷和后序遍歷的遞歸算法，并在主函數(shù)中調(diào)用它，調(diào)試好程序并分析其運行結(jié)果。/先序遍歷二叉樹void PreOrder(BiTree root)/先序遍歷二叉樹，root為指向二叉樹跟結(jié)點的指針if(root!=NULL)Visit(root->data);訪問根結(jié)點PreOrder(root->LChild);先序遍歷左子樹PreOrder(root->RChild);先序遍歷右子樹/后序遍歷二叉樹void PostOrder(BiTree root)if(root!=NULL)PostOrder(root->LChild);PostOrder(root->RChild);Visit(root->data);(2) 在二叉樹的層次遍歷中，如果不采用循環(huán)隊列，而是采用順序隊列，會出現(xiàn)什么問題會產(chǎn)生溢出或資源空間浪費。(3) 寫出二叉樹三種遍歷的非遞歸算法，并在主函數(shù)中調(diào)用它，調(diào)試好程序并分析其