1、實(shí)驗(yàn)六 二叉樹構(gòu)造和遍歷一. 實(shí)驗(yàn)?zāi)康?掌握二叉樹的邏輯結(jié)構(gòu)； 掌握二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)； 掌握基于二叉鏈表存儲(chǔ)的二叉樹的遍歷操作的實(shí)現(xiàn)。二. 實(shí)驗(yàn)環(huán)境Windows操作系統(tǒng)，Visual C+ 6.0編程環(huán)境。三. 實(shí)驗(yàn)內(nèi)容和步驟1觀察下面圖6-1的二叉樹，回答問題。圖6-1（1） 寫出前序、中序和后序遍歷序列；前序：ABDECFG 中序：DBEAFGC 后序：DEBGFCA（2） 分別寫單支結(jié)點(diǎn)和葉子結(jié)點(diǎn)；單支結(jié)點(diǎn)：CF 葉子結(jié)點(diǎn)：DEG（3） 以”#”補(bǔ)充所有結(jié)點(diǎn)的空分支；ABD#E#CF#G#（4）寫出補(bǔ)充空分支后二叉樹的前序遍歷序列（擴(kuò)展的前序遍歷序列）； ABD#E#CF#G#

2、2建立工程Bitree，編寫B(tài)iree.h，Biree.cpp和測(cè)試函數(shù)Bireemain.cpp,完成下列功能。 建立一棵含有n個(gè)結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲(chǔ)； 前序（或中序、后序）遍歷該二叉樹。四編碼 頭文件Bitree.h#includeusing namespace std;template struct BiNodeT data; BiNode *lchild, *rchild;template class BiTreepublic:BiTree()root=Creat(root); /有參構(gòu)造函數(shù)，初始化一棵二叉樹，其前序序列由鍵盤輸入 BiTree()Release(root)

3、; /析構(gòu)函數(shù)，釋放二叉鏈表中各結(jié)點(diǎn)的存儲(chǔ)空間 void PreOrder()PreOrder(root); /前序遍歷二叉樹 void InOrder()InOrder(root); /中序遍歷二叉樹 void PostOrder()PostOrder(root); /后序遍歷二叉樹private: BiNode *root; /指向根結(jié)點(diǎn)的頭指針 BiNode *Creat(BiNode *bt); /有參構(gòu)造函數(shù)調(diào)用 void Release(BiNode *bt); /析構(gòu)函數(shù)調(diào)用 void PreOrder(BiNode *bt); void InOrder(BiNode *bt);

4、 void PostOrder(BiNode *bt);template BiNode *BiTree:Creat(BiNode *bt)T ch; cinch; if(ch=#)bt=NULL; /建立一棵空樹 else bt=new BiNode; /生成一個(gè)結(jié)點(diǎn) bt-data=ch; bt-lchild=Creat(bt-lchild); /遞歸建立左子樹 bt-rchild=Creat(bt-rchild); /遞歸建立右子樹return bt;template void BiTree:Release(BiNode *bt)if(bt!=NULL)Release(bt-lchild)

5、;Release(bt-rchild);delete bt;template void BiTree:PreOrder(BiNode *bt) if (bt=NULL) return; /遞歸調(diào)用的結(jié)束條件 else coutdata; /訪問根結(jié)點(diǎn)的數(shù)據(jù)域 PreOrder(bt-lchild); /前序遞歸遍歷root的左子樹 PreOrder(bt-rchild); /前序遞歸遍歷root的右子樹 template void BiTree:InOrder(BiNode *bt) if (bt=NULL) return; /遞歸調(diào)用的結(jié)束條件 else InOrder(bt-lchild)

6、;coutdata; InOrder(bt-rchild); template void BiTree:PostOrder(BiNode *bt) if (bt=NULL) return; /遞歸調(diào)用的結(jié)束條件 else PostOrder(bt-lchild); PostOrder(bt-rchild);coutdata; 主函數(shù)main#includeBitree.hvoid main()int c=1;while(c)cout輸入前序序列:;BiTree tree;cout前序遍歷:;tree.PreOrder();coutendl; cout中序遍歷:;tree.InOrder();c

7、outendl;cout后序遍歷:;tree.PostOrder();coutendl;cout0.結(jié)束 1.重試endl;coutc;五.調(diào)試結(jié)果（表5-1） （表5-1）二叉樹驗(yàn)證實(shí)驗(yàn)調(diào)試結(jié)果六實(shí)驗(yàn)小結(jié)本次實(shí)驗(yàn)主要是通過實(shí)驗(yàn)過程掌握二叉樹的邏輯結(jié)構(gòu)，掌握二叉樹的二叉鏈表存儲(chǔ)結(jié)構(gòu)和掌握基于二叉鏈表存儲(chǔ)的二叉樹的遍歷操作的實(shí)現(xiàn)。哈夫曼編碼代碼#includeusing namespace std;const int Size=10,Size1=50; struct elementint weight;int lchild,rchild,parent;int getW(char T,int *w

8、,char *s)char c;int count,k=0;for(int i=0;Ti!=0;i+)count=0;if(Ti=a&T1hi4.weight) c=i3;i3=i4;i4=c;for(i;hi.weight0;i+)if(hi.parent=-1)if(hi.weighthi3.weight)i4=i3,i3=i;else if(hi.weighthi4.weight)i4=i;void HuffmanTree(element *huffTree,int w,int n)int i1,i2;for(int i=0;i2*n-1;i+)huffTreei.parent=-1;

9、huffTreei.lchild=-1; huffTreei.rchild=-1;for(i=0;in;i+)huffTreei.weight=wi;for(int k=n;k2*n-1;k+)Select(huffTree,i1,i2);huffTreei1.parent=k;huffTreei2.parent=k; huffTreek.weight=huffTreei1.weight+huffTreei2.weight; huffTreek.lchild=i1; huffTreek.rchild=i2;void bm(element h,int m)char bSize;b0=0; int

10、 sSize,cd;int top=-1,i=0,k;while(m!=-1|top!=-1)while(m!=-1)if(hm.lchild=-1 & hm.rchild=-1)/記錄路徑編碼0，1的算法，用到parent回溯。cd=0;for(int j=hm.parent;j!=-1;j=hj.parent)cd+;bcd=0;k=m;for(j=hk.parent;j!=-1;j=hj.parent)if(hj.lchild=k) b-cd=0;else b-cd=1;k=j;couthm.weight:bendl;s+top=m;m=hm.lchild;if(top!=-1)m=stop-;m=hm.rchild;void main()char TSize1,sSiz