數(shù)據(jù)結(jié)構(gòu) 二維碼文件第3章主要算法的C++代碼

第3章主要算法的C++代碼二叉樹基本操作的算法實現(xiàn)#include"stdio.h"#include"iostream.h"typedefstructBTreeNode{ intdata; BTreeNode*lChild,*rChild;}Bnode,*ptr;classBTree{public: voidsetRoot(ptrr){root=r;}ptrgetRoot(){returnroot;} ptrcreateBTree();//二叉樹的創(chuàng)建，用擴充的先序序列 ptrbuildtree(inta[],intb[],inti,intj,ints,intt); //用先序和中序序列構(gòu)建二叉樹 voidpreOrder();//前序遍歷(遞歸) voidinOrder();//中序遍歷(遞歸) voidpostOrder();//后序遍歷(遞歸)intBTreeSize();//求結(jié)點個數(shù) intBTreeLeaves();//求葉子結(jié)點個數(shù) intBTreeHeight();//求樹高protected: voidinOrder(ptr);//中序遍歷 voidpreOrder(ptr);//前序遍歷 voidpostOrder(ptr);//后序遍歷 intBTreeSize(ptr);//結(jié)點個數(shù) intBTreeLeaves(ptr);//葉子結(jié)點 intBTreeHeight(ptr);//樹高 private: ptrroot;};ptrBTree::createBTree(){//用擴充的先序序列構(gòu)建二叉樹 ptrp; intx; scanf("%d",&x); if(x==0)returnNULL; p=newBnode; p->data=x; p->lChild=createBTree(); p->rChild=createBTree(); returnp;}//用先序和中序序列構(gòu)建二叉樹ptrBTree::buildtree(inta[],intb[],inti,intj,ints,intt){intk; ptrp; if(i>j)returnNULL;//序列空，返回空指針p=newBnode;//申請結(jié)點p->data=a[i];//造根結(jié)點k=s;while((k<=t)&&(b[k]!=a[i]))k++;//找根if(b[k]!=a[i]){ cout<<"Error"<<endl; returnNULL;//沒找到，出錯}p->lChild=buildtree(a,b,i+1,i+k-s,s,k-1);p->rChild=buildtree(a,b,i+k-s+1,j,k+1,t);returnp;//返回根結(jié)點指針}voidBTree::preOrder(){//重載形式 preOrder(root); cout<<endl;}voidBTree::preOrder(ptrr){//前序遞歸訪問二叉樹(遞歸) if(r!=0){//是if，而不是while cout<<r->data<<""; preOrder(r->lChild);//遞歸訪問 preOrder(r->rChild);//遞歸訪問 }}voidBTree::inOrder(){//利用重載的方法 inOrder(root); cout<<endl;}voidBTree::inOrder(ptrr){//中序訪問二叉樹(遞歸) if(r!=0){//是if，而不是while inOrder(r->lChild);//遞歸訪問 cout<<r->data<<""; inOrder(r->rChild);//遞歸訪問 }}voidBTree::postOrder(){//重載形式 postOrder(root); cout<<endl;}voidBTree::postOrder(ptrr){//后序遍歷(遞歸) if(r!=0){//是if，而不是while postOrder(r->lChild);//遞歸訪問 postOrder(r->rChild);//遞歸訪問 cout<<r->data<<""; }}intBTree::BTreeSize(){//重載形式 returnBTreeSize(root);}intBTree::BTreeSize(ptrr){//求二叉樹結(jié)點個數(shù)的函數(shù) //二叉樹的結(jié)點個數(shù)為左右子樹的高度之和再+1 if(r==0)return0; else return1+BTreeSize(r->lChild)+BTreeSize(r->rChild);}intBTree::BTreeLeaves(){//重載形式 returnBTreeLeaves(root);}intBTree::BTreeLeaves(ptrr){//求二叉樹葉子結(jié)點個數(shù)的函數(shù) //當(dāng)為空時，返回0；當(dāng)找到葉子時返回1 if(r==0)return0; else if(r->lChild==0&&r->rChild==0) return1; else returnBTreeLeaves(r->lChild)+BTreeLeaves(r->rChild);}intBTree::BTreeHeight(){//重載形式 returnBTreeHeight(root);}intBTree::BTreeHeight(ptrr){//求二叉樹高度的函數(shù) if(r==0)return0; else { //二叉樹的高度為左右子樹的最大者+1 intlHei=BTreeHeight(r->lChild); intrHei=BTreeHeight(r->rChild); return(lHei>rHei)?lHei+1:rHei+1; }}voidmain(){ BTreebt; inti,j; intc=1; inta[N]; intb[N]; while(c){ cout<<"=====二叉樹構(gòu)造====="<<endl; cout<<"1用先序序列和中序序列構(gòu)造二叉樹"<<endl; cout<<"2用擴充先序序列構(gòu)造二叉樹"<<endl; cout<<"其他退出"<<endl; cout<<"===================="<<endl; cout<<"請輸入構(gòu)造方式:"; cin>>i; switch(i){ case1: cout<<"請輸入先序序列："<<endl; for(j=0;j<N;j++) cin>>a[j]; cout<<"請輸入中序序列："<<endl; for(j=0;j<N;j++) cin>>b[j]; bt.setRoot(bt.buildtree(a,b,0,N-1,0,N-1)); break; case2: cout<<"請輸入擴充的先序序列："<<endl; bt.setRoot(bt.createBTree()); break; default: cout<<"程序結(jié)束！"<<endl; return; } cout<<"二叉樹構(gòu)造完成"<<endl; cout<<"先序遍歷："; bt.preOrder(); cout<<"中序遍歷："; bt.inOrder(); cout<<"后序遍歷："; bt.postOrder(); cout<<"二叉樹的高度："<<bt.BTreeHeight()<<endl; cout<<"二叉樹的葉子結(jié)點數(shù)："<< bt.BTreeLeaves()<<endl; cout<<"二叉樹的結(jié)點數(shù)："<<bt.BTreeSize()<<endl; }}【運行結(jié)果】二叉樹基本操作C++描述二叉排序樹基本操作的算法實現(xiàn)#include"stdio.h"#include"iostream.h"#defineSUCC1#defineNOTFOUND0typedefintelement_type;typedefstructBTreeNode{ element_typedata; BTreeNode*Lson,*Rson;}Bnode,*ptr;classTBtree{private: ptrroot;public:voidcreat(); voidsearch(); voidinsert(); voiddeleteT(); voidpreOrder();//前序遍歷(遞歸) voidinOrder();//中序遍歷(遞歸) voidpostOrder();//后序遍歷(遞歸)protected:ptrsearch(element_typex,ptrp);voidinsert(element_typex,ptr&p);intdeleteT(element_typex,ptrp);voidinOrder(ptr);//中序遍歷 voidpreOrder(ptr);//前序遍歷 voidpostOrder(ptr);//后序遍歷 };voidTBtree::creat(){ptrr;element_typex;r=NULL;//開始時樹為空cout<<"請輸入一系列元素，以0結(jié)束：";scanf("%d",&x);//讀入元素序列while(x!=0){//ZERO是輸入結(jié)束標(biāo)記insert(x,r);//插入xscanf("%d",&x);//讀入下一個元素}root=r;//構(gòu)造完畢，返回根結(jié)點指針}voidTBtree::search(){ cout<<"\n請輸入要查找的元素:"; intx; cin>>x;//輸入x ptrp=search(x,root);//調(diào)用查找函數(shù)查找x if(p)cout<<"查找成功！"; elsecout<<"查找失敗"; cout<<endl;}//函數(shù)重載ptrTBtree::search(element_typex,ptrp){if(p==NULL)returnNULL;//遇到空樹if(x==p->data)returnp;//找到xif(x<p->data)returnsearch(x,p->Lson);//遞歸向左elsereturnsearch(x,p->Rson);//遞歸向右}voidTBtree::insert(){ cout<<"\n請輸入要插入的元素:"; intx; cin>>x;//輸入x insert(x,root);//調(diào)用插入函數(shù)插入x cout<<"插入成功！"; cout<<endl;}voidTBtree::insert(element_typex,ptr&p){//函數(shù)重載if(p==NULL){//遇到空樹p=newBnode;//申請新結(jié)點p->data=x;//置新結(jié)點的值域p->Lson=p->Rson=NULL;//新結(jié)點作葉子return;//插入完畢，返回}//否則，尚未找到插入點，繼續(xù)查找if(x<=p->data)insert(x,p->Lson);//遞歸的向左elseinsert(x,p->Rson);//遞歸的向右}voidTBtree::deleteT(){//增加虛擬根指針q，其值域為無窮小即-1 ptrq=newBnode; q->data=-1;//設(shè)置q的值域為-1 q->Lson=NULL; q->Rson=root;//設(shè)置q為檢索樹的虛擬根，即原檢索樹的根root為其右兒子 cout<<"\n請輸入要刪除的元素:"; intx; cin>>x; intp=deleteT(x,q);//調(diào)用刪除函數(shù)刪除x if(p)cout<<"刪除成功！"; elsecout<<"刪除失敗"; cout<<endl;}//函數(shù)重載intTBtree::deleteT(element_typex,ptrrt){ptrf,p,q,s,r;p=NULL;//p將指向要刪除結(jié)點f=rt;//f的初值指向虛根q=rt->Rson;//q搜索指針while(q!=NULL)//循環(huán)查找xif(x==q->data){p=q;q=NULL;}//找到xelse//沒找到x后，繼續(xù)搜索if(x<q->data){f=q;q=q->Lson;}//向左搜索else{f=q;q=q->Rson;}//向右搜索if(p==NULL)returnNOTFOUND;//沒找到xif(p->Rson==NULL)//p無右兒子，用左兒子代替pif(p==f->Lson){f->Lson=p->Lson;deletep;}else{f->Rson=p->Lson;deletep;}elseif(p->Lson==NULL)//p無左兒子，用右兒子代替pif(p==f->Lson){f->Lson=p->Rson;deletep;}else{f->Rson=p->Rson;deletep;}else{//以下是p有兩個兒子情況的處理//p有兩個兒子，找p的中序前驅(qū)s=p->Lson;//s是p的左兒子if(s->Rson==NULL){//s沒有右兒子，用s代替pp->data=s->data;//用s的值域代換p的值域p->Lson=s->Lson;//刪去sdeletes;}else{//以下是s有右兒子的情況//s有右兒子，找p的左兒子的最右子孫rr=s->Rson;while(r->Rson!=NULL){s=r;r=r->Rson;}p->data=r->data;//用r的值域代換p的值域s->Rson=r->Lson;//刪去rdeleter;}}returnSUCC;//返回刪除成功信息}//重載形式voidTBtree::preOrder(){ cout<<"先序遍歷："; preOrder(root); cout<<endl;}//前序遞歸訪問二叉樹(遞歸)voidTBtree::preOrder(ptrr){ if(r!=0){//是if，而不是while cout<<r->data<<""; if(r->Lson!=0)preOrder(r->Lson);//遞歸訪問 if(r->Rson!=0)preOrder(r->Rson);//遞歸訪問 }}//利用重載的方法voidTBtree::inOrder(){ cout<<"中序遍歷："; inOrder(root); cout<<endl;}//中序訪問二叉樹(遞歸)voidTBtree::inOrder(ptrr){ if(r!=0){//是if，而不是while if(r->Lson!=0)inOrder(r->Lson);//遞歸訪問 cout<<r->data<<""; if(r->Rson!=0)inOrder(r->Rson);//遞歸訪問 }}//重載形式voidTBtree::postOrder(){ cout<<"后序遍歷："; postOrder(root); cout<<endl;}//后序遍歷(遞歸)voidTBtree::postOrder(ptrr){ if(r!=0){//是if，而不是while if(r->Lson!=0)postOrder(r->Lson);//遞歸訪問 if(r->Rson!=0)postOrder(r->Rson);//遞歸訪問 cout<<r->data<<""; }}intmain(){TBtreebt;cout<<"=====構(gòu)造檢索樹====="<<endl;bt.creat();cout<<"\n檢索樹操作構(gòu)造完成！"<<endl;intc=1;inti=0;//構(gòu)造菜單cout<<"\n=====檢索樹操作====="<<endl; cout<<"1先序遍歷"<<endl; cout<<"2中序遍歷"<<endl; cout<<"3后序遍歷"<<endl; cout<<"4查找"<<endl; cout<<"5插入"<<endl; cout<<"6刪除"<<endl; cout<<"其他退出"<<endl; cout<<"===================="<<endl;while(c){ cout<<"請選擇操作代碼:"; cin>>i; switch(i){ //選擇菜單 case1: bt.preOrder(); break; case2: bt.inOrder(); break; case3: bt.postOrder(); break; case4: bt.search(); break; case5: bt.insert(); break; case6: bt.deleteT(); break; default: cout<<"程序結(jié)束！"<<endl; c=0; } }return0;}【運行結(jié)果】二叉排序樹基本操作C++描述哈夫曼樹的應(yīng)用算法實現(xiàn)#include<iostream>#include<string>usingnamespacestd;//哈夫曼樹結(jié)構(gòu)typedefstructHFnode{ intdata; //字母權(quán)值 stringleter; //對應(yīng)字母 HFnode*Lson,*Rson; //左右子樹 HFnode*next,*father; //深林域與父親域}*HFptr;//哈夫曼所有節(jié)點的字符集合//用于后面的譯碼typedefstructHFaggregate{ stringleter; //哈夫曼節(jié)點的字母值 HFnode*point;//指向?qū)?yīng)哈夫曼節(jié)點}*HFag;//哈夫曼深林轉(zhuǎn)為哈夫曼樹的函數(shù)voidmergeHFT(HFptr&root,intsize){ //n棵哈夫曼子樹合并為一棵哈夫曼樹 HFptrt1,t2,p,q,r; for(inti=0;i<size;i++){ r=newHFnode(); t1=root->next; t2=t1->next; t1->father=t2->father=r; r->data=t1->data+t2->data; r->Lson=t1; r->Rson=t2; r->leter="0"; root->next=t2->next; p=root; q=root->next; //將新生點r有序插入深林域 while(1){ if(q->data<r->data){ p=q; q=q->next; } else{ r->next=q; p->next=r; break; } } } //刪除虛擬根 p=root; root=root->next; deletep;}//創(chuàng)建哈夫曼深林的函數(shù)//root哈夫曼的根set后面譯碼需要用到的字符集合size數(shù)據(jù)的個數(shù)voidcreateHFT(HFptr&root,HFag&set,intsize){ intnum=0; stringstr; HFptrp=NULL; //動態(tài)創(chuàng)建哈夫曼樹與字母集合 p=root=newHFnode(); set=newHFaggregate[size]; //根的權(quán)重最大0x7f7f為16進制的大數(shù) root->data=0x7f7f; cout<<"請輸入相應(yīng)字符與權(quán)重(權(quán)重從小到大輸入)："<<endl; //權(quán)重從小到大輸入，若亂序，則需要進行排序后構(gòu)造哈夫曼樹 for(inti=0;i<size;i++){ p->next=newHFnode(); p=p->next; p->Lson=p->Rson=p->father=NULL; cin>>str>>num; //分別將str字母與對應(yīng)的權(quán)重num賦值給哈夫曼樹節(jié)點p與字母集合set中 //set[i]是set的一個元素set是集合 p->leter=set[i].leter=str; p->data=num; //set同時還存儲對應(yīng)字母的哈夫曼樹節(jié)點指針 set[i].point=p; } p->next=root; //調(diào)用mergeHFT函數(shù)將哈夫曼深林合并成一棵樹 //size-1例如5個節(jié)點合并次數(shù)4次就行了故合并次數(shù)=節(jié)點-1 mergeHFT(root,size-1);}//哈夫曼樹譯碼voiddecoding(HFptrroot){ stringstr,x; HFptrp=root; cin>>str; //對輸入譯碼的字符串str逐個去譯碼 for(inti=0;i<=str.size();i++){ x=str[i]; //判斷當(dāng)前字符x是左子樹還是右子樹 if(x=="0"){ //當(dāng)前節(jié)點為葉子則打印 if(p->Lson==NULL){ cout<<p->leter; //記得p要重新指向root下次查找還需要進行 p=root; } //否則就找當(dāng)前節(jié)點的左子樹 p=p-