掌握用指針類型描述、建立、遍歷二叉樹的運(yùn)算

1、掌握用指針類型描述、建立、遍歷二叉樹的運(yùn)算。洛陽理丄學(xué)院實(shí)驗(yàn)報告系部計算機(jī)系班級B110505學(xué)號B11050516姓名李滿意課程名稱數(shù)據(jù) 結(jié)構(gòu)實(shí)驗(yàn)日期2013. 04. 24實(shí)驗(yàn)名稱二叉樹的建立及遍歷成績實(shí)驗(yàn)LI的：掌握二義樹的結(jié)構(gòu)特征，掌握用指針類型描述、建立、遍歷二義樹的運(yùn)算。 實(shí)驗(yàn)條件：電腦一臺，VC+6. 0軟件。實(shí)驗(yàn)內(nèi)容與算法思想：內(nèi)容：建立一棵用二義鏈表方式存儲的二叉樹，并對其進(jìn)行遍歷（先序、中序、后 序），打印輸出遍歷結(jié)果?！净疽蟆繌逆I盤接受輸入先序序列，以二義鏈表作為存儲結(jié)構(gòu)，建立二 義樹（以先序來建立）并對其進(jìn)行遍歷（先序、中序、后序），然后將遍歷結(jié)果打印輸 出。要求釆

2、用遞歸和非遞歸兩種方法實(shí)現(xiàn)?！緶y試數(shù)據(jù)】ABC, DE, G ,F ,（其中，表示空格字符）輸出結(jié)果:先序序列為ABCDEGF中序序列為CBEGDFA后序序列為CGEFDBA算法思想：程序中使用遞歸和非遞歸兩種方法實(shí)現(xiàn)對二義樹的先序、中序及后序遍歷。遞 歸就是對自身的函數(shù)調(diào)用，遞歸遍歷中訪問根結(jié)點(diǎn)、遍歷左子樹、遍歷右子樹語句 的的順序決定了是在先序、中序、后序。非遞歸先序遍歷從根結(jié)點(diǎn)開始，只要當(dāng)前 結(jié)點(diǎn)存在，或者棧不空，則重復(fù)操作:？從當(dāng)前結(jié)點(diǎn)開始，訪問根結(jié)點(diǎn)、出棧，遍歷左子樹;？退棧，遍歷左子樹。非遞歸中序遍歷從根結(jié)點(diǎn)開始，只要當(dāng)前結(jié)點(diǎn)存在， 或者棧不空，則重復(fù)操作:？如果當(dāng)前結(jié)點(diǎn)存在，則進(jìn)

3、棧并遍歷左子樹;？否則退棧并 訪問，然后遍歷右子樹;非遞歸后序遍歷從根結(jié)點(diǎn)開始，只要當(dāng)前結(jié)點(diǎn)存在，或者 棧不空，則重復(fù)操作:？從當(dāng)前結(jié)點(diǎn)開始，進(jìn)棧并遍歷左子樹，直到左子樹為空;？如 果棧頂結(jié)點(diǎn)的右子樹為空，或者棧頂結(jié)點(diǎn)的右孩子為剛訪問過的結(jié)點(diǎn)，則退棧并訪 問，然后將半前結(jié)點(diǎn)指針置為空;？否則，遍歷右子樹運(yùn)行結(jié)果：試數(shù)據(jù)，ABC DE G F；ftBCDEGF ；CBEGDPA后序徉歹0為；CGEFDBR 韭遞歸先序遍歷：ftBGDEGF非遞歸中序遍歷CBEGDFft非遞歸后序遍歷CGEFDBfiany key to continue實(shí)驗(yàn)總結(jié)：通過這次實(shí)驗(yàn)我對二義樹有了更熟練的掌握，更清晰的認(rèn)識

4、。熟練掌握了二義樹的遍歷，并對使用非遞歸實(shí)現(xiàn)對二義樹的遍歷，使得我對非遞歸也更加熟練的掌 握，對以往知識起到了復(fù)習(xí)鞏固的作用。另外，感覺自己的編程能力也在不斷的進(jìn) 步之中，繼續(xù)努力，相信自己的數(shù)據(jù)結(jié)構(gòu)會學(xué)的很好，相信自己的編程技能也會提 高的，繼續(xù)努力。附:源程序:#includestdio h #includestdlib h typedef char DataType; ttdefine FALSE 0ttdefine TRUE 1typedef struct NodeDataType data;struct Node *Lchild;struct Node *Rchild;BiTNode

