第一篇：數(shù)據(jù)結(jié)構實驗報告-二叉樹的實現(xiàn)與遍歷
《數(shù)據(jù)結(jié)構》 第六次實驗報告
學生姓名 學生班級 學生學號 指導老師
重慶郵電大學計算機學院 計算機專業(yè)實驗中心
一、實驗內(nèi)容
1)采用二叉樹鏈表作為存儲結(jié)構，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結(jié)點總數(shù)的操作。2)輸出樹的深度，最大元，最小元。
二、需求分析
遍歷二叉樹首先有三種方法，即先序遍歷，中序遍歷和后序遍歷。遞歸方法比較簡單，首先獲得結(jié)點指針如果指針不為空，且有左子，從左子遞歸到下一層，如果沒有左子，從右子遞歸到下一層，如果指針為空，則結(jié)束一層遞歸調(diào)用。直到遞歸全部結(jié)束。下面重點來講述非遞歸方法： 首先介紹先序遍歷：
先序遍歷的順序是根 左 右，也就是說先訪問根結(jié)點然后訪問其左子再然后訪問其右子。具體算法實現(xiàn)如下：如果結(jié)點的指針不為空，結(jié)點指針入棧，輸出相應結(jié)點的數(shù)據(jù)，同時指針指向其左子，如果結(jié)點的指針為空，表示左子樹訪問結(jié)束，棧頂結(jié)點指針出棧，指針指向其右子，對其右子樹進行訪問，如此循環(huán)，直至結(jié)點指針和棧均為空時，遍歷結(jié)束。
再次介紹中序遍歷：
中序遍歷的順序是左 根 右，中序遍歷和先序遍歷思想差不多，只是打印順序稍有變化。具體實現(xiàn)算法如下：如果結(jié)點指針不為空，結(jié)點入棧，指針指向其左子，如果指針為空，表示左子樹訪問完成，則棧頂結(jié)點指針出棧，并輸出相應結(jié)點的數(shù)據(jù)，同時指針指向其右子，對其右子樹進行訪問。如此循環(huán)直至結(jié)點指針和棧均為空，遍歷結(jié)束。最后介紹后序遍歷：
后序遍歷的順序是左 右 根，后序遍歷是比較難的一種，首先需要建立兩個棧，一個用來存放結(jié)點的指針，另一個存放標志位，也是首先訪問根結(jié)點，如果結(jié)點的指針不為空，根結(jié)點入棧，與之對應的標志位也隨之入標志位棧，并賦值0，表示該結(jié)點的右子還沒有訪問，指針指向該結(jié)點的左子，如果結(jié)點指針為空，表示左子訪問完成，父結(jié)點出棧，與之對應的標志位也隨之出棧，如果相應的標志位值為0，表示右子樹還沒有訪問，指針指向其右子，父結(jié)點再次入棧，與之對應的標志位也入棧，但要給標志位賦值為1，表示右子訪問過。如果相應的標志位值為1，表示右子樹已經(jīng)訪問完成，此時要輸出相應結(jié)點的數(shù)據(jù)，同時將結(jié)點指針賦值為空，如此循環(huán)直至結(jié)點指針和棧均為空，遍歷結(jié)束。
三、詳細設計
源代碼：
#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--];//相應標志位出棧 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é)構是：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)用相應的函數(shù)輸出遍歷結(jié)果*/ } printf(“=====================遞歸后序遍歷：====================n”); printf(“=====================非遞歸后序遍歷：==================n”); 五、遇到的問題及解決辦法 這部分我主要遇到如下兩個問題，其內(nèi)容和解決方法如下所列： 執(zhí)行程序時程序停止運行，其效果如圖： 解決方法：看到程序停止運行，推測可能的原因：遇到死循環(huán)、參數(shù)設置不合理或者結(jié)構體沒有造好。首先對結(jié)構體進行了檢查，各個成員聲明正常無誤，在對程序進行調(diào)試，程序正常跳出循環(huán)，因此最可能是自定義函數(shù)的參數(shù)設置的不合理，因此對調(diào)用的自定義函數(shù)進行相應的改動，將參數(shù)由具體類型改為指針類型后，程序正常運行。 程序不停的輸出同一個結(jié)點的數(shù)據(jù)，其效果入圖： 解決方法：分析運行結(jié)果可知，第一不停的輸出證明遇到了死循環(huán)，第二輸出的是同一個結(jié)點的數(shù)據(jù)，表示指針沒有按預期進行指向，首先對程序進行調(diào)試，發(fā)現(xiàn)程序沒有添加循環(huán)結(jié)束條件，添加循環(huán)結(jié)束條件后，只能輸出樹的部分結(jié)點的數(shù)據(jù)，對標志位進行修改后，程序運行正常，也能正確輸出遍歷結(jié)果。 六、心得體會 通過這次作業(yè)真的受益匪淺，感觸良多： 首先，要提高編程能力，必須多動手，多實踐，而不是僅僅局限在書本上，更不能眼高手低。眼高手低，懶得動手，這就犯了編程人員的大忌。大一我們開始接觸C語言，這是我們接觸到的第一種編程語言，但是當時徒有對編程的興趣，卻沒有付諸行動，動手少，結(jié)果考試險過，通過這次作業(yè)，我再次看了C語言課本，邊看邊寫代碼，理解快，印象深刻，思維也活躍許多，狀態(tài)也好，真正的意識到，編程能力需要靠實踐來提升。當自己寫出意想的程序后，真的有些成就感。再者，在吳老師的指導和要求下，我們改掉了很多的編程壞習慣的同時也養(yǎng)成了良好的編程習慣，另一方面我們態(tài)度端正了很多，認真完成好每一項任務，這樣無形中提高了對自己的要求，同時也增強了我們的動手能力和編程能力。 七、附錄 運行結(jié)果截圖。 實驗報告 課程名：數(shù)據(jù)結(jié)構（C語言版）實驗名：二叉樹的遍歷 姓名： 班級： 學號： 時間：2014.11.03 一 實驗目的與要求 1.掌握二叉樹的存儲方法 2.掌握二叉樹的三種遍歷方法 3.實現(xiàn)二叉樹的三種遍歷方法中的一種 二 實驗內(nèi)容 ? 接受用戶輸入一株二叉樹 ? 輸出這株二叉樹的前根, 中根, 后根遍歷中任意一種的順序 三 實驗結(jié)果與分析 //*********************************************************** //頭文件 #include #define OK 1 #define ERROR 0 #define OVERFLOW 0 //*********************************************************** typedef struct BiTNode { //二叉樹二叉鏈表存儲結(jié)構 char data;struct BiTNode *lChild,*rChild;}BiTNode,*BiTree;//*********************************************************** int CreateBiTree(BiTree &T){ //按先序次序輸入二叉中樹結(jié)點的值，空格表示空樹 //構造二叉鏈表表示的二叉樹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é)構，先序遍歷二叉樹的遞歸算法 if(T){ printf(“%c”,T->data);PreOrderTraverse(T->lChild);PreOrderTraverse(T->rChild);} } /***********************************************************/ void InOrderTraverse(BiTree T){ //采用二叉鏈表存儲結(jié)構，中序遍歷二叉樹的遞歸算法 if(T){ InOrderTraverse(T->lChild);printf(“%c”,T->data);InOrderTraverse(T->rChild);} } //*********************************************************** void PostOrderTraverse(BiTree T){ //采用二叉鏈表存儲結(jié)構，后序遍歷二叉樹的遞歸算法 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班 學號：57000211 姓名：徐敏 實驗報告 一，實驗目的： ·掌握二叉樹的鏈式存儲結(jié)構； ·掌握構造二叉樹的方法； ·加深對二叉樹的中序遍歷的理解； 二，實驗方法： ·用遞歸調(diào)用算法中序遍歷二叉樹。三，實驗步驟： ·通過鏈式存儲建立一顆二叉樹。 ·設計一個算法實現(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班 學號：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班 學號：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】;六，上機實驗體會： ·體會到熟練掌握各種程序算法的重要性； ·通過上機練習，充分理解了鏈式建立二叉樹的算法； ·形象的了解二叉樹的結(jié)構，能夠熟練的進行先序，中序，后序遍歷二叉樹。 數(shù)據(jù)結(jié)構程序設計報告 學院： 班級： 學號： 姓名： 實驗名稱：二叉樹的建立與遍歷 一、實驗目的： 1.掌握二叉樹的二叉鏈表存儲結(jié)構； 2.掌握二叉樹創(chuàng)建方法； 3.掌握二叉樹的先序、中序、后序的遞歸實現(xiàn)方法。 二、實驗內(nèi)容和要求： 創(chuàng)建二叉樹，分別對該二叉樹進行先序、中序、后序遍歷，并輸出遍歷結(jié)果。 三、叉樹的建立與遍歷代碼如下： #include };typedef struct tnode TNODE; TNODE *creat(void){ TNODE *root,*p;TNODE *queue[50];char data;struct tnode *lchild,*rchild; int front=0,rear=-1,counter=0;//初始隊列中需要的變量front、rear和計數(shù)器counter char ch;printf(“建立二叉樹，請輸入結(jié)點:（#表示虛節(jié)點,!表示結(jié)束)n”); ch=getchar(); while(ch!='!'){ if(ch!='#') { p=(TNODE *)malloc(sizeof(TNODE)); p->data=ch; p->lchild=NULL; p->rchild=NULL;rear++; queue[rear]=p;//把非#的元素入隊 if(rear==0)//如果是第一個元素，則作為根節(jié)點 { } else { if(counter%2==1)//奇數(shù)時與其雙親的左子樹連接 { } if(counter%2==0)//偶數(shù)時與其雙親的右子樹連接 { queue[front]->rchild=p;queue[front]->lchild=p;root=p;counter++; } } } } front++; counter++; else//為#時，計數(shù)，但不連接結(jié)點 { if(counter%2==0) front++;counter++; } ch=getchar();} return root;void preorder(TNODE *bt)//先序遍歷 { if(bt!=NULL){ printf(“%c ”,bt->data);preorder(bt->lchild);preorder(bt->rchild); } } void inorder(TNODE *bt)//中序遍歷 { if(bt!=NULL){ inorder(bt->lchild);printf(“%c ”,bt->data);inorder(bt->rchild); } } void postorder(TNODE *bt)//后序遍歷 { if(bt!=NULL){ postorder(bt->lchild);postorder(bt->rchild);printf(“%c ”,bt->data); } } int main(){ TNODE *root; root=creat();printf(“遞歸先序遍歷是:”); preorder(root); printf(“n”);printf(“遞歸中序遍歷是：”);inorder(root);printf(“n”); } printf(“遞歸后序遍歷是：”);postorder(root);printf(“n”);return 0; 四、程序運行結(jié)果： 五、程序設計指導： 1.創(chuàng)建二叉樹的算法：首先對一般的二叉樹，添加若干個虛結(jié)點使其成為完全二叉樹，然后依次輸入結(jié)點信息，若輸入的結(jié)點不是虛結(jié)點，則建立一個新結(jié)點，若是第一個，則令其為根結(jié)點，否則將新結(jié)點鏈接至它的雙親結(jié)點上。如此重復下去，直至遇到輸入結(jié)束符（自定）為止。為了使新結(jié)點能夠與雙親結(jié)點正確相連，并考慮到這種方法中先建立的結(jié)點其孩子結(jié)點也一定先建立的特點，可以設置一個指針類型的數(shù)組構成的隊列來保存已輸入結(jié)點的地址，并使隊尾(rear)指向當前輸入的結(jié)點，隊頭(front)指向這個結(jié)點的雙親結(jié)點的前一個位置。由于根結(jié)點的地址放在隊列的第一個單元里，所以當rear為奇數(shù)時，則rear所指的結(jié)點應作為左孩子與其雙親鏈接，否則rear所指的結(jié)點應作為右孩子與其雙親鏈接。若雙親結(jié)點或孩子結(jié)點為虛結(jié)點，則無須鏈接。若一個雙親結(jié)點與兩個孩子鏈接完畢，則進行出隊操作，使隊頭指針指向下一個待鏈接的雙親結(jié)點。 2.void preorder(TNODE *bt)函數(shù)：利用遞歸的思想，不斷嵌套循環(huán)，讀取結(jié)點元素，在每個循環(huán)中每次先讀取，再進行進入下一個遞歸循環(huán)中。 3.void inorder(TNODE *bt)函數(shù) ：利用遞歸的思想，不斷嵌套循環(huán)，讀取結(jié)點元素，在每個循環(huán)中每次先左子樹，再讀取結(jié)點元素，再進行進入下一個遞歸循環(huán)中。 4.void postorder(TNODE *bt)函數(shù)：利用遞歸的思想，不斷嵌套循環(huán)，讀取結(jié)點元素，在每個循環(huán)中每次先分別進入左右子樹，再進行讀取，再進行進入下一個遞歸循環(huán)中。 六、心得體會： 本次數(shù)據(jù)結(jié)構程序設計對我有一定的幫助。通過這次的實踐，使我對數(shù)據(jù)結(jié)構這門課程有了更深入地了解。在寫程序的過程中，我重復地讀課本上的知識，并且漸漸領悟到數(shù)據(jù)結(jié)構編程的方法。在編程中，雖然遇到了一些困難，但我并不氣餒。當程序運行出來時，我感到了快樂。總之，通過自己地探索和努力，思維得到了鍛煉，編程能力也有了較大地改善。 班級：計算機11-2 學號：40 姓名：朱報龍 成績：_________ 實驗七 二叉樹操作驗證 一、實驗目的 ⑴ 掌握二叉樹的邏輯結(jié)構； ⑵ 掌握二叉樹的二叉鏈表存儲結(jié)構； ⑶ 掌握基于二叉鏈表存儲的二叉樹的遍歷操作的實現(xiàn)。 二、實驗內(nèi)容 ⑴ 建立一棵含有n個結(jié)點的二叉樹，采用二叉鏈表存儲； ⑵ 前序（或中序、后序）遍歷該二叉樹。 三、設計與編碼 #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é) 多練習，多上機，耐心調(diào)試程序，找出錯誤，多總結(jié)。第二篇：數(shù)據(jù)結(jié)構-二叉樹的遍歷實驗報告
第三篇：數(shù)據(jù)結(jié)構實驗報告——中序遍歷二叉樹
第四篇：二叉樹遍歷課程設計】
第五篇：數(shù)據(jù)結(jié)構二叉樹操作驗證實驗報告
點擊咨詢 