还剩14页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
第章主要算法的代码3C++二叉树基本操作的算法实现#include nstdio.hn#include niostream.htypedef structBTreeNode{int data;BTreeNode*lChild,*rChild;}Bnode,*ptr;class BTree{public:void setRootptr r{root=r;}ptr getRoot{return root;}〃二义树的创建,用扩充的先序序列ptr createBTree;//用先序和中序序列构建二叉树ptr buildtreeint a[],int b[],int i,int j,int s,int t;〃前序遍历递归void preOrder;〃中序遍历递归void inOrder;〃后序遍历递归void postOrder;;〃求结点个数int BTreeSize;//求叶子结点个数int BTreeLeaves;//求树高int BTreeHeightprotected:中序遍历void inOrderptr;//前序遍历void preOrderptr;//〃后序遍历void postOrderptr;〃结点个数int BTreeSizeptr;〃叶子结点int BTreeLeavesptr;树高int BTreeHeightptr;//private:ptr root;;〃用扩充的先序序列构建二叉树ptr BTree::createBTree{ptrp;int x;scanfn%dn,x;ifx==0return NULL;p=new Bnode;p-data=x;p-lChild=createBTree;p-rChild=createBTree;return p;〃用先序和中序序列构建二叉树bt.preOrder;break;bt.inOrder;break;bt.postOrder;break;bt.search;break;bt.insert;break;bt.deleteT;break;default:程序结束!coutvv””endl;c=0;return0;【运行结果】•2211443366作代码2•1122334466作代码31133664422后作代码麴翳找的元素.4查请选择操作代码4其篡簿鎏落查找的元素礴盍量作代码5鞅哈善柄人的元素口寓蠹般代码请输入要删除的元素6请选择操作代码126删作要除代二叉排序树基本操作描述C++置束入成毒序请揩程哈夫曼树的应用算法实现#includeiostream#includestring usingnamespace std;//哈夫曼树结构typedef structHFnode{int data;string leter;〃字母权值HFnode*Lson,*Rson;〃对应字母HFnode*next,*father;〃左右子树}*HFptr;〃深林域与父亲域654321!!0-5■■ZJ-.T//哈夫曼所有节点的字符集合〃用于后面的译码typedef structHFaggregate{〃哈夫曼节点的字母值string leter;〃指向对应哈夫曼节点HFnode*point;}*HFag;〃哈夫曼深林转为哈夫曼树的函数void mergeHFTHFptr root,int size{棵哈夫曼子树合并为一棵哈夫曼树//nHFptr tl,t2,p,q,r;for int i=0;isize;i++{r=new HFnode;tl=root-next;t2=tl-next;tl-father=t2-father=r;r-data=tl-data+t2-data;r-Lson=tl;r-Rson=t2;r-leter=0;root-next=t2-next;p=root;q=root-next;〃将新生点有序插入深林域rwhile1{if q-datar-data{p=q;q=q-next;else{r-next=q;p-next=r;break;//删除虚拟根p=root;root=root-next;delete p;〃创建哈夫曼深林的函数哈夫曼的根后面译码需要用到的字符集合数据的个数//root setsize void createHFTHFptr root,HFag set,int size{int num=0;string str;HFptr p=NULL;〃动态创建哈夫曼树与字母集合p=root=new HFnodeQ;set=new HFaggregate[size];〃根的权重最大为进制的大数Ox7f7f16root-data=0x7f7f;«”请输入相应字符与权重权重从小到大输入cout endl;〃权重从小到大输入,若乱序,则需要进行排序后构造哈夫曼树for int i=0;isize;i++{p-next=new HFnode;p=p-next;p-Lson=p-Rson=p-father=NULL;cin»str»num;//分别将字母与对应的权重赋值给哈夫曼树节点与字母集合中str nump set〃是的一个元素是集合set[i]set setp-leter=set[i].leter=str;p-data=num;同时还存储对应字母的哈夫曼树节点指针//setset[i].point=p;p-next=root;〃调用函数将哈夫曼深林合并成一棵树mergeHFT例如个节点合并次数次就行了故合并次数=节点//size-154-1mergeHFTroot,size-1;〃哈夫曼树译码void decodingHFptr root{string str,x;HFptr p=root;cin»str;〃对输入译码的字符串逐个去译码strfor inti=0;i=str.size;i++{x=str[i];〃判断当前字符是左子树还是右子树xifx=”0{〃当前节点为叶子则打印if p-Lson==NULL{cout«p-leter;〃记得要重新指向下次查找还需要进行p rootp=root;〃否则就找当前节点的左子树p=p-Lson;else{〃当前节点为叶子,则打印if p-Lson==NULL{cout«p-leter;p=root;〃否则就找当前节点的右子树二p p-Rson;〃编码路径string encodingPathHFptrroot,HFptr p{string x,y;HFptr q=p-father;〃由下向上记录路径while q!=root{if q-Lson!=p{x+=T;else{;x+=0;p=qq=q-father;〃判断最后一个节点是的左子树还是右子树rootif root-Lson!=p{x+=T;else{;x+=0〃路径由于是下往上,故需要反转for inti=x.size-1;i!=-1;i-{y+=x[i];return y;//哈夫曼树编码void encodingHFptrroot,HFag set,int size{string str,x;cin»str;for inti=0;istr.size;i++{x=str[i|;〃遍历字符集里面的元素找到字母所对应的哈夫曼节点指针,再把对应的路径输出//set集合最后一个元素的下标为由于之前输入是权重从大到小输入,〃故权重越size-1,set大出现的频率大的放到前面遍历,提高效率for int j=size-1;j!=-1;j-{if x==set[j].leter{cout«encodingPathroot,set[j].point;int main{HFptrroot=NULL;HFag set=NULL;int size=0;请输入字符个数”cout VV”vvendl;cin»size;createHFTroot,set,size;请输入编码的字符串coutvv”vvendl;encodingroot,set,size;«”请输入译码的字符串cout«endl endl;decodingroot;cout«endl;return0;【运行结果】情输入学符个数:10请输入相应字符与权重权重从小到大输入〉al9bl8cl6dl4el2£8g6h4i2jl请输入编码的字符串aftereatteaarea请输入译码的字符串bbhabc哈夫曼树描述C++ptr BTree::buildtreeint a[],intb[],inti,intj,int s,int t{int k;ptr p;〃序列空,返回空指针〃申请结点二〃造ifij return NULL;p=new Bnode;p-data a[i];根结点k=s;〃找根whilek=tb[k]!=a[i]k++;ifb[k]!=a[i]{cout«Error,«endl;〃没找到,出错returnNULL;p-lChild=buildtreea,b,i+1,i+k-s,s,k-1;p-rChild=buildtreea,b,i+k-s+1,j,k+1,t;返回根结点指针return p;//{〃重载形式void BTree::preOrderpreOrderroot;cout«endl;前序递归访问二叉树递归〃是而不是void BTree::preOrderptr r{//ifr!=O{if,whilecout«r-data«n n;〃递归访问〃递归访问preOrderr-lChild;preOrderr-rChiId;〃利用重载的方法void BTree::inOrder{inOrderroot;cout«endl;〃中序访问二叉树递归〃是而不是void BTree::inOrderptr r{ifr!=O{if,while递归访问inOrderr-lChild;//cout«r-data«n”;inOrderr-rChild;〃递归访问{〃重载形式void BTree::postOrderpostOrderroot;cout«endl;〃后序遍历递归〃是而不是void BTree::postOrderptr r{ifr!=O{if,whilepostOrderr-lChild;//递归访问postOrderr-〉rChild;//递归访问cout«r-data«n H;{〃重载形式int BTree::BTreeSize returnBTreeSizeroot;〃求二叉树结点个数的函数int BTree::BTreeSizeptr r{〃二叉树的结点个数为左右子树的高度之和再+1ifr==O return0;elsereturn14-BTreeSizer-lChild+BTreeSizer-rChild;{〃重载形式int BTree::BTreeLeavesreturn BTreeLeavesroot;〃求二叉树叶子结点个数的函数〃当为空时,返回;当找到叶子int BTree::BTreeLeavesptr r{0时返回1ifr==O return0;elseifr-lChild==0r-rChild==0return1;elsereturn BTreeLeavesr-lChild+BTreeLeavesr-rChild;}{〃重载形式int BTree::BTreeHeightreturn BTreeHeightroot;求二叉树高度的函数int BTree::BTreeHeightptr r{//ifr==O return0;else{〃二叉树的高度为左右子树的最大者+1int!Hei=BTreeHeightr-lChild;int rHei=BTreeHeightr-rChild;return!HeirHeilHei+l:rHei+l;void main{BTree bt;int ij;int c=l;inta[N];intb[N];whilec{二叉树构造===vvendl;cout«nl用先序序列和中序序列构造二叉树vvendl;cout«n2用扩充先序序列构造二叉树”《endl;其他退出coutvv”endl;cout«u===================-«endl\请输入构造方式:;coutvv”cin»i;switchi{case1:cout«”请输入先序序列u«endl;forj=0;jN;j++cin»a[j];coutvv”请输入中序序列:n«endl;forj=0;jN;j++cin»bfj];bt.setRootbt.buildtreea,b,0,N-1,0,N-1;break;case2:cout”请输入扩充的先序序列M«endl;bt.setRootbt.createBTree;break;default:程序结束!cout««endl;return;}二叉树构造完成coutvv”endl;先序遍历cout«”bt.preOrder;中序遍历:coutvv”bt.inOrder;后序遍历”;coutvv”bt.postOrder;coutvv”二叉树的高度:n«bt.BTreeHeight«endl;二叉树的叶子结点数n«coutvv”bt.BTreeLeaves«endl;〈”二叉树的结点数”coutv vbt.BTreeSize«endl;【运行结果】曷〈中列骁和权造树构用序琳列序叉叉列二苴二叉树基本操作描述C++二叉排序树基本操作的算法实构先方序请中序现请完构造请历历#include stdio.h序哥的二序#include niostream.hu的造先魂#define SUCC1中入入#define NOTFOUND0typedef int入后树element_type;二先typedef structBTreeNode{三扩、element_type data;权BTreeNode*Lson,*Rson;叉}Bnode,*ptr;造树构叉列二看完式class TBtree{叉度苫就、先列序造充private:造万命」成ptrroot;叉叉家与public:叉一一用上voidcreat;构历历密用闻的者露void search;八・・请请入入土口二先树WWW先和中序杈中后扩列叉造树构叉列二请方造构束居程入结21132B^:4^
14133433100465156..L:!30=:04223243=2••=i156565614156565614y4--:6,y4--000-JM4void insert;void deleteT;;//前序遍历递归void preOrder;//中序遍历递归void inOrder;//后序遍历递归void postOrderprotected:ptr searchelement_type x,ptr p;void insertelement_type x,ptr p;int deleteTelement_type x,ptr p;〃中序遍历void inOrderptr;〃前序遍历void preOrderptr;后序遍历void postOrderptr;//};void TBtree::creat{ptrr;element_type x;『〃开始时树为空NULL;请输入一系列元素,以结束:coutvv”0scanfn%dn,x;〃读入元素序列是输入结束标记whilex!=0{//ZERO〃插入insertx,r;xscanfn%d\x;〃读入下一个元素〃构造完毕,返回根结点指针root=r;void TBtree::search{cout«n\n请输入要查找的元素:;int x;〃输入cin»x;x//调用查找函数查找ptr p=searchx,root;x查找成功!”;ifp coutv”查找失败”;else coutvv”cout«endl;〃函数重载ptr TBtree::searchelement_type x,ptr p{〃遇到空树if p==NULL returnNULL;〃找至if x==p-data returnp;U xifxp-data〃递归向左return searchx,p-Lson;〃递归向右else returnsearchx,p-Rson;void TBtree::insert{cout«n\n请输入要插入的元素:;int x;〃输入cin»x;x〃调用插入函数插入insertx,root;x插入成功!”;coutvv”cout«endl;{〃函数重载void TBtree::insertelement_type x,ptr p二二〃遇到空树if pNULL{〃申请新结点p=new Bnode;〃置新结点的值域p-data=x;〃新结点作叶子p-Lson=p-Rson=NULL;〃插入完毕,返回return;}〃否则,尚未找到插入点,继续查找〃递归的向左ifx=p-data insertx,p-Lson;〃递归的向右else insertx,p-Rson;void TBtree::deleteT{〃增加虚拟根指针其值域为无穷小即-q,1ptr q=new Bnode;//设置的值域为q-data=-1;q-1q-Lson=NULL;〃设置为检索树的虚拟根,即原检索树的根为其右儿子q-Rson=root;q rootcout«n\n请输入要删除的元素:;int x;cin»x;〃调用册除函数册除int p=deleteTx,q;lj ljx删除成功!”;ifpcout”删除失败”;else coutcout«endl;〃函数重载int TBtree::deleteTelement_type x,ptr rt{ptr f,p,q,s,r;将指向要删除结点p=NULL;//p的初值指向虚根f=rt;//f搜索指针q=rt-Rson;//q〃循环查找whileq!=NULL x〃找至ifx=q-data{p=q;q=NULL;}U x没找到后,继续搜索else//x〃向左搜索ifxq-data{f=q;q=q-Lson;}〉〃向右搜索else{f=q;q=q-Rson;}〃没找至if p==NULL returnNOTFOUND;U x〃无右儿子,用左儿子代替if p-Rson==NULL p pifp==f-Lson{f-Lson=p-Lson;delete p;}else{f-Rson=p-Lson;delete p;}else无左儿子,用右儿子代替if p-Lson==NULL//p pifp==f-Lson{f-Lson=p-Rson;delete p;}else{f-Rson=p-Rson;delete p;}以下是有两个儿子情况的处理else{//p〃有两个儿子,找的中序前驱p p〃是的左儿子s=p-Lson;s p没有右儿子,用代替用的值ifs-Rson==NULL{//s s pp-data=s-data;//s域代换的值域p〃删去p-Lson=s-Lson;sdelete s;}〃以下是有右儿子的情况else{s有右儿子,找的左儿子的最右子孙//sprr=s-Rson;〃用的值域代换whiler-Rson!=NULL{s=r;r=r-Rson;}p-data=r-data;r的值域删去p s-Rson=r-Lson;//rdelete r;〃返回删除成功信息return SUCC;〃重载形式void TBtree::preOrder{先序遍历”;coutvv”preOrderroot;cout«endl;〃前序递归访问二叉树递归void TBtree::preOrderptr r{〃是而不是ifr!=O{if,whilecout«r-data«n n;递归访问ifr-Lson!=0preOrderr-Lson;//〃递归访问ifr-Rson!=0preOrderr-Rson;〃利用重载的方法void TBtree::inOrder{中序遍历COUtVV”inOrderroot;cout«endl;〃中序访问二叉树递归void TBtree::inOrderptr r{〃是而不是ifr!=O{if,while递归访问ifr-Lson!=0inOrderr-Lson;//cout«r-data«n”;递归访问ifr-Rson!=0inOrderr-Rson;//〃重载形式void TBtree::postOrder{后序遍历coutvv”postOrderroot;cout«endl;〃后序遍历递归void TBtree::postOrderptr r{〃是而不是ifr!=O{if,while〃递归访问ifr-Lson!=0postOrderr-Lson;ifr-Rson!=0postOrderr-Rson;〃递归访问cout«r-data«n H;int main{TBtree bt;构造检索树=====endl;bt.creat;检索树操作构造完成!”cout«”\n vendl;int c=l;inti=0;〃构造菜单二检索树操作coutv\n=========vvendl;cout«n1先序遍历vvendl;cout«n2中序遍历vvendl;cout«n3后序遍历endl;cout«n4查找vvendl;cout«n5插入”endl;cout«n6删除”《endl;其他退出coutvv”vvendl;cout«u====================«end\;whilec{请选择操作代码:;coutvv”cin»i;switchi{〃选择菜单case1:。