數(shù)據(jù)結(jié)構(gòu)實驗報告-二叉樹的實現(xiàn)與遍歷9頁

1、數(shù)據(jù)結(jié)構(gòu)第六次實驗報告學生姓名學生班級學生學號指導老師重慶郵電大學計算機學院計算機專業(yè)實驗中心1、 實驗內(nèi)容1) 采用二叉樹鏈表作為存儲結(jié)構(gòu)，完成二叉樹的建立，先序、中序和后序以及按層次遍歷的操作，求所有葉子及結(jié)點總數(shù)的操作。2) 輸出樹的深度，最大元，最小元。 2、 需求分析遍歷二叉樹首先有三種方法，即先序遍歷，中序遍歷和后序遍歷。遞歸方法比較簡單，首先獲得結(jié)點指針如果指針不為空，且有左子，從左子遞歸到下一層，如果沒有左子，從右子遞歸到下一層，如果指針為空，則結(jié)束一層遞歸調(diào)用。直到遞歸全部結(jié)束。 下面重點來講述非遞歸方法：首先介紹先序遍歷：先序遍歷的順序是根 左 右，也就是說先訪問根結(jié)點然后

2、訪問其左子再然后訪問其右子。具體算法實現(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é)束。最后介紹后序遍

3、歷：后序遍歷的順序是左 右 根，后序遍歷是比較難的一種，首先需要建立兩個棧，一個用來存放結(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é)點指針

4、和棧均為空，遍歷結(jié)束。 三、詳細設(shè)計源代碼：#include<stdio.h>#define MAX 100 /表示棧的最大容量#define FULL 99/表示棧滿#define EMPTY -1/表示棧空typedef struct Tnode /定義結(jié)點char data;/存儲結(jié)點數(shù)據(jù) struct Tnode *left;/定義結(jié)點左子指針struct Tnode *right;/定義右子指針Tnode,*Pnode;/聲明Tnode類型的變量和指針typedef struct Stack/定義棧Pnode pnodeMAX;/存放數(shù)據(jù)int p;/棧頂指針Stack,

5、*Pstack;/定義Stack類型的變量和指針void Push (Pstack pstack,Pnode pnode)/入棧pstack->p +;pstack->pnodepstack->p = pnode;/賦值Pnode Pop(Pstack pstack)/出棧return pstack->pnodepstack->p-;Pnode Top (Pstack pstack)/看棧頂元素return pstack->pnodepstack->p;int Isempty (Pstack pstack)/棧判空if(pstack->p=EMP

6、TY)return 1;else return 0;int Isfull (Pstack pstack )/棧滿if (pstack ->p=FULL)return 1;else return 0;void Initstack (Pstack pstack)/初始化棧pstack->p=EMPTY;void Inittnode(Pnode root,Pnode left,Pnode right,char data)/初始化結(jié)點root->left=left;root->right = right;root->data = data;void PreorderR(P

7、node proot)/遞歸先序遍歷算法if(proot)printf("%2c",proot->data);PreorderR(proot->left);PreorderR(proot->right);void InorderR(Pnode proot)/遞歸中序遍歷算法if(proot)InorderR(proot->left);printf("%2c",proot->data);InorderR(proot->right);void PostorderR(Pnode proot)/遞歸后序遍歷算法if(proot

8、)PostorderR(proot->left);PostorderR(proot->right);printf("%2c",proot->data);void PreorderI(Pnode proot,Pstack pstack)/非遞歸先序遍歷算法Initstack(pstack);/初始化棧while(proot|!Isempty(pstack)/如果?？詹⑶医Y(jié)點指針空，則結(jié)束循環(huán)if(proot)printf("%2c",proot->data);if(Isfull(pstack)/如果棧滿不能執(zhí)行入棧操作printf(

9、"棧滿，不能執(zhí)行入棧操作！");return;Push(pstack,proot);/入棧proot=proot->left;/指針指向左子else if(Isempty(pstack)/?？諘r不能出棧printf("?？?，不能執(zhí)行出棧操作！");return;proot = Pop(pstack);/執(zhí)行出棧操作proot=proot->right;/指針指向右子void InorderI(Pnode proot,Pstack pstack)/非遞歸中序遍歷算法Initstack(pstack);/初始化棧while(proot|!Isem

10、pty(pstack)/循環(huán)結(jié)束條件if(proot)if(Isfull(pstack)printf("棧滿，不能執(zhí)行入棧操作！");return;Push(pstack,proot);/執(zhí)行入棧操作proot = proot->left;/指針指向左子else if(Isempty(pstack)printf("?？眨荒軋?zhí)行出棧操作！");return ;proot = Pop(pstack);/出棧printf("%2c",proot->data);/打印數(shù)據(jù)proot=proot->right;/指針指向右子

11、void PostorderI(Pnode proot,Pstack pstack)/非遞歸后續(xù)遍歷算法int flagsMAX;/定義標志位棧int p =-1;/初始化標志位棧int flag;/存放標志位Initstack(pstack);/初始化棧while(proot|!Isempty(pstack)/循環(huán)結(jié)束條件if(proot)if(Isfull(pstack)printf("棧滿，不能執(zhí)行入棧操作！");return ;flags+p = 0;/標志位置0，并入棧Push(pstack,proot);/結(jié)點入棧proot=proot->left;/指針

12、指向左子elseproot = Pop(pstack);/指針出棧flag = flagsp-;/相應(yīng)標志位出棧if(flag=0)/如果標志位為0表示右子還未訪問過flag =1;/將標志位置1，右子已訪問flags+p = flag;/標志位入棧Push(pstack,proot);/結(jié)點入棧 proot = proot->right;/指針指向右子else printf("%2c",proot->data);/打印數(shù)據(jù)proot = NULL;/將結(jié)點指針置空void main ()Tnode A,B,C,D,E,F,G;/聲明結(jié)點變量Stack stac

13、k;/聲明棧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

14、9;);printf("你定義的樹的結(jié)構(gòu)是：n"); /*一下是調(diào)用相應(yīng)的函數(shù)輸出遍歷結(jié)果*/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("=遞歸中序遍歷：=

15、n");InorderR(&A);printf("n");printf("=非遞歸中序遍歷：=n");InorderI(&A,&stack);printf("n"); printf("=遞歸后序遍歷：=n");PostorderR(&A);printf("n"); printf("=非遞歸后序遍歷：=n");PostorderI(&A,&stack); printf("n");5、 遇到的問題及解決

16、辦法 這部分我主要遇到如下兩個問題，其內(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è)真的受益匪淺，感觸良多：首先，要提高編程能力，必須多動手，多實踐，而不是僅僅局限在書本上，更不能眼高手低。眼高手低，懶得動手，這就犯了編程人員的大忌。大