數(shù)據(jù)結構實驗報告_二叉樹的實現(xiàn)與遍歷

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

2、如果結點的指針不為空，結點指針入棧， 輸出相應結點的數(shù)據(jù)，同時指針指向其左子，如果結點的指針為空，表示左 子樹訪問結束，棧頂結點指針出棧，指針指向其右子，對其右子樹進行訪問， 如此循環(huán)，直至結點指針和棧均為空時，遍歷結束。再次介紹中序遍歷：中序遍歷的順序是左 根右，中序遍歷和先序遍歷思想差不多，只是打印順 序稍有變化。具體實現(xiàn)算法如下：如果結點指針不為空，結點入棧，指針指 向其左子，如果指針為空，表示左子樹訪問完成，則棧頂結點指針出棧，并 輸出相應結點的數(shù)據(jù)，同時指針指向其右子，對其右子樹進行訪問。如此循 環(huán)直至結點指針和棧均為空，遍歷結束。最后介紹后序遍歷：后序遍歷的順序是左 右 根，后序遍

3、歷是比較難的一種，首先需要建立兩個 棧，一個用來存放結點的指針，另一個存放標志位，也是首先訪問根結點， 如果結點的指針不為空，根結點入棧，與之對應的標志位也隨之入標志位棧， 并賦值0,表示該結點的右子還沒有訪問，指針指向該結點的左子，如果結 點指針為空，表示左子訪問完成，父結點出棧，與之對應的標志位也隨之出 棧，如果相應的標志位值為0,表示右子樹還沒有訪問，指針指向其右子， 父結點再次入棧，與之對應的標志位也入棧，但要給標志位賦值為1，表示右子訪問過。如果相應的標志位值為 1，表示右子樹已經(jīng)訪問完成，此時要 輸出相應結點的數(shù)據(jù)，同時將結點指針賦值為空，如此循環(huán)直至結點指針和 棧均為空，遍歷結束

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

5、義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=EMPTY)r

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

7、root)/遞歸先序遍歷算法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)Posto

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

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

