数据结构 二维码文件第3章主要算法的C++代码VIP

第3章主要算法的C++代码二叉树基本操作的算法实现#include"stdio.h"#include"iostream.h"typedefstructBTreeNode{ intdata; BTreeNode*lChild,*rChild;}Bnode,*ptr;classBTree{public: voidsetRoot(ptrr){root=r;}ptrgetRoot(){returnroot;} ptrcreateBTree();//二叉树的创建，用扩充的先序序列 ptrbuildtree(inta[],intb[],inti,intj,ints,intt); //用先序和中序序列构建二叉树 voidpreOrder();//前序遍历(递归) voidinOrder();//中序遍历(递归) voidpostOrder();//后序遍历(递归)intBTreeSize();//求结点个数 intBTreeLeaves();//求叶子结点个数 intBTreeHeight();//求树高protected: voidinOrder(ptr);//中序遍历 voidpreOrder(ptr);//前序遍历 voidpostOrder(ptr);//后序遍历 intBTreeSize(ptr);//结点个数 intBTreeLeaves(ptr);//叶子结点 intBTreeHeight(ptr);//树高 private: ptrroot;};ptrBTree::createBTree(){//用扩充的先序序列构建二叉树 ptrp; intx; scanf("%d",&x); if(x==0)returnNULL; p=newBnode; p->data=x; p->lChild=createBTree(); p->rChild=createBTree(); returnp;}//用先序和中序序列构建二叉树ptrBTree::buildtree(inta[],intb[],inti,intj,ints,intt){intk; ptrp; if(i>j)returnNULL;//序列空，返回空指针p=newBnode;//申请结点p->data=a[i];//造根结点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;//返回根结点指针}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){//求二叉树结点个数的函数 //二叉树的结点个数为左右子树的高度之和再+1 if(r==0)return0; else return1+BTreeSize(r->lChild)+BTreeSize(r->rChild);}intBTree::BTreeLeaves(){//重载形式 returnBTreeLeaves(root);}intBTree::BTreeLeaves(ptrr){//求二叉树叶子结点个数的函数 //当为空时，返回0；当找到叶子时返回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){//求二叉树高度的函数 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<<"=====二叉树构造====="<<endl; cout<<"1用先序序列和中序序列构造二叉树"<<endl; cout<<"2用扩充先序序列构造二叉树"<<endl; cout<<"其他退出"<<endl; cout<<"===================="<<endl; cout<<"请输入构造方式:"; 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<<"程序结束！"<<endl; return; } cout<<"二叉树构造完成"<<endl; cout<<"先序遍历："; bt.preOrder(); cout<<"中序遍历："; bt.inOrder(); cout<<"后序遍历："; bt.postOrder(); cout<<"二叉树的高度："<<bt.BTreeHeight()<<endl; cout<<"二叉树的叶子结点数："<< bt.BTreeLeaves()<<endl; cout<<"二叉树的结点数："<<bt.BTreeSize()<<endl; }}【运行结果】二叉树基本操作C++描述二叉排序树基本操作的算法实现#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结束：";scanf("%d",&x);//读入元素序列while(x!=0){//ZERO是输入结束标记insert(x,r);//插入xscanf("%d",&x);//读入下一个元素}root=r;//构造完毕，返回根结点指针}voidTBtree::search(){ cout<<"\n请输入要查找的元素:"; intx; cin>>x;//输入x ptrp=search(x,root);//调用查找函数查找x if(p)cout<<"查找成功！"; elsecout<<"查找失败"; cout<<endl;}//函数重载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);//调用插入函数插入x cout<<"插入成功！"; cout<<endl;}voidTBtree::insert(element_typex,ptr&p){//函数重载if(p==NULL){//遇到空树p=newBnode;//申请新结点p->data=x;//置新结点的值域p->Lson=p->Rson=NULL;//新结点作叶子return;//插入完毕，返回}//否则，尚未找到插入点，继续查找if(x<=p->data)insert(x,p->Lson);//递归的向左elseinsert(x,p->Rson);//递归的向右}voidTBtree::deleteT(){//增加虚拟根指针q，其值域为无穷小即-1 ptrq=newBnode; q->data=-1;//设置q的值域为-1 q->Lson=NULL; q->Rson=root;//设置q为检索树的虚拟根，即原检索树的根root为其右儿子 cout<<"\n请输入要删除的元素:"; intx; cin>>x; intp=deleteT(x,q);//调用删除函数删除x if(p)cout<<"删除成功！"; elsecout<<"删除失败"; cout<<endl;}//函数重载intTBtree::deleteT(element_typex,ptrrt){ptrf,p,q,s,r;p=NULL;//p将指向要删除结点f=rt;//f的初值指向虚根q=rt->Rson;//q搜索指针while(q!=NULL)//循环查找xif(x==q->data){p=q;q=NULL;}//找到xelse//没找到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的中序前驱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<<"=====构造检索树====="<<endl;bt.creat();cout<<"\n检索树操作构造完成！"<<endl;intc=1;inti=0;//构造菜单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<<"程序结束！"<<endl; c=0; } }return0;}【运行结果】二叉排序树基本操作C++描述哈夫曼树的应用算法实现#include<iostream>#include<string>usingnamespacestd;//哈夫曼树结构typedefstructHFnode{ intdata; //字母权值 stringleter; //对应字母 HFnode*Lson,*Rson; //左右子树 HFnode*next,*father; //深林域与父亲域}*HFptr;//哈夫曼所有节点的字符集合//用于后面的译码typedefstructHFaggregate{ stringleter; //哈夫曼节点的字母值 HFnode*point;//指向对应哈夫曼节点}*HFag;//哈夫曼深林转为哈夫曼树的函数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;}//创建哈夫曼深林的函数//root哈夫曼的根set后面译码需要用到的字符集合size数据的个数voidcreateHFT(HFptr&root,HFag&set,intsize){ intnum=0; stringstr; HFptrp=NULL; //动态创建哈夫曼树与字母集合 p=root=newHFnode(); set=newHFaggregate[size]; //根的权重最大0x7f7f为16进制的大数 root->data=0x7f7f; cout<<"请输入相应字符与权重(权重从小到大输入)："<<endl; //权重从小到大输入，若乱序，则需要进行排序后构造哈夫曼树 for(inti=0;i<size;i++){ p->next=newHFnode(); p=p->next; p->Lson=p->Rson=p->father=NULL; cin>>str>>num; //分别将str字母与对应的权重num赋值给哈夫曼树节点p与字母集合set中 //set[i]是set的一个元素set是集合 p->leter=set[i].leter=str; p->data=num; //set同时还存储对应字母的哈夫曼树节点指针 set[i].point=p; } p->next=root; //调用mergeHFT函数将哈夫曼深林合并成一棵树 //size-1例如5个节点合并次数4次就行了故合并次数=节点-1 mergeHFT(root,size-1);}//哈夫曼树译码voiddecoding(HFptrroot){ stringstr,x; HFptrp=root; cin>>str; //对输入译码的字符串str逐个去译码 for(inti=0;i<=str.size();i++){ x=str[i]; //判断当前字符x是左子树还是右子树 if(x=="0"){ //当前节点为叶子则打印 if(p->Lson==NULL){ cout<<p->leter; //记得p要重新指向root下次查找还需要进行 p=root; } //否则就找当前节点的左子树 p=p-