二叉樹實(shí)驗(yàn)報(bào)告-15

實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)?zāi)康呐c要求1.建立二叉樹；2.對(duì)二叉樹的先、中、后序遍歷并輸出遍歷序列；3.實(shí)現(xiàn)二叉樹的中序遍歷非遞歸算法；4.實(shí)現(xiàn)二叉樹交換其左右子女的算法。實(shí)驗(yàn)內(nèi)容1.系統(tǒng)功能需求分析：由實(shí)驗(yàn)的目的與要求可知，本系統(tǒng)要主要是用于實(shí)現(xiàn)以上功能基于先序遍歷的構(gòu)造方法，建立圖4-13（a）所示二叉樹。并輸入其擴(kuò)充的先序序列（AB#C#D##EF##G##）輸出二叉樹的先、中、后序遍歷序列非遞歸算法，實(shí)現(xiàn)二叉樹的中序遍歷交換其左右子女2.存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)：二叉樹可采用順序存儲(chǔ)結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)。但考慮到順序存儲(chǔ)結(jié)構(gòu)比較適合于完全二叉樹、滿二叉樹。對(duì)于圖4-13（a）所示的二叉樹，采用二叉鏈表存儲(chǔ)結(jié)構(gòu)較為合適。二叉鏈表結(jié)點(diǎn)除數(shù)據(jù)域外，還有兩個(gè)鏈域：左孩子域、右孩子域分別指向其左右孩子。其結(jié)點(diǎn)類型定義如下：typedefstructnode{chardata;structnode*lchild,*rchild;}Node;3.我的源程序如下:#include"stdio.h"#include<malloc.h>typedefstructnode/*定義結(jié)點(diǎn)類型*/{chardata;structnode*lchild,*rchild;}Node;Node*createbintree()/*建立二叉樹*/{Node*t;charx;scanf("%c",&x);if(x=='#')t=NULL;else{t=(Node*)malloc(sizeof(Node));t->data=x;t->lchild=createbintree();t->rchild=createbintree();}return(t);}voidpreorder(Node*t)/*先序遍歷*/{if(t!=NULL){printf("%c",t->data);preorder(t->lchild);preorder(t->rchild);}}voidinorder(Node*t)/*中序遍歷*/{if(t!=NULL){inorder(t->lchild);printf("%c",t->data);inorder(t->rchild);}}voidpostorder(Node*t)/*后序遍歷*/{if(t!=NULL){postorder(t->lchild);postorder(t->rchild);printf("%c",t->data);}}voidinorder1(Node*t)/*非遞歸中序遍歷*/{Node*p;Node*stack[20];inttop=0;p=t;while(p||top!=0){while(p){stack[top++]=p;p=p->lchild;}p=stack[--top];printf("%c",p->data);p=p->rchild;}}voidexchangeLR(Node*t)/*交換其左右子女*/{Node*tmp;if(t!=NULL){tmp=t->lchild;t->lchild=t->rchild;t->rchild=tmp;exchangeLR(t->lchild);exchangeLR(t->rchild);}}voidmain(){Node*t=NULL;inta;while(1){printf("\n\n\n\n\n\n\n\n\n\t\t按任意鍵進(jìn)入主菜單....");getch();system("cls");printf("\t\t*****************09信管(1)班-關(guān)配-3109005656*************\n");printf("\n");printf("\t\t=======================================\n");printf("\t\t1.建立圖4-13(a)所示二叉樹\n");printf("\t\t2.二叉樹的先序遍歷\n");printf("\t\t3.二叉樹的中序遍歷\n");printf("\t\t4.二叉樹的后序遍歷\n");printf("\t\t5.二叉樹的中序非遞歸遍歷\n");printf("\t\t6.二叉樹交換其左右子女\n");printf("\t\t=======================================\n");printf("\n\t請(qǐng)選擇（0-6):");scanf("%d",&a);getchar();switch(a){case1:system("cls");printf("\n\n\n\n請(qǐng)輸入圖4-13(a)擴(kuò)充的先序序列為:(AB#C#D##EF##G##):");t=createbintree();if(t==NULL)printf("創(chuàng)建二叉樹失敗!");break;case2:system("cls");printf("\n\n先序遍歷為:");preorder(t);printf("\n");break;case3:system("cls");printf("\n\n中序遍歷為:");inorder(t);printf("\n");break;case4:system("cls");printf("\n\n后序遍歷為:");postorder(t);printf("\n");break; case5:system("cls");printf("\n\n中序非遞歸遍歷為:");inorder1(t);printf("\n");break;case6:system("cls");exchangeLR(t);if(t)printf("\n\n已成功交換其左右子樹");printf("\n");break;default:printf("輸入錯(cuò)誤,請(qǐng)重新輸入!\n");} }}三、實(shí)驗(yàn)結(jié)果和數(shù)據(jù)處理1.所要建立的二叉如下圖：BBECGFDD其先、中、后序序?yàn)椋篈BCDEFG，BCDAFEG，DCBFGEA交換左右子樹后的先、中、后序列為：AEGFBCD，GEFADCB，GFEDCBA2.測試結(jié)果：運(yùn)行程序(2)進(jìn)行主菜單選擇1，建立二叉樹回到主菜單，依次分分別選擇2、3、4，輸出其先中后序遞歸遍歷，其運(yùn)行結(jié)果如下圖，實(shí)驗(yàn)結(jié)果正確?；氐街鞑藛芜x擇5，其非遞歸中序遍歷，如下圖，結(jié)果正確?；氐街鞑藛?，選擇6，將它的左右子樹交換?；氐街鞑藛危来畏址謩e選擇2、3、4，輸出其先中后序遞歸遍歷，其運(yùn)行結(jié)果如下圖，交換后，實(shí)驗(yàn)結(jié)果正確?？偨Y(jié)本次實(shí)驗(yàn)主要遇到兩個(gè)問題，一個(gè)是自己解決的，另一個(gè)請(qǐng)教同學(xué)解決的。第一個(gè)問題是我編寫好源程序后，編譯沒有問題。但在輸入二叉樹的擴(kuò)充序列時(shí)沒有問題，就無法輸出，彈出對(duì)話框是“內(nèi)存不能READ”，我在猜想：與內(nèi)存相關(guān)的，應(yīng)該是指針的問題吧。我認(rèn)真檢查了一下源程序，原來是遍歷的函數(shù)出了問題，我忘記在if語句后三個(gè)語句加“{}”。第二個(gè)問題是我對(duì)程序進(jìn)行改進(jìn)時(shí)遇到的，我想對(duì)程序設(shè)計(jì)二級(jí)菜單，要用到“switch”語句。但在建立二叉樹時(shí)即無法將擴(kuò)充的先序序列輸入去，請(qǐng)教了同學(xué)之后，原來是在“switch”后面的括號(hào)的整型數(shù)據(jù)的輸入和建立二叉樹輸入的字符發(fā)生了沖突。加入了一個(gè)“getchar()”語