數(shù)據(jù)結(jié)構(gòu) 樹(shù)和二叉樹(shù)代碼

《數(shù)據(jù)結(jié)構(gòu) 樹(shù)和二叉樹(shù)代碼》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、樹(shù)和二叉樹(shù)一、實(shí)驗(yàn)?zāi)康模簠⒄战o定的二叉樹(shù)類的程序樣例，驗(yàn)證給出的有關(guān)二叉樹(shù)的常見(jiàn)算法，并實(shí)現(xiàn)有關(guān)的操作。二、實(shí)驗(yàn)要求：1、掌握二叉樹(shù)、哈夫曼樹(shù)和樹(shù)的特點(diǎn)。掌握它們的常見(jiàn)算法。2、提交實(shí)驗(yàn)報(bào)告，報(bào)告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說(shuō)明、程序清單、調(diào)試情況、設(shè)計(jì)技巧、心得體會(huì)。三、實(shí)驗(yàn)內(nèi)容：1．設(shè)計(jì)實(shí)現(xiàn)二叉樹(shù)類，要求：（1）編寫一個(gè)程序，首先建立不帶頭結(jié)點(diǎn)的二叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的二叉樹(shù)，然后分別輸出按照前序遍歷二叉樹(shù)、中序遍歷二叉樹(shù)和后序遍歷二叉樹(shù)訪問(wèn)各結(jié)點(diǎn)的序列信息，最后再測(cè)試查找函數(shù)和撤銷函數(shù)的正確性。（

2、2）實(shí)現(xiàn)二叉樹(shù)層次遍歷的非遞歸算法。（3）假設(shè)二叉樹(shù)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)，編寫一個(gè)算法，輸出一個(gè)二叉樹(shù)的所有葉子結(jié)點(diǎn)，并統(tǒng)計(jì)葉子結(jié)點(diǎn)個(gè)數(shù)。（4）編寫求二叉樹(shù)高度的函數(shù)（5）編寫一主函數(shù)來(lái)驗(yàn)證算法實(shí)現(xiàn)。2.設(shè)計(jì)實(shí)現(xiàn)二叉線索鏈表類，要求：（1）編寫一個(gè)程序，首先建立中序線索鏈表的二叉樹(shù)，然后實(shí)現(xiàn)中序線索鏈表的遍歷算法。（2）編寫一主函數(shù)來(lái)驗(yàn)證算法實(shí)現(xiàn)。*3.編寫創(chuàng)建哈夫曼樹(shù)和生成哈夫曼編碼的算法。*4．假設(shè)二叉樹(shù)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)，試設(shè)計(jì)一個(gè)算法，輸出從每個(gè)葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。*5．假設(shè)二叉樹(shù)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

3、進(jìn)行存儲(chǔ)，試設(shè)計(jì)一個(gè)算法，求二叉樹(shù)的寬度（即具有結(jié)點(diǎn)數(shù)最多的層次上結(jié)點(diǎn)總數(shù)）四、程序樣例#include#includeusingnamespacestd;templatestructBiNode{Tdata;BiNode*lchild,*rchild;};intmax(inta,intb){returna>b?a:b;}templateclassBiTree{public:BiTree();//構(gòu)造函數(shù)，初始化一棵空的二叉樹(shù)~BiTree()//

4、二叉樹(shù)的析構(gòu)函數(shù)算法BiTree{Release(root);}voidInOrder(){InOrder(root);}//中序遍歷二叉樹(shù)voidPreOrder(){PreOrder(root);}voidPostOrder(){PostOrder(root);}//后序遍歷二叉樹(shù)voidLeverOrder(){LeverOrder(root);}//層序遍歷二叉樹(shù)voidCount(){Count(root);}voidPreOrdercnt(){PreOrdercnt(root);}intDepth(){in

5、twww=Depth(root);returnwww;}private:BiNode*root;//指向根結(jié)點(diǎn)的頭指針voidCreat(BiNode*&root);voidPreOrder(BiNode*root);//前序遍歷二叉樹(shù)voidInOrder(BiNode*root);voidPostOrder(BiNode*root);voidLeverOrder(BiNode*root);//層序遍歷二叉樹(shù)voidRelease(BiNode*root);//析構(gòu)函數(shù)調(diào)用v

6、oidCount(BiNode*root);/////求二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)voidPreOrdercnt(BiNode*root);///設(shè)計(jì)算法按前序次序打印二叉樹(shù)中的葉子結(jié)點(diǎn);intDepth(BiNode*root);//深度；};templateBiTree::BiTree(){Creat(root);}templatevoidBiTree::Creat(BiNode*&root){charch;cin>>ch;if(ch=='#')root=N

7、ULL;//建立一棵空樹(shù)else{root=newBiNode;//生成一個(gè)結(jié)點(diǎn)root->data=ch;Creat(root->lchild);//遞歸建立左子樹(shù)Creat(root->rchild);//遞歸建立右子樹(shù)}}templatevoidBiTree::LeverOrder(BiNode*root){BiNode*Q[100];intfront=0,rear=0;//采用順序隊(duì)列，并假定不會(huì)發(fā)生上溢if(root==NULL)return;Q[++rear]=roo

8、t;while(front!=rear){BiNode*q=Q[++front];cout<data<<"";if(q->lchild!=NULL)Q[++rear]=q->lchild;if(q->rchild!=NULL)Q[++rear]=q->rchild;}}templatevoidBiTr