數(shù)據(jù)結(jié)構(gòu)上機(jī)-實(shí)驗(yàn)三-樹結(jié)構(gòu)算法設(shè)計(jì)

中國(guó)礦業(yè)大學(xué)計(jì)算機(jī)學(xué)院實(shí)驗(yàn)報(bào)告課程名稱大學(xué)計(jì)算機(jī)根底〔理工類〕實(shí)驗(yàn)名稱_實(shí)驗(yàn)三樹結(jié)構(gòu)算法設(shè)計(jì)班級(jí)姓名學(xué)號(hào)____儀器組號(hào)_______實(shí)驗(yàn)日期____實(shí)驗(yàn)報(bào)告要求：1.實(shí)驗(yàn)?zāi)康?.實(shí)驗(yàn)內(nèi)容3.實(shí)驗(yàn)步驟4.運(yùn)行結(jié)果5.流程圖6.實(shí)驗(yàn)體會(huì)1．實(shí)驗(yàn)?zāi)康?、理解樹結(jié)構(gòu)的邏輯特性；2、熟練掌握二叉樹的邏輯結(jié)構(gòu)特性及各種存儲(chǔ)方法；3、熟練掌握二插樹的各種根本操作，尤其是三種遍歷算法以及線索化算法。4、進(jìn)一步了解和掌握類的私有和公有成員函數(shù)的定義和使用以及類型的作用域。實(shí)驗(yàn)內(nèi)容基此題1、試寫出中序遍歷二叉樹的遞歸〔1.1〕和非遞歸〔1.2〕程序并調(diào)試。2、給定一棵用鏈表表示的二叉樹，其根指針為root，試寫出求二叉樹結(jié)點(diǎn)數(shù)目。加強(qiáng)題3、寫出中序線索二叉樹的中序遍歷程序并調(diào)試。提高題4、實(shí)現(xiàn)霍夫曼編、解碼〔1〕輸入一系列字符及其出現(xiàn)頻率并以此構(gòu)造霍夫曼樹進(jìn)行編碼并輸出碼表，另輸入一段文字，對(duì)其進(jìn)行霍夫曼編碼輸出；例：CASTCASTSATATATASA〔2〕在1中已構(gòu)成的霍夫曼樹的根底上，輸入一段01編碼，要求輸出其解碼的原文 實(shí)驗(yàn)步驟基此題1.1:#include<iostream.h>#include<conio.h>#include<stdlib.h>typedefstructBiTNode{ chardata; BiTNode*lchild,*rchild; }BiTNode,*BiTree;voidCreateBiTree(BiTree&T){ charch; cout<<"請(qǐng)輸入數(shù)據(jù)："<<"\t"; cin>>ch; if(ch=='#') T=NULL; else { T=(BiTNode*)malloc(sizeof(BiTNode)); T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); }}//CreateBiTreevoidInOrderTraverse(BiTree&T){ if(T!=NULL){ InOrderTraverse(T->lchild); cout<<T->data<<""; InOrderTraverse(T->rchild); }}//InOrderTraversevoidmain(){ BiTreeRoot; CreateBiTree(Root); InOrderTraverse(Root); cout<<endl;getch();}基此題1.2:#include<iostream>#include<conio.h>#include<stack>usingnamespacestd;typedefstructBiTNode{ chardata; BiTNode*lchild,*rchild; }BiTNode,*BiTree;voidCreateBiTree(BiTree&T){ charch; cout<<"請(qǐng)輸入數(shù)據(jù)："<<"\t"; cin>>ch; if(ch=='0') T=NULL; else { T=(BiTNode*)malloc(sizeof(BiTNode)); T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); }}//CreateBiTreevoidInOrderTraverse(BiTree&T){ //采用非遞歸算法輸出二叉樹中的值 stack<BiTNode*>s; BiTreep=T; while(p||!s.empty()){ if(p) { s.push(p); p=p->lchild; } else { p=s.top(); cout<<p->data<<""; s.pop(); p=p->rchild; }//else }//while}//InOrderTraversevoidmain(){ BiTreeRoot; cout<<"'0'作為空樹"<<endl; Root=(BiTNode*)malloc(sizeof(BiTNode)); CreateBiTree(Root); cout<<"中序輸出二叉樹："<<endl; InOrderTraverse(Root); cout<<endl; getch();}根底題2：#include<iostream.h>#include<conio.h>#include<stdlib.h>typedefstructBiTNode{ chardata; BiTNode*lchild,*rchild; }BiTNode,*BiTree;intn=0;voidCreateBiTree(BiTree&T){ charch; cout<<"請(qǐng)輸入數(shù)據(jù)："<<"\t"; cin>>ch; if(ch=='0') T=NULL; else { T=(BiTNode*)malloc(sizeof(BiTNode)); T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); }}//CreateBiTreevoidsum(BiTree&T){ //求出二叉樹的結(jié)點(diǎn)的數(shù)目 if(T){ n++; sum(T->lchild); sum(T->rchild); }}//sumvoidmain(){ cout<<"'0'作為空樹"<<endl; cout<<"請(qǐng)輸入此二叉樹。"<<endl; BiTreeroot; root=(BiTNode*)malloc(sizeof(BiTNode)); CreateBiTree(root); sum(root); cout<<endl; cout<<"此二叉樹的結(jié)點(diǎn)數(shù)為"<<n<<"個(gè)"<<endl;getch();}運(yùn)行結(jié)果基此題1:輸入的樹為：結(jié)果為：基此題1.2:基此題2: