樹和二叉樹實(shí)驗(yàn)報(bào)告1000字

樹和二叉樹實(shí)驗(yàn)報(bào)告1000字

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)?zāi)康模赫莆斩鏄涞臉?gòu)造和遍歷應(yīng)用。實(shí)驗(yàn)內(nèi)容：建立二叉樹的二叉鏈表存儲并進(jìn)行先序、中序和后序遍歷。(要求：填上語句實(shí)現(xiàn)二叉樹的先序遍歷；編寫二叉樹的中序和后序遍歷。)#include<iostream>usingnamespacestd;typedefcharDataType;/*設(shè)數(shù)據(jù)域類型為字符型*/typedefstructBinTNode{DataTypedata;structBinTNode*lchild,*rchild;/*左右鏈域?yàn)橹赶蚪Y(jié)點(diǎn)結(jié)構(gòu)的指針類型*/}BinTNode,*BinTree;//,*BinTree;/*指向二叉樹結(jié)點(diǎn)的指針類型*/intcount;/*全局變量用于統(tǒng)計(jì)結(jié)點(diǎn)個(gè)數(shù)*/voidCreateBinTree(BinTreeT){/*以加入結(jié)點(diǎn)的先序序列輸入，構(gòu)造二叉鏈表*/charch;cin>>ch;if(ch=='0')T=NULL;/*讀入0時(shí)，將相應(yīng)結(jié)點(diǎn)置空*/else{if(!(T=(BinTNode*)malloc(sizeof(BinTNode))))exit(1);T->data=ch;CreateBinTree(T->lchild);/*構(gòu)造二叉樹的左子樹*/CreateBinTree(T->rchild);/*構(gòu)造二叉樹的右子樹*/}}boolPreorder(BinTreeT){/*先序遍歷二叉樹T*/if(T){printf("%3c",T->data);if(Preorder(T->lchild))/*先序遍歷二叉樹T的左子樹*/if(Preorder(T->rchild))/*先序遍歷二叉樹T的右子樹*/returntrue;}else{returnfalse;}}voidmain(){BinTreeT;printf("請按帶空指針的二叉樹先序輸入建立二叉樹存儲的結(jié)點(diǎn)序列:\n");CreateBinTree(T);printf("該二叉樹的先序遍歷序列為:\n");Preorder(T);}

