數據結構C語言版實驗五報告

1、實驗五一、實驗目的1、理解二叉樹的類型定義域性質。2、掌握二叉樹的二叉鏈表儲存結構的表示和實現方法。3、掌握二叉樹遍歷操作的算法實現。4、熟悉二叉樹遍歷操作的應用。二、實驗內容1、建立二叉樹的二叉鏈表儲存結構。2、實現二叉樹的先序、中序和后序三種遍歷操作(驗證性內容)。3、應用二叉樹的遍歷操作來實現判斷兒科二叉樹是否相等的操作(設計性內容)。4、求從二叉樹根結點到指定結點P之間的路徑(應用性設計內容)。三、驗證性實驗1、實驗要求編程實現如下功能：(1) 假如二叉樹的結點值是字符，根據輸入的一顆二叉樹的完整先序遍歷序列建立一顆 以二叉樹鏈表表示的二叉樹。(2) 對二叉樹進行先序、中序和后序遍歷操

2、作，并輸出表里序列，觀察輸出的序列是否 與邏輯上的序列一致。(3) 主程序中要求設計一個菜單，允許用戶通過菜單來多次選擇執(zhí)行哪一種遍歷操作。2、參考代碼：#include#includetypedef struct Bitnode(char data;struct Bitnode *lchild, *rchild;Bitnode,*Bitree;Bitree create (Bitree T)/ 創(chuàng)建樹(char x; scanf(%c，&x) : if(x=#)NULL;else 1T二(Bitree)malloc(sizeof(Bitnode); T-data=x;T-lchild=cre

3、ate(T-lchild) ; T-rchild=create(T-:rch訂d);Jretum T;Bitree preorder(Bitree T)/ 前序(if(T!二 NULL)printf (%c, T-data);T-lchild=preorder(T-lchild); T-rchild=preorder(T-rchild);return T;Bitree InOrderTraverse (Bitree T) / 中序(if(T!二 NULL)T-lchild=InOrderTraverse(T-lchild);printf (/z%c/z, T-data);T-rchild=In

4、OrderTraverse(T-rchild);)return T;Bitree PostOrderTraverse (Bitree T) / 后序(if(T!二 NULL)T-lchild=PostOrderTraverse(T-lchild); T-rchild=PostOrderTraverse (T-rchild); printf(c, T-data);)return T;int first二0,last二0;Bitree a10;int Enter(Bitree a,Bitree e)(last=last%10;alast+二e;return 0;Bitree Exit (Bitre

5、e a)(first=first%10; return afirst+;void LeveOrderTraverse (Bitree T) / 層序(Bitree K; Enter (a,T); if(T) while (first!二last) lK=Exit( a):printf (/z%cz，, K-data) ; if (K-lchild) Enter (a, K-lch訂d) ; if (K-rchild) Enter (a,K-rchild);void main()(int i二1;char x, y;Bitree T二NULL; printf (credte two treenz

6、/) ; T=create(T); int i;printfCl前序遍歷n2中序遍歷n3后序遍歷n4層序遍歷)；scanf (%d, &i);if (i二二1) preorder (T);if (i二二2)InOrderTraverse(T);if(i=3) PostOrderTraverse (T);if (i二二4)LeveOrderTraverse(T); printf (n)；四、設計性實驗編程實現根據二叉樹的先序遍歷序列和中序遍歷序列來建立兩顆二叉樹，并 判斷這兩顆二叉樹是否相等。(1) 實驗要求1、實現兩棵樹是否相同的判斷。(2) 程序代碼#include #includeSdef

7、ine Stack_Init_Size 100 typedef struct(char *base;char *top;int stacksize;SqStack;int InitStack(SqStack &S)(S.base=(char*)malloc(Stack_Init_Size*sizeof(char); if(!S. base) return0；S.top=S. base;S. st&cksize二Stack_Init_Size; return 1;int Push (SqStack &s, char e)(if (s.top-s.base=s. stacksize) return

8、 0;*s. top+二e;return 1;int Pop(SqStack &s, char &e)(if (s.top=s. base) return 0; e=*-一s.top; return 1;typedef struet Bitnode(char data;struct Bitnode *lch訂d, *rchild; Bitnode, *Bitree;Bitree create (Bitree T)/ 創(chuàng)建樹char x; scanf(c，&x);if (x二二#)T二NULL;elseT= (Bitree)malloc(sizeof(Bitnode);T-data二x;T-lc

9、hild=create(Tlchild);T-rchild=create(T-rchild);return T:Bitree otherpreorder (Bitree T, SqStack &S) 前序比較(if (T!=NULL)(Push(S, Tdata);T-lchild=otherpreorder(T-lchild, S);T-rchild=otherpreorder(T-rchild, S);return T;Bitree otherlnOrderTraverse(Bitree T, SqStack &s)/ 中序比較(if (T!=NULL)(T-lchild=otherlnO

10、rderTraverse(T-lchild, s);Push(s, T-data);T-rchild=otherlnOrderTraverse(T-rchild, s);return T;void main()(int i=l;char x, y;Bitree T=NULL;printf (create two treenz/):T=create (T);Bitree K=NULL;K=create (K);SqStack a, b;InitStack(a);InitStack(b);otherpreorder(T, a);otherpreorder(K, b);otherlnOrderTra

11、verse(T, a);otherlnOrderTraverse(K, b);for (:a. base!=a. top&b. base!二b. top;)Pop (a, x);Pop (b, y); if (x!=y)i=0;break;if(i=l)printf (equal!)；elseprintf(not equal!，z);printf (n)；五、應用性設計實驗 編程求從二叉樹根結點到指定結點P之間的路徑。(1) 實驗要求1、假設二叉樹的結點是字符，請給定一結點P,輸出從二叉樹的根節(jié)點到該結 點P的路徑。(2) 程序代碼：#include#include#includeSdefin

12、e STACK 100typedef struet Bitnode(char data;struct Bitnode *lch訂d,*rchild;Bitnode,*Bitree;Bitree create (Bitree T)/ 創(chuàng)建樹(char x;scanf (%c, &x);if (x二二#)T二NULL;elseT=(Bitree)malloc(sizeof(Bitnode); T-data二x;T-lchild=create(T-lchild);T-rchild=create(T-rchild);1return T;Bitree preorder (Bitree T)/ 前序(if

13、(T!二 NULL)printf(%c, T-data);T-lchild=preorder(T-lchild); T-rchild=preorder(T-rchiId);return T;typedef struet(Bitree *base;Bitree *top;int stacksize;SqStack;int InitStack(SqStack &s)(s. base=(Bitree *)malloc (STACK*sizeof (Bitree); if (! s base)return 0;s. top=s. base;s. stacksize=STACK;return 1;int

14、 GetTop(SqStack s,Bitree &e)(if (s. top=s. base)return 0;e 二*(s to p-1);return 1;int Push (SqStack &s, Bitree e)(*s top+二e;return 1;int Pop (SqStack &s, Bitree &e)(if (s. top=s. base)return 0;e=*-一s. top;return 1;Bitree select(Bitree T,SqStack &s,char a)(Bitree e;Push(s, T);if (T-da ta=a)for(;s. base!=s. top;)Bitree d; d二*s. base; printf(c，d-dat&); s.base+;exit (0);if (!T-lch 訂 d&!T-i*ch 訂 d)Pop(s, e);return NULL;if(T-lchild)T-lchild=select (T-lch訂d,s, a); if (T-rchild)T-rchild=select(T-rchild, s, a); if(!T-lchild&!T-rchild)Pop(s