數(shù)據(jù)結(jié)構(gòu)樹(shù)和二叉樹(shù)實(shí)驗(yàn)報(bào)告

1、.數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱樹(shù)和二叉樹(shù)實(shí)驗(yàn)序號(hào)5實(shí)驗(yàn)日期姓 名院系班 級(jí)學(xué) 號(hào)專 業(yè)指導(dǎo)教師成 績(jī)教師評(píng)語(yǔ)一、實(shí)驗(yàn)?zāi)康暮鸵?1)掌握樹(shù)的相關(guān)概念，包括樹(shù)、結(jié)點(diǎn)的度、樹(shù)的度、分支結(jié)點(diǎn)、葉子結(jié)點(diǎn)、兒子結(jié)點(diǎn)、雙親結(jié)點(diǎn)、樹(shù)的深度、森林等定義。(2)掌握樹(shù)的表示，包括樹(shù)形表示法、文氏圖表示法、凹入表示法和括號(hào)表示法等。(3)掌握二叉樹(shù)的概念，包括二叉樹(shù)、滿二叉樹(shù)和完全二叉樹(shù)的定義。(4)掌握二叉樹(shù)的性質(zhì)。(5)重點(diǎn)掌握二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，包括二叉樹(shù)順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(6)重點(diǎn)掌握二叉樹(shù)的基本運(yùn)算和各種遍歷算法的實(shí)現(xiàn)。(7)掌握線索二叉樹(shù)的概念和相關(guān)算法的實(shí)現(xiàn)。(8)掌握哈夫曼樹(shù)的定義、哈夫曼

2、樹(shù)的構(gòu)造過(guò)程和哈夫曼編碼產(chǎn)生方法。(9)掌握并查集的相關(guān)概念和算法。(10)靈活掌握運(yùn)用二叉樹(shù)這種數(shù)據(jù)結(jié)構(gòu)解決一些綜合應(yīng)用問(wèn)題。二、實(shí)驗(yàn)項(xiàng)目摘要1編寫(xiě)一程序，實(shí)現(xiàn)二叉樹(shù)的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序完成如下功能：（1） 輸出二叉樹(shù)b;（2） 輸出H結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)值；（3） 輸出二叉樹(shù)b的深度；（4） 輸出二叉樹(shù)b的寬度；（5） 輸出二叉樹(shù)b的結(jié)點(diǎn)個(gè)數(shù)；（6） 輸出二叉樹(shù)b的葉子結(jié)點(diǎn)個(gè)數(shù)。2編寫(xiě)一程序，實(shí)現(xiàn)二叉樹(shù)的先序遍歷、中序遍歷和后序遍歷的各種遞歸和非遞歸算法，以及層次遍歷的算法。三、實(shí)驗(yàn)預(yù)習(xí)內(nèi)容二叉樹(shù)存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)基本運(yùn)算（創(chuàng)建二叉樹(shù)、尋找結(jié)點(diǎn)、找孩子結(jié)點(diǎn)、求高度、輸出

3、二叉樹(shù)）三、實(shí)驗(yàn)結(jié)果與分析 7-1#include #include #define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;struct node *lchild;struct node *rchild; BTNode;void CreateBTNode(BTNode *&b,char *str)BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;ch=strj;while (ch!=0) switch(ch) case (:top+;