10、k)循環(huán)結束條件if(proot)if(lsfull(pstack)printf("棧滿，不能執(zhí)行入棧操作！");return;Push(pstack,proot); 執(zhí)行入棧操作 proot = proot->left; 指針指向左子elseif(lsempty(pstack)printf("?？?，不能執(zhí)行出棧操作！");return ;proot = Pop(pstack);/ 出棧printf("%2c",proot->data);打印數(shù)據(jù)proot=proot->right;指針指向右子void Postor

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

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

13、棧lnittnode(&A,&B,&C,'A');初始化結點lnittnode(&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(”你定義的

14、樹的結構是：n");/*一下是調(diào)用相應的函數(shù)輸出遍歷結果*/printf("A(B(D)C(E F(G)n");printf(”=下面是遍歷結果=n"); printf(”=遞歸先序遍歷：=n"); PreorderR(&A);printf("n");printf("=非遞歸先序遍歷：=n");Preorderl(&A,&stack);printf("n");printf("=遞歸中序遍歷：=n");InorderR(&A);prin

15、tf("n");printf("=非遞歸中序遍歷：=n");InorderI(&A,& stack);printf("n");printf("=遞歸后序遍歷：=n");PostorderR(&A);printf("n");printf("=非遞歸后序遍歷：=n");Postorderl(&A,& stack);printf("n");五、遇到的問題及解決辦法這部分我主要遇到如下兩個問題，其內(nèi)容和解決方法如下所列： 執(zhí)

16、行程序時程序停止運行，其效果如圖：解決方法：看到程序停止運行，推測可能的原因：遇到死循環(huán)、參數(shù)設置不合 理或者結構體沒有造好。首先對結構體進行了檢查，各個成員聲明正常無誤，在 對程序進行調(diào)試，程序正常跳出循環(huán)，因此最可能是自定義函數(shù)的參數(shù)設置的不 合理，因此對調(diào)用的自定義函數(shù)進行相應的改動， 將參數(shù)由具體類型改為指針類 型后，程序正常運行。程序不停的輸出同一個結點的數(shù)據(jù)，其效果入圖：'C：U$?|5WFriy鎬沽芻二匸療尹忌二童悄的PF Drbj了JT1 冃"LMJU.”DJDLDEblJDDDDDEDLiDDDDDDCiLDDEDJDJELlJLiDDDJDLDLbDDDJ

17、DCCLbDDDDDDCriLiDDDDDDOELljDDJDXL 亠 DDDDOriiDDDDTEDDDDDDDDDErDDDDDDDrDDDDDDDCErDDDDODDDWDDDDTCDDDDDDDDDEEDDDODDOOTEDDDDiraKDDDDDDDDDDDDDDEWDDDDDBDDIIlDDDDDDmDDDDDDDOIIlDDDDDDDDnCDDDDDODD DDDDDDDDDDDDDDDDDDDDrWDDDDDDDDDDMmDDIOCnDDDDDDDnCDDDDDDDDDMDDDCiDDnDDDDDDOnD _!_吐山 JDJUElJLiDDDDJlJULbDDBJDJLllJi

18、iDDDJJElJUjDDDJDUELlJDBDDJDLlJLiDDDDJLDLlJLrDDJDJUL pHDCI ITDDTD 如匚 DDDDDMDCT DEMDOrT MDDD：i 尢 M DDdMETDDDDDD 如CDMDDMDCT MDDBMrD bDJDUbEDDDJDJDLDLiDDDDJDULLiDDUJDJLLLiLiDDJJJLLLLiDDDJDDLLLiDUDDJDLDLiDDDDJLUIlJLiDDJDJLLLD3OTEnDn3DDDEnDDDDD3DOnrDDDD3DrnTiDDDDDriirnDDDDDrDPDDnDDDDrnriDDDDDDODnriDD3D3DD

19、 rDJDDL.LDDD3DEbL'DDDDDDOLLiDDDJDXLLiLiDDl)DDClJLliDDDDDUELLirUDDDDt；L£'DDDDDDD£UDDUJDDDD hmorriTiDDrorDDi：jiDnDnDDDDrTDDiEmDTiriTMDDDDi®DDDDDDnTrinTwmrriiDriDT)DDDOinDEiroTDrT pDDDDDEDDDDDDDEDDDDDDDXDDDDDDDJDDDDDDDDDCEDDDDDDXDDDDDDDDDDDDDDDDDXDCDDDDDJDD pOJtXrarDDDDIWDCDDDDDD

20、DDDDDDDDDDiDWDIJDLDDDCDDDDDIIIXWDDDDDDnETirinDBDODOriPDnDriTE pDDDDDDDEDDimimDDDIDCDDDDIWQimDBDDDDDDBDDDDDDtnDDDDLWIXDDDD 皿 DCDDDDDDDEd toDDDDEDDDDDDDDBDDDDDDDDDDDDDODODrDDDDBDDDBDDDDDBCODDDDDDDDDrCDDDDDDDDDEDDDBDODD I)DJDC'DLiDDDDDDDEEDDDDD3DOELiDED3DODIDBDDDDDCEDDDDJDjELiDDDDDDDCEDDDDD3DOELiDD

21、DJDDDD bnODCIWDDDDIWIffiDDDDDDDDDDDDDDDDDDDDDDDinffinCDDDDDCBDDDDDDOBCDDDDDDnDnDIlDDDDOro pDODDDEDDDDDDOECDDDDDDDDDDDDDDDODDDDDDBDDDCDDDDDDDDDDDDDDDODDCDEDDDDDDDCDDDDDODD bDDDErDDDDTDDDDDDDDDDDDDrDDTDDnDDDDDDCnDDDIIDDDEEDDDDDDOTCDEDDDDDCOrDDDDDCCD UDJDL)lJlJDDDJDDUEDLiDDl)DJlX)LDDDDJDJLLDl)I)DBDD£UnDDDDJDL)LLlJDDDDJDEDLiDDi)DiJDUljlJDDDJD