5、, *BiTree;typedef BiTree StackElementType; #define Stack_Size 50typedef structStackElementType elemStack_SizeZ;int top;SeqStack;void InitStack(SeqStack *S) S-top二T;int IsEmpty(SeqStack *S) if (S-top=-l)return 1:else return 0;void GreatBiTree(BiTree *root) char c;c=getchar ();辻(c二二)*root二NULL;*root=(

6、BiTNode *)malloc(sizeof(BiTNode);(*root)-data=c;GreatBiTree(&(*root)-LchiId);GreatBiTree(&(*root)-Rchild);void PreOrder (BiTree root) /*先序遍歷二叉樹,root為指向_.叉樹(或某一 子樹)根結(jié)點(diǎn)的指針*/ 辻(root!二NULL)printf (%c, root-data) ; /*訪問根結(jié)點(diǎn)*/PreOrder (root-LchiId) ; /*先序遍歷左子樹*/PreOrder (root-RchiId) ; /*先療;遍歷右子樹*/void InO

7、rder (BiTree root) /*中序遍歷二叉樹,root為指向二叉樹(或某一 子樹)根結(jié)點(diǎn)的指針*/ if (root!=NULL)InOrder (root -Lchild) ; /*中序遍歷左子樹*/printf (%c, root-data) ; /*訪問根結(jié)點(diǎn)*/InOrder (root -Rchild) ; /*中序遍歷右子樹*/void PostOrder (BiTree root) /*后序遍歷二叉樹,root為指向二叉樹(或某子樹)根結(jié)點(diǎn)的指針*/ if(root!二NULL)PostOrder (root -Lchild) ; /*后序遍歷左子樹*/PostOrd

8、er (root -Rchild) ; /*后序遍歷右子樹*/printf (%c： root-data) ; /*訪問根結(jié)點(diǎn)*/int Push(SeqStack *S, StackElementType x)if (Stop (Stack_Sizel)return (FALSE) : /*棧已滿*/S_top+;S-elemS-top二x;return(TRUE);int Pop (SeqStack *S, StackElementType *x)/*將棧S的棧頂元素彈出，放到x所指的存儲空間中*/if (S-top=l) /*棧為空*/return(FALSE);*x=S-elem ES

9、top;S-top; /*修改棧頂指針*/return(TRUE);int InOrderfeidigui (BiTree root) /*中序遍歷二叉樹的非遞歸算法*/ SeqStack S;BiTree p;InitStack (&S);p二root;while(p!=NULL .I !IsEmpty(&S)if (p!=NULL) /*根指針進(jìn)棧，遍歷左子樹*/Push (&S, p);p=pLchild;else /*根指針退棧，訪問根結(jié)點(diǎn)，遍歷右子樹*/Pop(&S, &p)；printf, pdata);p=p-Rchild;/*算法c*/void PostOrderfeidigu

10、i (BiTree root)BiTNode *p, *q;BiTNode *s;int top=0;int NUM二50;q二NULL;p=root;s=(BiTNode*)malloc(sizeof(BiTNode*)*NUM);/* NUM為預(yù)定義的常數(shù)*/while(p!=NULL I top!=0)while(p!=NULL)top+;stop=p;p=p-Lchild; /*遍歷左子樹*/if(top0) p二stop;辻(p-Rchild=NULL) I I (p-Rchild=q) /*無右孩子，或右孩子已遍歷過 printf C%c，z, p-data) : /* 訪問根結(jié)點(diǎn)

11、*/q二P； /*保存到q,為下一次已處理結(jié)點(diǎn)前驅(qū)*/top-;p二NULL;elsep=p-Rchild;free (s);void Preorderfeidigui (BiTree root) /*非遞歸先序遍歷二義樹*/SeqStack S;BiTree p;InitStack (&S);if (root=NULL) return;p=root;while(p!=NULL : i !IsEmpty(&S) while(p!=NULL) printf (%c, p-data); /*訪問結(jié)點(diǎn)的數(shù)據(jù)域*/Push (&S, p) ; /*將當(dāng)前抬針p壓棧*/P二p-Lch訂d; /*指針指向p的左孩子*/if (!IsEmpty(&S) Pop(&S, &p); /*從棧中彈出棧頂元素*/p二p-Rchild; /*指針指向p的右孩子結(jié)點(diǎn)*/void main()BiTree root:printfC請輸入二義樹先序序列測試數(shù)據(jù):”);GreatBiTree(&root);printfC先序序列為:)；PreOrder (root);printf(n);printf (中序序列為:”)；InOrder(root);printf(n);printfC后序序列