4、Sttop=p;k=1; break;case ):top-;break;case ,:k=2; break; default:p=(BTNode *)malloc(sizeof(BTNode);p-data=ch;p-lchild=p-rchild=NULL; if (b=NULL) b=p;else switch(k) case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;BTNode *FindNode(BTNode *b,ElemType x)BTNode *p;if (b=NULL) return NUL

5、L;else if (b-data=x) return b;elsep=FindNode(b-lchild,x);if (p!=NULL) return p;else return FindNode(b-rchild,x);BTNode *LchildNode(BTNode *p) return p-lchild;BTNode *RchildNode(BTNode *p) return p-rchild;int BTNodeDepth(BTNode *b) int lchilddep,rchilddep; if (b=NULL) return(0); else lchilddep=BTNode

6、Depth(b-lchild); rchilddep=BTNodeDepth(b-rchild);return (lchilddeprchilddep)? (lchilddep+1):(rchilddep+1); void DispBTNode(BTNode *b)if (b!=NULL)printf(%c,b-data);if (b-lchild!=NULL | b-rchild!=NULL)printf();DispBTNode(b-lchild);if (b-rchild!=NULL) printf(,);DispBTNode(b-rchild);printf();int BTWidth

7、(BTNode *b)struct int lno;BTNode *p; QuMaxSize;int front,rear;int lnum,max,i,n;front=rear=0; if (b!=NULL) rear+;Qurear.p=b;Qurear.lno=1;while (rear!=front)front+;b=Qufront.p;lnum=Qufront.lno;if (b-lchild!=NULL)rear+;Qurear.p=b-lchild;Qurear.lno=lnum+1;if (b-rchild!=NULL)rear+;Qurear.p=b-rchild;Qurea

8、r.lno=lnum+1;max=0;lnum=1;i=1;while (i=rear)n=0;while (imax) max=n;return max;elsereturn 0;int Nodes(BTNode *b)int num1,num2; if (b=NULL) return 0; else if (b-lchild=NULL & b-rchild=NULL) return 1; else num1=Nodes(b-lchild); num2=Nodes(b-rchild); return (num1+num2+1);int LeafNodes(BTNode *b)int num1

9、,num2; if (b=NULL) return 0; else if (b-lchild=NULL & b-rchild=NULL) return 1; else num1=LeafNodes(b-lchild); num2=LeafNodes(b-rchild); return (num1+num2);void main()BTNode *b,*p,*lp,*rp;CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N),C(F,G(,I); printf(輸出二叉樹(shù):);DispBTNode(b);printf(n);printf(H結(jié)點(diǎn):);p=FindNode(b,

10、H);if (p!=NULL)lp=LchildNode(p);if (lp!=NULL) printf(左孩子為%c ,lp-data);elseprintf(無(wú)左孩子 );rp=RchildNode(p);if (rp!=NULL) printf(右孩子為%c,rp-data);elseprintf(無(wú)右孩子 );printf(n);printf(二叉樹(shù)b的深度:%dn,BTNodeDepth(b);printf(二叉樹(shù)b的寬度:%dn,BTWidth(b);printf(二叉樹(shù)b的結(jié)點(diǎn)個(gè)數(shù):%dn,Nodes(b);printf(二叉樹(shù)b的葉子結(jié)點(diǎn)個(gè)數(shù):%dn,LeafNodes(b);

11、7-2#include #include #define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;struct node *lchild;struct node *rchild; BTNode;void CreateBTNode(BTNode *&b,char *str)BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;ch=strj;while (ch!=0) switch(ch) case (:top+;Sttop=p;k=1; b

12、reak;case ):top-;break;case ,:k=2; break; default:p=(BTNode *)malloc(sizeof(BTNode);p-data=ch;p-lchild=p-rchild=NULL; if (b=NULL) b=p;else switch(k) case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;void DispBTNode(BTNode *b)if (b!=NULL)printf(%c,b-data);if (b-lchild!=NULL | b-rchil

13、d!=NULL)printf();DispBTNode(b-lchild);if (b-rchild!=NULL) printf(,);DispBTNode(b-rchild);printf();void PreOrder(BTNode *b)if (b!=NULL) printf(%c ,b-data);PreOrder(b-lchild);PreOrder(b-rchild);void PreOrder1(BTNode *b)BTNode *StMaxSize,*p; int top=-1; if (b!=NULL) top+; Sttop=b; while (top-1) p=Sttop

14、; top-; printf(%c ,p-data); if (p-rchild!=NULL) top+; Sttop=p-rchild; if (p-lchild!=NULL) top+; Sttop=p-lchild;printf(n);void InOrder(BTNode *b)if (b!=NULL) InOrder(b-lchild);printf(%c ,b-data);InOrder(b-rchild);void InOrder1(BTNode *b)BTNode *StMaxSize,*p;int top=-1;if (b!=NULL)p=b;while (top-1 | p

15、!=NULL)while (p!=NULL)top+;Sttop=p;p=p-lchild;if (top-1)p=Sttop;top-;printf(%c ,p-data);p=p-rchild;printf(n);void PostOrder(BTNode *b)if (b!=NULL) PostOrder(b-lchild);PostOrder(b-rchild);printf(%c ,b-data);void PostOrder1(BTNode *b)BTNode *StMaxSize;BTNode *p;int flag,top=-1;if (b!=NULL)dowhile (b!=

16、NULL)top+;Sttop=b;b=b-lchild;p=NULL;flag=1;while (top!=-1 & flag)b=Sttop;if (b-rchild=p)printf(%c ,b-data);top-;p=b;elseb=b-rchild;flag=0; while (top!=-1);printf(n); void LevelOrder(BTNode *b) BTNode *p; BTNode *quMaxSize;int front,rear;front=rear=-1;rear+;qurear=b; while (front!=rear) front=(front+1)%MaxSize;p=qufront;printf(%c ,p-data);if (p-lchild!=NULL) rear=(rear+1)%MaxSize;qurear=p-lchild;if (p-rchild!=NULL) rear=(rear+1)%MaxSize;qurear=p-rchild; void main()BTNode *b;CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N),C(F,G(,I); printf(二叉樹(shù)b:);DispBTNode(b);printf(n);printf(先序遍歷序列:n);printf(遞歸算法:)