树相关算法实现.docx
- 文档编号:9612008
- 上传时间:2023-05-20
- 格式:DOCX
- 页数:12
- 大小:16.25KB
树相关算法实现.docx
《树相关算法实现.docx》由会员分享,可在线阅读,更多相关《树相关算法实现.docx(12页珍藏版)》请在冰点文库上搜索。
树相关算法实现
树相关算法C++实现
.cpp部分
#include
#include"tree2.h"
usingnamespacestd;
intmain(){
tree
ints;
cout<<"如果要创建树,请输入stop的值:
"< cin>>s; tree1.createtree(s);//创建树// intch; cout<<"1: 获取stop的值: "< cout<<"2: 获取根节点地址: "< cout<<"3: 查找左孩子: "< cout<<"4: 查找右兄弟: "< cout<<"5: 查找父节点: "< cout<<"6: 查找指定值的节点: "< cout<<"7: 删除子树: "< cout<<"8: 先根遍历: "< cout<<"9: 后根遍历: "< cin>>ch; while(ch! =0){ switch(ch){ case1: {cout<<"stop的值为: "<<""< case2: {cout<<"根节点地址: "<<""< case3: {cout<<"输入想查找左孩子的节点的值: "< intitem;cin>>item; treenode cout<<"左孩子节点地址: "<<""< break;} case4: {cout<<"输入想查找右兄弟的节点的值: "< intitem;cin>>item; treenode cout<<"右兄弟节点地址: "<<""< break;} case5: {cout<<"输入想查找父节点的节点值: "< intitem;cin>>item; treenode cout<<"父节点地址: "<<""< break;} case6: {cout<<"输入想查找指定值的节点值: "< intitem;cin>>item; cout<<"指定值节点地址: "<<""< break;} case7: {cout<<"输入想删除的节点值: "< intitem;cin>>item; treenode tree1.delsubtree(tree1.getroot(),t); break;} case8: {tree1.preorder(tree1.getroot()); break;} case9: {tree1.postorder(tree1.getroot()); break;} } cout<<"还需要什么帮助吗? "< cin>>ch; } if(ch==0)cout<<"谢谢使用"< return0; } .h部分 tree.h #include usingnamespacestd; template classtreenode{ private: Tdata; treenode public: treenode(Titem=0,treenode data(item),firstchild(child),nextbrother(brother){} treenode voidsetfirstchild(treenode treenode voidsetnextbrother(treenode T&getdata(){returndata;} voidsetdata(T&item){data=item;} }; template classtree{ private: treenode Tstop; public: tree(){root=NULL;} treenode voidcreatetree(Ttostop); treenode voidsetroot(treenode Tgetstop(){returnstop;} voidsetstop(Ts){stop=s;} treenode treenode treenode treenode voidpreorder(treenode voidpostorder(treenode voidleveorder(treenode voidnorcepreorder(treenode voidnorcepostorder(treenode voiddel(treenode voiddelsubtree(treenode }; template treenode : create(){//函数无问题,请注意创建树时的数据输入次序// treenode Titem; cout<<"输入数的节点元素: "< cin>>item; if(item==stop){t=NULL;returnt;} else{ if(! (t=newtreenode t1=create(); t->setfirstchild(t1); t2=create(); t->setnextbrother(t2); returnt; } } template voidtree : createtree(Ttostop){ setstop(tostop); root=create(); } template treenode : findfather(treenode if(t==NULL||p==NULL){cout<<"输入节点异常"< treenode treenode while(q! =NULL&&q! =p){ result=findfather(q,p); if(! result)q=q->getnextbrother(); elsereturnresult; } if(q==p)returnt; elsereturnNULL; } template treenode : findtarget(treenode if(t==NULL){cout<<"根节点为空"< if(t->getdata()==target)returnt; treenode treenode while(p! =NULL&&(result=findtarget(p,target))==NULL)p=p->getnextbrother();//左孩子中未找到target// returnresult;//左孩子中找到target// } template treenode : firstchild(treenode if(p==NULL){returnNULL;} if(p! =NULL&&p->getfirstchild()! =NULL)returnp->getfirstchild(); returnNULL; } template treenode : nextbrother(treenode if(p==NULL){cout<<"节点为空"< if(p! =NULL&&p->getnextbrother()! =NULL)returnp->getnextbrother(); returnNULL; } template voidtree : del(treenode if(p==NULL){cout<<"异常,欲删除空节点! "< treenode while(q! =NULL){ next=q->getnextbrother(); del(q); q=next; } deletep; } template voidtree : delsubtree(treenode if(t==NULL||p==NULL)cout<<"异常,有参数为空! "< if(t! =NULL&&p! =NULL){ if(t==p){del(p);root=NULL;} treenode result=findfather(t,p); if(result){ if((result->getfirstchild())==p){ result->setfirstchild(p->getnextbrother()); del(p); return; } else{ q=result->getfirstchild(); while(q->getnextbrother()! =p)q=q->getnextbrother(); q->setnextbrother(p->getnextbrother()); del(p); return; } } } } template voidtree : preorder(treenode if(t==NULL)return; if(t! =NULL){ cout< treenode child=firstchild(t); while(child){ preorder(child); child=nextbrother(child); } } } template voidtree : postorder(treenode if(t==NULL)return; if(t! =NULL){ treenode while(p){ postorder(p); p=nextbrother(p); } cout< } } tree2.h #include #include"tree.h" usingnamespacestd; template structslnode{ public: Tdata; slnode slnode(Td=0,slnode data(d),next(s){} }; template classqueue{ private: slnode intcount; public: queue(){front=rear=NULL;} ~queue(){clear();} boolisempty(){if(front==NULL)returntrue;elsereturnfalse;} voidinsert(T&item); voidqdelete(T&item); voidclear(); }; template voidqueue : insert(T&item){ if(isempty()){front=rear=newslnode else{ rear->next=newslnode rear=rear->next; } } template voidqueue : qdelete(T&item){ if(isempty()){cout<<"队列为空"< slnode item=temp->data; front=front->next; count--; deletetemp; if(count==0)rear=NULL; } template voidqueue : clear(){ while(! isempty()){ rear=front; front=front->next; deleterear; count--; } rear=NULL; } template voidtree : leveorder(treenode queue if(t! =NULL){ treenode q.insert(t); while(! q.isempty()){ q.qdelete(p); cout< p=firstchild(p); while(p! =NULL){ q.insert(p); p=nextbrother(p); } } } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 相关 算法 实现