第二篇：樹和二叉樹實(shí)驗(yàn)報(bào)告10300字樹和二叉樹一、實(shí)驗(yàn)?zāi)康?.掌握二叉樹的結(jié)構(gòu)特征，以及各種存儲結(jié)構(gòu)的特點(diǎn)及適用范圍。2.掌握用指針類型描述、訪問和處理二叉樹的運(yùn)算。二、實(shí)驗(yàn)要求1.認(rèn)真閱讀和掌握本實(shí)驗(yàn)的程序。2.上機(jī)運(yùn)行本程序。3.保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。4.按照二叉樹的操作需要，重新改寫主程序并運(yùn)行，打印出文件清單和運(yùn)行結(jié)果。三、實(shí)驗(yàn)內(nèi)容1.輸入字符序列，建立二叉鏈表。2.按先序、中序和后序遍歷二叉樹（遞歸算法）。3.按某種形式輸出整棵二叉樹。4.求二叉樹的高度。5.求二叉樹的葉節(jié)點(diǎn)個(gè)數(shù)。6.交換二叉樹的左右子樹。7.借助隊(duì)列實(shí)現(xiàn)二叉樹的層次遍歷。8.在主函數(shù)中設(shè)計(jì)一個(gè)簡單的菜單，分別調(diào)試上述算法。為了實(shí)現(xiàn)對二叉樹的有關(guān)操作，首先要在計(jì)算機(jī)中建立所需的二叉樹。建立二叉樹有各種不同的方法。一種方法是利用二叉樹的性質(zhì)5來建立二叉樹，輸入數(shù)據(jù)時(shí)要將節(jié)點(diǎn)的序號（按滿二叉樹編號）和數(shù)據(jù)同時(shí)給出：（序號，數(shù)據(jù)元素0）。另一種方法是主教材中介紹的方法，這是一個(gè)遞歸方法，與先序遍歷有點(diǎn)相似。數(shù)據(jù)的組織是先序的順序，但是另有特點(diǎn)，當(dāng)某結(jié)點(diǎn)的某孩子為空時(shí)以字符“#”來充當(dāng)，也要輸入。若當(dāng)前數(shù)據(jù)不為“#”，則申請一個(gè)結(jié)點(diǎn)存入當(dāng)前數(shù)據(jù)。遞歸調(diào)用建立函數(shù)，建立當(dāng)前結(jié)點(diǎn)的左右子樹。四、解題思路1訪問根結(jié)點(diǎn)，○2先序遍歷左子樹，○3先序遍歷右子樹1、先序遍歷：○1中序遍歷左子樹，○2訪問根結(jié)點(diǎn)，○3中序遍歷右子樹2、中序遍歷：○1后序遍歷左子樹，○2后序遍歷右子樹，○3訪問根結(jié)點(diǎn)3、后序遍歷：○4、層次遍歷算法：采用一個(gè)隊(duì)列q，先將二叉樹根結(jié)點(diǎn)入隊(duì)列，然后退隊(duì)列，輸出該結(jié)點(diǎn)；若它有左子樹，便將左子樹根結(jié)點(diǎn)入隊(duì)列；若它有右子樹，便將右子樹根結(jié)點(diǎn)入隊(duì)列，直到隊(duì)列空為止。因?yàn)殛?duì)列的特點(diǎn)是先進(jìn)后出，所以能夠達(dá)到按層次遍歷二叉樹的目的。五、程序清單#include<stdio.h>#include<stdlib.h>#defineM100typedefcharEtype;//定義二叉樹結(jié)點(diǎn)值的類型為字符型typedefstructBiTNode//樹結(jié)點(diǎn)結(jié)構(gòu){Etypedata;structBiTNode*lch,*rch;}BiTNode,*BiTree;BiTreeque[M];intfront=0,rear=0;//函數(shù)原型聲明BiTNode*creat_bt1();BiTNode*creat_bt2();voidpreorder(BiTNode*p);voidinorder(BiTNode*p);voidpostorder(BiTNode*p);voidenqueue(BiTree);BiTreedelqueue();voidlevorder(BiTree);inttreedepth(BiTree);voidprtbtree(BiTree,int);voidexchange(BiTree);intleafcount(BiTree);voidpaintleaf(BiTree);BiTNode*t;intcount=0;//主函數(shù)voidmain(){charch;intk;do{printf("\n\n\n");printf("\n===================主菜單===================");printf("\n\n1.建立二叉樹方法1");printf("\n\n2.建立二叉樹方法2");printf("\n\n3.先序遞歸遍歷二叉樹");printf("\n\n4.中序遞歸遍歷二叉樹");printf("\n\n5.后序遞歸遍歷二叉樹");printf("\n\n6.層次遍歷二叉樹");printf("\n\n7.計(jì)算二叉樹的高度");printf("\n\n8.計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)");printf("\n\n9.交換二叉樹的左右子樹");printf("\n\n10.打印二叉樹");printf("\n\n0.結(jié)束程序運(yùn)行");printf("\n============================================");printf("\n請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)");scanf("%d",&k);switch(k){case1:t=creat_bt1();break;//調(diào)用性質(zhì)5建立二叉樹算法case2:printf("\n請輸入二叉樹各結(jié)點(diǎn)值:");fflush(stdin);t=creat_bt2();break;//調(diào)用遞歸建立二叉樹算法case3:if(t){printf("先序遍歷二叉樹:");preorder(t);printf("\n");}elseprintf("二叉樹為空!\n");break;case4:if(t){printf("中序遍歷二叉樹:");inorder(t);printf("\n");}elseprintf("二叉樹為空!\n");break;case5:if(t){printf("后序遍歷二叉樹:");postorder(t);printf("\n");}elseprintf("二叉樹為空!\n");break;case6:if(t){printf("層次遍歷二叉樹：");levorder(t);printf("\n");}elseprintf("二叉樹為空！\n");break;case7:if(t){printf("二叉樹的高度為：%d",treedepth(t));printf("\n");}elseprintf("二叉樹為空！\n");break;case8:if(t){printf("二叉樹的葉子結(jié)點(diǎn)數(shù)為：%d\n",leafcount(t));printf("二叉樹的葉結(jié)點(diǎn)為：");paintleaf(t);printf("\n");}elseprintf("二叉樹為空！\n");break;case9:if(t){printf("交換二叉樹的左右子樹：\n");exchange(t);prtbtree(t,0);printf("\n");}elseprintf("二叉樹為空！\n");break;case10:if(t){printf("逆時(shí)針旋轉(zhuǎn)90度輸出的二叉樹：\n");prtbtree(t,0);printf("\n");}elseprintf("二叉樹為空！\n");break;case0:exit(0);}//switch}while(k>=1&&k<=10);printf("\n再見！按回車鍵，返回?\n");ch=getchar();}//main//利用二叉樹性質(zhì)5，借助一維數(shù)組V建立二叉樹BiTNode*creat_bt1(){BiTNode*t,*p,*v[20];inti,j;Etypee;/*輸入結(jié)點(diǎn)的序號i、結(jié)點(diǎn)的數(shù)據(jù)e*/printf("\n請輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值（如1，a）：");scanf("%d,%c",&i,&e);while(i!=0&&e!='#')//當(dāng)i為0，e為'#'時(shí)，結(jié)束循環(huán){p=(BiTNode*)malloc(sizeof(BiTNode));p->data=e;p->lch=NULL;p->rch=NULL;v[i]=p;if(i==1)t=p;//序號為1的結(jié)點(diǎn)是根else{j=i/2;if(i%2==0)v[j]->lch=p;//序號為偶數(shù)，作為左孩子elsev[j]->rch=p;//序號為奇數(shù)，作為右孩子}printf("\n請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值：");scanf("%d,%c",&i,&e);}return(t);}//creat_bt1;//模仿先序遞歸遍歷方法，建立二叉樹BiTNode*creat_bt2(){BiTNode*t;Etypee;scanf("%c",&e);if(e=='#')t=NULL;//對于'#'值，不分配新結(jié)點(diǎn)else{t=(BiTNode*)malloc(sizeof(BiTNode));t->data=e;t->lch=creat_bt2();t->rch=creat_bt2();}return(t);}//creat_bt2//先序遞歸遍歷二叉樹voidpreorder(BiTNode*p){if(p){printf("%3c",p->data);preorder(p->lch);preorder(p->rch);}}//preorder//中序遞歸遍歷二叉樹voidinorder(BiTNode*p){if(p){inorder(p->lch);printf("%3c",p->data);inorder(p->rch);}}//inorder//后序遞歸遍歷二叉樹voidpostorder(BiTNode*p){if(p){postorder(p->lch);postorder(p->rch);printf("%3c",p->data);//左孩子獲得新指針值//右孩子獲得新指針值}}//postordervoidenqueue(BiTreeT){if(front!=(rear+1)%M){rear=(rear+1)%M;que[rear]=T;}}BiTreedelqueue(){if(front==rear)returnNULL;front=(front+1)%M;return(que[front]);}voidlevorder(BiTreeT){BiTreep;if(T){enqueue(T);while(front!=rear){p=delqueue();printf("%3d",p->data);if(p->lch!=NULL)enqueue(p->lch);if(p->rch!=NULL)enqueue(p->rch);}}}inttreedepth(BiTreebt){inthl,hr,max;if(bt!=NULL){hl=treedepth(bt->lch);hr=treedepth(bt->rch);max=(hl>hr)?hl:hr;return(max+1);}elsereturn(0);}voidprtbtree(BiTreebt,intlevel){intj;if(bt){prtbtree(bt->rch,level+1);//層次遍歷二叉樹//計(jì)算二叉樹的高度//逆時(shí)針旋轉(zhuǎn)90度輸出二叉樹樹形for(j=0;j<=6*level;j++)printf("");printf("%c\n",bt->data);prtbtree(bt->lch,level+1);}}voidexchange(BiTreebt)//交換二叉樹左右子樹{BiTreep;if(bt){p=bt->lch;bt->lch=bt->rch;bt->rch=p;exchange(bt->lch);exchange(bt->rch);}}intleafcount(BiTreebt)//計(jì)算葉結(jié)點(diǎn)數(shù){if(bt!=NULL){leafcount(bt->lch);leafcount(bt->rch);if((bt->lch==NULL)&&(bt->rch==NULL))count++;}return(count);}voidpaintleaf(BiTreebt)//輸出葉結(jié)點(diǎn){if(bt!=NULL){if(bt->lch==NULL&&bt->rch==NULL)printf("%3c",bt->data);paintleaf(bt->lch);paintleaf(bt->rch);}}圖11.2所示二叉樹的輸入數(shù)據(jù)順序應(yīng)該是：abd#g###ce#h##f##。圖11.2二叉樹示意圖運(yùn)行結(jié)果：===================主菜單===================1.建立二叉樹方法12.建立二叉樹方法23.先序遞歸遍歷二叉樹4.中序遞歸遍歷二叉樹5.后序遞歸遍歷二叉樹6.層次遍歷二叉樹7.計(jì)算二叉樹的高度8.計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9.交換二叉樹的左右子樹10.打印二叉樹0.結(jié)束程序運(yùn)行============================================請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)1請輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值（如1，a）：1，a請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值：2，b請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值：3，c請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值：4，d請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值：6，e請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值：7，f請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值：9，g請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值：13，h請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值：0，#===================主菜單===================");1.建立二叉樹方法12.建立二叉樹方法23.先序遞歸遍歷二叉樹4.中序遞歸遍歷二叉樹5.后序遞歸遍歷二叉樹6.層次遍歷二叉樹7.計(jì)算二叉樹的高度8.計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9.交換二叉樹的左右子樹10.打印二叉樹0.結(jié)束程序運(yùn)行============================================請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)3先序遍歷二叉樹：abdgcehf===================主菜單===================");1.建立二叉樹方法12.建立二叉樹方法23.先序遞歸遍歷二叉樹4.中序遞歸遍歷二叉樹5.后序遞歸遍歷二叉樹6.層次遍歷二叉樹7.計(jì)算二叉樹的高度8.計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9.交換二叉樹的左右子樹10.打印二叉樹0.結(jié)束程序運(yùn)行============================================請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)4中序遍歷二叉樹：dgbaehcf===================主菜單===================");1.建立二叉樹方法12.建立二叉樹方法23.先序遞歸遍歷二叉樹4.中序遞歸遍歷二叉樹5.后序遞歸遍歷二叉樹6.層次遍歷二叉樹7.計(jì)算二叉樹的高度8.計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9.交換二叉樹的左右子樹10.打印二叉樹0.結(jié)束程序運(yùn)行============================================請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)5后序遍歷二叉樹：gdbhefca===================主菜單===================");1.建立二叉樹方法12.建立二叉樹方法23.先序遞歸遍歷二叉樹4.中序遞歸遍歷二叉樹5.后序遞歸遍歷二叉樹6.層次遍歷二叉樹7.計(jì)算二叉樹的高度8.計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9.交換二叉樹的左右子樹10.打印二叉樹0.結(jié)束程序運(yùn)行============================================請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)6層次遍歷二叉樹：979899100101102103104===================主菜單===================");1.建立二叉樹方法12.建立二叉樹方法23.先序遞歸遍歷二叉樹4.中序遞歸遍歷二叉樹5.后序遞歸遍歷二叉樹6.層次遍歷二叉樹7.計(jì)算二叉樹的高度8.計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9.交換二叉樹的左右子樹10.打印二叉樹0.結(jié)束程序運(yùn)行============================================請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)7二叉樹的高度為：4===================主菜單===================");1.建立二叉樹方法12.建立二叉樹方法23.先序遞歸遍歷二叉樹4.中序遞歸遍歷二叉樹5.后序遞歸遍歷二叉樹6.層次遍歷二叉樹7.計(jì)算二叉樹的高度8.計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9.交換二叉樹的左右子樹10.打印二叉樹0.結(jié)束程序運(yùn)行============================================請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)8二叉樹的葉子結(jié)點(diǎn)數(shù)為：3二叉樹的葉結(jié)點(diǎn)為：ghf===================主菜單===================");1.建立二叉樹方法12.建立二叉樹方法23.先序遞歸遍歷二叉樹4.中序遞歸遍歷二叉樹5.后序遞歸遍歷二叉樹6.層次遍歷二叉樹7.計(jì)算二叉樹的高度8.計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9.交換二叉樹的左右子樹10.打印二叉樹0.結(jié)束程序運(yùn)行============================================請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)9交換二叉樹的左右子樹：dgbaehcf===================主菜單=============