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

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

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

3、遍歷是比較難的一種，首先需要建立兩個(gè)棧，一個(gè)用來(lái)存放結(jié)點(diǎn)的指針，另一個(gè)存放標(biāo)志位，也是首先訪問(wèn)根結(jié)點(diǎn)，如果結(jié)點(diǎn)的指針不為空，根結(jié)點(diǎn)入棧，與之對(duì)應(yīng)的標(biāo)志位也隨之入標(biāo)志位棧，并賦值0，表示該結(jié)點(diǎn)的右子還沒(méi)有訪問(wèn)，指針指向該結(jié)點(diǎn)的左子，如果結(jié)點(diǎn)指針為空，表示左子訪問(wèn)完成，父結(jié)點(diǎn)出棧，與之對(duì)應(yīng)的標(biāo)志位也隨之出棧，如果相應(yīng)的標(biāo)志位值為0，表示右子樹(shù)還沒(méi)有訪問(wèn)，指針指向其右子，父結(jié)點(diǎn)再次入棧，與之對(duì)應(yīng)的標(biāo)志位也入棧，但要給標(biāo)志位賦值為1，表示右子訪問(wèn)過(guò)。如果相應(yīng)的標(biāo)志位值為1，表示右子樹(shù)已經(jīng)訪問(wèn)完成，此時(shí)要輸出相應(yīng)結(jié)點(diǎn)的數(shù)據(jù)，同時(shí)將結(jié)點(diǎn)指針賦值為空，如此循環(huán)直至結(jié)點(diǎn)指針和棧均為空，遍歷結(jié)束。 三、詳細(xì)設(shè)計(jì)

4、源代碼：#include#define MAX 100 /表示棧的最大容量#define FULL 99/表示棧滿#define EMPTY -1/表示?？誸ypedef struct Tnode /定義結(jié)點(diǎn)char data;/存儲(chǔ)結(jié)點(diǎn)數(shù)據(jù) struct Tnode *left;/定義結(jié)點(diǎn)左子指針struct Tnode *right;/定義右子指針Tnode,*Pnode;/聲明Tnode類型的變量和指針typedef struct Stack/定義棧Pnode pnodeMAX;/存放數(shù)據(jù)int p;/棧頂指針Stack,*Pstack;/定義Stack類型的變量和指針void Push

5、 (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)return 1;else return 0;int Isfull (Pstack pstack )/棧滿if (pstac

6、k -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é)點(diǎn)root-left=left;root-right = right;root-data = data;void PreorderR(Pnode proot)/遞歸先序遍歷算法if(proot)printf(%2c,proot-data);PreorderR(proot-left);PreorderR(p

7、root-right);void InorderR(Pnode proot)/遞歸中序遍歷算法if(proot)InorderR(proot-left);printf(%2c,proot-data);InorderR(proot-right);void PostorderR(Pnode proot)/遞歸后序遍歷算法if(proot)PostorderR(proot-left);PostorderR(proot-right);printf(%2c,proot-data);void PreorderI(Pnode proot,Pstack pstack)/非遞歸先序遍歷算法Initstack(p

8、stack);/初始化棧while(proot|!Isempty(pstack)/如果?？詹⑶医Y(jié)點(diǎn)指針空，則結(jié)束循環(huán)if(proot)printf(%2c,proot-data);if(Isfull(pstack)/如果棧滿不能執(zhí)行入棧操作printf(棧滿，不能執(zhí)行入棧操作！);return;Push(pstack,proot);/入棧proot=proot-left;/指針指向左子else if(Isempty(pstack)/?？諘r(shí)不能出棧printf(?？?，不能執(zhí)行出棧操作！);return;proot = Pop(pstack);/執(zhí)行出棧操作proot=proot-right;/指

9、針指向右子void InorderI(Pnode proot,Pstack pstack)/非遞歸中序遍歷算法Initstack(pstack);/初始化棧while(proot|!Isempty(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

10、(%2c,proot-data);/打印數(shù)據(jù)proot=proot-right;/指針指向右子void PostorderI(Pnode proot,Pstack pstack)/非遞歸后續(xù)遍歷算法int flagsMAX;/定義標(biāo)志位棧int p =-1;/初始化標(biāo)志位棧int flag;/存放標(biāo)志位Initstack(pstack);/初始化棧while(proot|!Isempty(pstack)/循環(huán)結(jié)束條件if(proot)if(Isfull(pstack)printf(棧滿，不能執(zhí)行入棧操作！);return ;flags+p = 0;/標(biāo)志位置0，并入棧Push(pstack,p

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

12、量Stack stack;/聲明棧Inittnode(&A,&B,&C,A);/初始化結(jié)點(diǎn)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(你定義的樹(shù)的結(jié)構(gòu)是：n); /*一下是調(diào)用相應(yīng)的函數(shù)輸出遍歷結(jié)果*/printf(A(B(D)C(E F(G)n);printf(=下面是遍歷結(jié)果=n);printf(=遞歸先序遍歷：=n);Preo

13、rderR(&A);printf(n);printf(=非遞歸先序遍歷：=n);PreorderI(&A,&stack);printf(n);printf(=遞歸中序遍歷：=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、 遇到的問(wèn)題及解決辦法 這部分我主要遇到如下兩個(gè)問(wèn)題，其內(nèi)容和解決方法如

14、下所列： 執(zhí)行程序時(shí)程序停止運(yùn)行，其效果如圖： 解決方法：看到程序停止運(yùn)行，推測(cè)可能的原因：遇到死循環(huán)、參數(shù)設(shè)置不合理或者結(jié)構(gòu)體沒(méi)有造好。首先對(duì)結(jié)構(gòu)體進(jìn)行了檢查，各個(gè)成員聲明正常無(wú)誤，在對(duì)程序進(jìn)行調(diào)試，程序正常跳出循環(huán)，因此最可能是自定義函數(shù)的參數(shù)設(shè)置的不合理，因此對(duì)調(diào)用的自定義函數(shù)進(jìn)行相應(yīng)的改動(dòng)，將參數(shù)由具體類型改為指針類型后，程序正常運(yùn)行。 程序不停的輸出同一個(gè)結(jié)點(diǎn)的數(shù)據(jù)，其效果入圖： 解決方法：分析運(yùn)行結(jié)果可知，第一不停的輸出證明遇到了死循環(huán)，第二輸出的是同一個(gè)結(jié)點(diǎn)的數(shù)據(jù)，表示指針沒(méi)有按預(yù)期進(jìn)行指向，首先對(duì)程序進(jìn)行調(diào)試，發(fā)現(xiàn)程序沒(méi)有添加循環(huán)結(jié)束條件，添加循環(huán)結(jié)束條件后，只能輸出樹(shù)的部分結(jié)點(diǎn)的數(shù)據(jù)，對(duì)標(biāo)志位進(jìn)行修改后，程序運(yùn)行正常，也能正確輸出遍歷結(jié)果。六、心得體會(huì) 通過(guò)這次作業(yè)真的受益匪淺，感觸良多：首先，要提高編程能力，必須多動(dòng)手，多實(shí)踐，而不是僅僅局限在書(shū)本上，更不能眼高手低。眼高手低，懶得動(dòng)手，這就犯了編程人員的大忌。大一我們開(kāi)始接觸C語(yǔ)言，這是我們接觸到的第一種編程語(yǔ)言，但是當(dāng)時(shí)徒