第一篇：實驗報告：二叉樹
實驗報告 二叉樹
一 實驗?zāi)康?/p>
1、進一步掌握指針變量，動態(tài)變量的含義；
2、掌握二叉樹的結(jié)構(gòu)特性以及各種存儲結(jié)構(gòu)的特點及適用范圍。
3、掌握用指針類型描述、訪問和處理二叉樹的運算。
4、熟悉各種存儲結(jié)構(gòu)的特征以及如何應(yīng)用樹結(jié)構(gòu)解決具體問題。
二 實驗原理
樹形結(jié)構(gòu)是一種應(yīng)用十分廣泛和重要的非線性數(shù)據(jù)結(jié)構(gòu)，是一種以分支關(guān)系定義的層次結(jié)構(gòu)。在這種結(jié)構(gòu)中，每個數(shù)據(jù)元素至多只有一個前驅(qū)，但可以有多個后繼；數(shù)據(jù)元素之間的關(guān)系是一對多的層次關(guān)系。樹形結(jié)構(gòu)主要用于描述客觀世界中具有層次結(jié)構(gòu)的數(shù)據(jù)關(guān)系，它在客觀世界中大量存在。遍歷二叉樹的實質(zhì)是將非線性結(jié)構(gòu)轉(zhuǎn)為線性結(jié)構(gòu)。
三 使用儀器，材料 計算機 2 Wndows xp 3 VC6.0
四實驗步驟
【問題描述】建立一個二叉樹，請分別按前序，中序和后序遍歷該二叉樹?！净疽蟆繌逆I盤接受輸入（按前序順序），以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以前序來建立），并采用遞歸算法對其進行前序，中序和后序遍歷，將結(jié)果輸出。
【實現(xiàn)提示】按前序次序輸入二叉樹中結(jié)點的值（一個整數(shù)），0表示空樹，葉子結(jié)點的特征是其左右孩子指針為空。
五實驗過程原始記錄 基本數(shù)據(jù)結(jié)構(gòu)描述； 2 函數(shù)間的調(diào)用關(guān)系； 用類C語言描述各個子函數(shù)的算法； 附錄：源程序。
六 試驗結(jié)果分析
將實驗結(jié)果分析、實驗中遇到的問題和解決問題的方法以及關(guān)于本實驗項目的心得體會，寫在實驗報告上。
第二篇：數(shù)據(jù)結(jié)構(gòu)二叉樹操作驗證實驗報告
班級：計算機11-2 學(xué)號：40 姓名：朱報龍
成績：_________
實驗七 二叉樹操作驗證
一、實驗?zāi)康?/p>
⑴ 掌握二叉樹的邏輯結(jié)構(gòu)；
⑵ 掌握二叉樹的二叉鏈表存儲結(jié)構(gòu)；
⑶ 掌握基于二叉鏈表存儲的二叉樹的遍歷操作的實現(xiàn)。
二、實驗內(nèi)容
⑴ 建立一棵含有n個結(jié)點的二叉樹，采用二叉鏈表存儲；
⑵ 前序（或中序、后序）遍歷該二叉樹。
三、設(shè)計與編碼
#include
void inorder(void visit(BTreeNode
void postorder(void visit(BTreeNode
static void fun(BTreeNode data;}//訪問結(jié)點 protected: BTreeNode //***********************建樹******************************* template template //***********************遍歷******************************* template {cout <<“遞歸先序遍歷二叉樹：”;s.preorder(s.fun);cout < 答：經(jīng)常忘記對頭結(jié)點的定義，以至于程序出錯，經(jīng)定義頭結(jié)點，使程序正常運行。 b)程序運行的結(jié)果如何？ 四、實驗小結(jié) 多練習(xí)，多上機，耐心調(diào)試程序，找出錯誤，多總結(jié)。 實驗報告 課程名：數(shù)據(jù)結(jié)構(gòu)（C語言版）實驗名：二叉樹的遍歷 姓名： 班級： 學(xué)號： 時間：2014.11.03 一 實驗?zāi)康呐c要求 1.掌握二叉樹的存儲方法 2.掌握二叉樹的三種遍歷方法 3.實現(xiàn)二叉樹的三種遍歷方法中的一種 二 實驗內(nèi)容 ? 接受用戶輸入一株二叉樹 ? 輸出這株二叉樹的前根, 中根, 后根遍歷中任意一種的順序 三 實驗結(jié)果與分析 //*********************************************************** //頭文件 #include #define OK 1 #define ERROR 0 #define OVERFLOW 0 //*********************************************************** typedef struct BiTNode { //二叉樹二叉鏈表存儲結(jié)構(gòu) char data;struct BiTNode *lChild,*rChild;}BiTNode,*BiTree;//*********************************************************** int CreateBiTree(BiTree &T){ //按先序次序輸入二叉中樹結(jié)點的值，空格表示空樹 //構(gòu)造二叉鏈表表示的二叉樹T char ch;fflush(stdin);scanf(“%c”,&ch);if(ch==' ')T=NULL;else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))return(OVERFLOW);T->data=ch;CreateBiTree(T->lChild);CreateBiTree(T->rChild);} return(OK);} //********************************************************* void PreOrderTraverse(BiTree T){ //采用二叉鏈表存儲結(jié)構(gòu)，先序遍歷二叉樹的遞歸算法 if(T){ printf(“%c”,T->data);PreOrderTraverse(T->lChild);PreOrderTraverse(T->rChild);} } /***********************************************************/ void InOrderTraverse(BiTree T){ //采用二叉鏈表存儲結(jié)構(gòu)，中序遍歷二叉樹的遞歸算法 if(T){ InOrderTraverse(T->lChild);printf(“%c”,T->data);InOrderTraverse(T->rChild);} } //*********************************************************** void PostOrderTraverse(BiTree T){ //采用二叉鏈表存儲結(jié)構(gòu)，后序遍歷二叉樹的遞歸算法 if(T){ PostOrderTraverse(T->lChild);PostOrderTraverse(T->rChild);printf(“%c”,T->data);} } //*********************************************************** void main(){ //主函數(shù)分別實現(xiàn)建立并輸出先、中、后序遍歷二叉樹 printf(“please input your tree follow the PreOrder:n”);BiTNode *Tree;CreateBiTree(Tree);printf(“n先序遍歷二叉樹:”);PreOrderTraverse(Tree);printf(“n中序遍歷二叉樹:”);InOrderTraverse(Tree);printf(“n后序遍歷二叉樹:”);PostOrderTraverse(Tree);} 圖1:二叉樹的遍歷運行結(jié)果 班級：380911班 學(xué)號：57000211 姓名：徐敏 實驗報告 一，實驗?zāi)康模?/p> ·掌握二叉樹的鏈式存儲結(jié)構(gòu)； ·掌握構(gòu)造二叉樹的方法； ·加深對二叉樹的中序遍歷的理解； 二，實驗方法： ·用遞歸調(diào)用算法中序遍歷二叉樹。三，實驗步驟： ·通過鏈式存儲建立一顆二叉樹。 ·設(shè)計一個算法實現(xiàn)中序遍歷二叉樹。四，具體實驗步驟： #include typedef struct _BTNODE{ char c;struct _BTNODE *lchild;struct _BTNODE *rchild;}BTNODE,*PBTNODE; void PrintBTree(PBTNODE p,int depth);void ConstructBTree(PBTNODE p);void InorderTraverse(PBTNODE p); void main(){ PBTNODE p;p=(PBTNODE)calloc(1,sizeof(BTNODE));printf(“Input the data:”);ConstructBTree(p);PrintBTree(p,0);printf(“Now InorderTraverse:”);InorderTraverse(p);printf(“nPress any key to continue...”);getchar();} void PrintBTree(PBTNODE p,int depth){ 班級：380911班 學(xué)號：57000211 姓名：徐敏 int i;if(p==NULL){ return;}else{ for(i=0;i printf(“--”);} printf(“>”); printf(“%cn”,p->c); PrintBTree(p->lchild,depth+1); PrintBTree(p->rchild,depth+1);} } void ConstructBTree(PBTNODE p){ int side;char c;side=LEFT;while(TRUE){ scanf(“%c”,&c); if(c=='n'){ //printf(“EOFn”); return; } // printf(“%dn”,c); switch(c){ case '|': break; case')': return; case',': side=RIGHT; break; case'(': if(side==LEFT){ if(p->lchild==NULL){ p->lchild=(PBTNODE)calloc(1,sizeof(BTNODE)); } ConstructBTree(p->lchild); }else{ if(p->rchild==NULL){ p->rchild=(PBTNODE)calloc(1,sizeof(BTNODE)); } 班級：380911班 學(xué)號：57000211 姓名：徐敏 ConstructBTree(p->rchild); } break; default: if(side==LEFT){ p->lchild=(PBTNODE)calloc(1,sizeof(BTNODE)); p->lchild->c=c; }else{ p->rchild=(PBTNODE)calloc(1,sizeof(BTNODE)); p->rchild->c=c; } } } } void InorderTraverse(PBTNODE p){ if(p==NULL){ return;}else{ InorderTraverse(p->lchild); printf(“[%c] ”,p->c); InorderTraverse(p->rchild);} return;} 五，實驗過程： ·輸出：Input the date; ·輸入：1(2(3,4),5(6,7)); ·輸出：Now InorderTraverse:【3】【2】【4】【1】【6】【5】【7】;六，上機實驗體會： ·體會到熟練掌握各種程序算法的重要性； ·通過上機練習(xí)，充分理解了鏈式建立二叉樹的算法； ·形象的了解二叉樹的結(jié)構(gòu)，能夠熟練的進行先序，中序，后序遍歷二叉樹。 《數(shù)據(jù)結(jié)構(gòu)》 第六次實驗報告 學(xué)生姓名 學(xué)生班級 學(xué)生學(xué)號 指導(dǎo)老師 重慶郵電大學(xué)計算機學(xué)院 計算機專業(yè)實驗中心 一、實驗內(nèi)容 1)采用二叉樹鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結(jié)點總數(shù)的操作。2)輸出樹的深度，最大元，最小元。 二、需求分析 遍歷二叉樹首先有三種方法，即先序遍歷，中序遍歷和后序遍歷。遞歸方法比較簡單，首先獲得結(jié)點指針如果指針不為空，且有左子，從左子遞歸到下一層，如果沒有左子，從右子遞歸到下一層，如果指針為空，則結(jié)束一層遞歸調(diào)用。直到遞歸全部結(jié)束。下面重點來講述非遞歸方法： 首先介紹先序遍歷： 先序遍歷的順序是根 左 右，也就是說先訪問根結(jié)點然后訪問其左子再然后訪問其右子。具體算法實現(xiàn)如下：如果結(jié)點的指針不為空，結(jié)點指針入棧，輸出相應(yīng)結(jié)點的數(shù)據(jù)，同時指針指向其左子，如果結(jié)點的指針為空，表示左子樹訪問結(jié)束，棧頂結(jié)點指針出棧，指針指向其右子，對其右子樹進行訪問，如此循環(huán)，直至結(jié)點指針和棧均為空時，遍歷結(jié)束。 再次介紹中序遍歷： 中序遍歷的順序是左 根 右，中序遍歷和先序遍歷思想差不多，只是打印順序稍有變化。具體實現(xiàn)算法如下：如果結(jié)點指針不為空，結(jié)點入棧，指針指向其左子，如果指針為空，表示左子樹訪問完成，則棧頂結(jié)點指針出棧，并輸出相應(yīng)結(jié)點的數(shù)據(jù)，同時指針指向其右子，對其右子樹進行訪問。如此循環(huán)直至結(jié)點指針和棧均為空，遍歷結(jié)束。最后介紹后序遍歷： 后序遍歷的順序是左 右 根，后序遍歷是比較難的一種，首先需要建立兩個棧，一個用來存放結(jié)點的指針，另一個存放標志位，也是首先訪問根結(jié)點，如果結(jié)點的指針不為空，根結(jié)點入棧，與之對應(yīng)的標志位也隨之入標志位棧，并賦值0，表示該結(jié)點的右子還沒有訪問，指針指向該結(jié)點的左子，如果結(jié)點指針為空，表示左子訪問完成，父結(jié)點出棧，與之對應(yīng)的標志位也隨之出棧，如果相應(yīng)的標志位值為0，表示右子樹還沒有訪問，指針指向其右子，父結(jié)點再次入棧，與之對應(yīng)的標志位也入棧，但要給標志位賦值為1，表示右子訪問過。如果相應(yīng)的標志位值為1，表示右子樹已經(jīng)訪問完成，此時要輸出相應(yīng)結(jié)點的數(shù)據(jù)，同時將結(jié)點指針賦值為空，如此循環(huán)直至結(jié)點指針和棧均為空，遍歷結(jié)束。 三、詳細設(shè)計 源代碼： #include typedef struct Tnode //定義結(jié)點 { char data;//存儲結(jié)點數(shù)據(jù) struct Tnode *left;//定義結(jié)點左子指針 struct Tnode *right;//定義右子指針 }Tnode,*Pnode;//聲明Tnode類型的變量和指針 typedef struct Stack//定義棧 { Pnode pnode[MAX];//存放數(shù)據(jù) int p;//棧頂指針 }Stack,*Pstack;//定義Stack類型的變量和指針 void Push(Pstack pstack,Pnode pnode)//入棧 { } Pnode Pop(Pstack pstack)//出棧 { } Pnode Top(Pstack pstack)//看棧頂元素 { } int Isempty(Pstack pstack)//棧判空 { } int Isfull(Pstack pstack)//棧滿 { } void Initstack(Pstack pstack)//初始化棧 if(pstack->p==FULL)else return 0;return 1;if(pstack->p==EMPTY)else return 0;;return 1;return pstack->pnode[pstack->p];return pstack->pnode[pstack->p--];pstack->p ++;pstack->pnode[pstack->p] = pnode;//賦值 { } void Inittnode(Pnode root,Pnode left,Pnode right,char data)//初始化結(jié)點 { } void PreorderR(Pnode proot)//遞歸先序遍歷算法 { } void InorderR(Pnode proot)//遞歸中序遍歷算法 { } void PostorderR(Pnode proot)//遞歸后序遍歷算法 { } void PreorderI(Pnode proot,Pstack pstack)//非遞歸先序遍歷算法 { Initstack(pstack);//初始化棧 while(proot||!Isempty(pstack))//如果?？詹⑶医Y(jié)點指針空，則結(jié)束循環(huán) { if(proot){ printf(“%2c”,proot->data);if(proot){ } PostorderR(proot->left);PostorderR(proot->right);printf(“%2c”,proot->data);if(proot){ } InorderR(proot->left);printf(“%2c”,proot->data);InorderR(proot->right);if(proot){ } printf(“%2c”,proot->data);PreorderR(proot->left);PreorderR(proot->right);root->left=left;root->right = right;root->data = data;pstack->p=EMPTY; } } } else { } if(Isfull(pstack))//如果棧滿不能執(zhí)行入棧操作 { } Push(pstack,proot);//入棧 proot=proot->left;//指針指向左子 printf(“棧滿，不能執(zhí)行入棧操作！”);return;if(Isempty(pstack))//?？諘r不能出棧 { } proot = Pop(pstack);//執(zhí)行出棧操作 proot=proot->right;//指針指向右子 printf(“棧空，不能執(zhí)行出棧操作！”);return;void InorderI(Pnode proot,Pstack pstack)//非遞歸中序遍歷算法 { Initstack(pstack);//初始化棧 while(proot||!Isempty(pstack))//循環(huán)結(jié)束條件 { if(proot){ } else { if(Isempty(pstack)){ } proot = Pop(pstack);//出棧 printf(“%2c”,proot->data);//打印數(shù)據(jù) printf(“?？?，不能執(zhí)行出棧操作！”);return;if(Isfull(pstack)){ } Push(pstack,proot);//執(zhí)行入棧操作 proot = proot->left;//指針指向左子 printf(“棧滿，不能執(zhí)行入棧操作！”);return; } } } proot=proot->right;//指針指向右子 void PostorderI(Pnode proot,Pstack pstack)//非遞歸后續(xù)遍歷算法 { } void main(){ int flags[MAX];//定義標志位棧 int p =-1;//初始化標志位棧 int flag;//存放標志位 Initstack(pstack);//初始化棧 while(proot||!Isempty(pstack))//循環(huán)結(jié)束條件 { } if(proot){ } else { } proot = Pop(pstack);//指針出棧 flag = flags[p--];//相應(yīng)標志位出棧 if(flag==0)//如果標志位為0表示右子還未訪問過 { } else { } printf(“%2c”,proot->data);//打印數(shù)據(jù) proot = NULL;//將結(jié)點指針置空 flag =1;//將標志位置1，右子已訪問 flags[++p] = flag;//標志位入棧 Push(pstack,proot);//結(jié)點入棧 if(Isfull(pstack)){ } flags[++p] = 0;//標志位置0，并入棧 Push(pstack,proot);//結(jié)點入棧 proot=proot->left;//指針指向左子 printf(“棧滿，不能執(zhí)行入棧操作！”);return; proot = proot->right;//指針指向右子 Tnode A,B,C,D,E,F,G;//聲明結(jié)點變量 Stack stack;//聲明棧 Inittnode(&A,&B,&C,'A');//初始化結(jié)點 Inittnode(&B,NULL,&D,'B');Inittnode(&C,&E,&F,'C');Inittnode(&D,NULL,NULL,'D');Inittnode(&E,NULL,NULL,'E');Inittnode(&F,&G,NULL,'F');Inittnode(&G,NULL,NULL,'G');printf(“你定義的樹的結(jié)構(gòu)是：n”);printf(“A(B(D)C(E F(G)))n”);printf(“=====================下面是遍歷結(jié)果====================n”);printf(“=====================遞歸先序遍歷：====================n”);PreorderR(&A);printf(“n”);printf(“=====================非遞歸先序遍歷：==================n”);PreorderI(&A,&stack);printf(“n”);printf(“=====================遞歸中序遍歷：====================n”);InorderR(&A);printf(“n”);printf(“=====================非遞歸中序遍歷：==================n”);InorderI(&A,&stack);printf(“n”);PostorderR(&A);printf(“n”);PostorderI(&A,&stack); printf(“n”); /*一下是調(diào)用相應(yīng)的函數(shù)輸出遍歷結(jié)果*/ } printf(“=====================遞歸后序遍歷：====================n”); printf(“=====================非遞歸后序遍歷：==================n”); 五、遇到的問題及解決辦法 這部分我主要遇到如下兩個問題，其內(nèi)容和解決方法如下所列： 執(zhí)行程序時程序停止運行，其效果如圖： 解決方法：看到程序停止運行，推測可能的原因：遇到死循環(huán)、參數(shù)設(shè)置不合理或者結(jié)構(gòu)體沒有造好。首先對結(jié)構(gòu)體進行了檢查，各個成員聲明正常無誤，在對程序進行調(diào)試，程序正常跳出循環(huán)，因此最可能是自定義函數(shù)的參數(shù)設(shè)置的不合理，因此對調(diào)用的自定義函數(shù)進行相應(yīng)的改動，將參數(shù)由具體類型改為指針類型后，程序正常運行。 程序不停的輸出同一個結(jié)點的數(shù)據(jù)，其效果入圖： 解決方法：分析運行結(jié)果可知，第一不停的輸出證明遇到了死循環(huán)，第二輸出的是同一個結(jié)點的數(shù)據(jù)，表示指針沒有按預(yù)期進行指向，首先對程序進行調(diào)試，發(fā)現(xiàn)程序沒有添加循環(huán)結(jié)束條件，添加循環(huán)結(jié)束條件后，只能輸出樹的部分結(jié)點的數(shù)據(jù)，對標志位進行修改后，程序運行正常，也能正確輸出遍歷結(jié)果。 六、心得體會 通過這次作業(yè)真的受益匪淺，感觸良多： 首先，要提高編程能力，必須多動手，多實踐，而不是僅僅局限在書本上，更不能眼高手低。眼高手低，懶得動手，這就犯了編程人員的大忌。大一我們開始接觸C語言，這是我們接觸到的第一種編程語言，但是當時徒有對編程的興趣，卻沒有付諸行動，動手少，結(jié)果考試險過，通過這次作業(yè)，我再次看了C語言課本，邊看邊寫代碼，理解快，印象深刻，思維也活躍許多，狀態(tài)也好，真正的意識到，編程能力需要靠實踐來提升。當自己寫出意想的程序后，真的有些成就感。再者，在吳老師的指導(dǎo)和要求下，我們改掉了很多的編程壞習(xí)慣的同時也養(yǎng)成了良好的編程習(xí)慣，另一方面我們態(tài)度端正了很多，認真完成好每一項任務(wù)，這樣無形中提高了對自己的要求，同時也增強了我們的動手能力和編程能力。 七、附錄 運行結(jié)果截圖。第三篇：數(shù)據(jù)結(jié)構(gòu)-二叉樹的遍歷實驗報告
第四篇：數(shù)據(jù)結(jié)構(gòu)實驗報告——中序遍歷二叉樹
第五篇：數(shù)據(jù)結(jié)構(gòu)實驗報告-二叉樹的實現(xiàn)與遍歷
點擊咨詢 