已阅读5页,还剩18页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
#include/#includemystring.h#include/#include/二叉链表结点的类定义using namespace std;templateclass binarytreenode/friend class binarytree;private:T info; binarytreenode * left; binarytreenode * right;public: /binarytreenode() binarytreenode(T ele)info=ele;left=NULL;right=NULL; binarytreenode(T ele,binarytreenode * l,binarytreenode * r)info=ele;left=l;right=r;T value()const; binarytreenode * leftchild()const; binarytreenode * rightchild()const;void setleftchild(binarytreenode *l); void setrightchild(binarytreenode *l);void setvalue(T val);/*templatebinarytreenode:binarytreenode()left=null;right=null;templatebinarytreenode:binarytreenode(T ele)info=ele;left=NULL;right=NULL;templatebinarytreenode:binarytreenode(T ele,binarytreenode * l,binarytreenode * r) info=ele;left=l;right=r;*/templateT binarytreenode:value()constreturn info;templatebinarytreenode * binarytreenode:leftchild()constreturn left;templatebinarytreenode * binarytreenode:rightchild()constreturn right;templatevoid binarytreenode:setleftchild(binarytreenode * l)left=l;templatevoid binarytreenode:setrightchild(binarytreenode * r)right=r;templatevoid binarytreenode:setvalue(T val)info=val;/二叉链表的类定义templateclass binarytreeprivate:binarytreenode * root;public:binarytree()root=NULL;binarytree()deletebinarytree(root);binarytreenode * Root()return root;binarytreenode * parent(binarytreenode * current);binarytreenode * leftsibling(binarytreenode * current);binarytreenode * rightsibling(binarytreenode * current);void creattree(T info);void creattree(T info,binarytree & lefttree,binarytree & righttree);/void creattree(mystring a);void deletebinarytree(binarytreenode * root);void preorder1(binarytreenode * root); /保存当前结点的前序周游void preorder(binarytreenode * root); /保存当前结点右孩子的前序周游void inorder(binarytreenode * root); void postorder(binarytreenode * root);void levelorder(binarytreenode * root);int deep(binarytreenode * current); /求出一个结点的深度 void numofleaf(binarytreenode * root,int & i); /叶子个数/void high(binarytreenode * root,int & i); /高度 void shadow(binarytreenode * root); /镜面影射 void commonp(binarytreenode * p,binarytreenode * q); /求两结点的最近的共同祖先;/找双亲templatebinarytreenode * binarytree:parent(binarytreenode * current)using std:stack;binarytreenode * pointer=root;stackbinarytreenode * astack;if(root=null|current=null)return null;while(!astack.isempty()|pointer)if(pointer)if(pointer.left=current|pointer.right=current)return pointer;astack.push(poiter);pointer=pointer.left;elsepointer=astack.top();astack.pop(); pointer=pointer.right;/找左兄弟templatebinarytreenode * binarytree:leftsibling(binarytreenode * current)binarytreenode * pointer=parent(current);return pointer.left;/找右兄弟templatebinarytreenode * binarytree:rightsibling(binarytreenode * current)binarytreenode * pointer=parent(current);return pointer.right;/生成新树templatevoid binarytree:creattree(const T info)root=new binarytreenode (info);/l=r=NULL;/生成新树templatevoid binarytree:creattree(T info,binarytree & lefttree,binarytree & righttree)root=new binarytreenode (info,lefttree.root,righttree.root);lefttree.root=righttree.root=NULL;/用字符串生成新树/*templatevoid binarytree:creattree(mystring a)using std:stack;stackbinarytreenode * astack;root=new binarytreenode (a0);binarytreenode * pointer=root;int i;for(i=1;ai!=0;i+)if(ai=()astack.push();else if(ai=)astack.top();pointer=rightsibling(pointer); else pointer.left=new binarytreenode (ai);pointer=pointer-leftchild(); */删除树/*templatevoid binarytree:deletebinarytree(binarytreenode * root)if(root!=NULL)deletebinarytree(root-leftchild();deletebinarytree(root-rightchild();delete root;/保存当前结点的前序周游templatevoid binarytree:preorder1(binarytreenode * root)using std:stack;binarytreenode * pointer=root;stackbinarytreenode * astack;while(!astack.empty()|pointer)if(pointer)coutvalue()leftchild();elsepointer=astack.top();astack.pop();pointer=pointer-rightchild();/保存当前结点右孩子的前序周游templatevoid binarytree:preorder(binarytreenode * root)using std:stack;binarytreenode * pointer=root;stackbinarytreenode * astack;astack.push(NULL);while(!astack.empty()|pointer)if(pointer)coutvalue() rightchild()!=NULL)astack.push(pointer-rightchild();pointer=pointer-leftchild();else pointer=astack.top();astack.pop();/中序周游templatevoid binarytree:inorder(binarytreenode * root)using std:stack;binarytreenode * pointer=root;stackbinarytreenode * astack;while(!astack.isempty()|pointer)if(pointer) astack.push(pointer); pointer=pointer.left;elsepointer=astack.top();t;pointer=poiter.right;/后序周游templatevoid binarytree:postorder(binarytreenode * root)using std:stack;enum tagsleft,right;templateclass stackelementpublic:binarytreenode * pointer;tags tag;stackstackelement * astack;stackelement element;binarytreenode * pointer=root;while(!astack.isempty()|pointer) while(pointer)element.pointer=pointer; element.tag=left;astack.push(element);pointer=pointer.leftchild();element=astack.top;pointer=element.pointer;if(element.tag=left)element.tag=right;astack.push(element);pointer=pointer.rightchild();elsecoutpointer.value();pointer=null;/求一个结点的深度templateint binarytree:deep(binarytreenode * current)int i;binarytreenode * pointer=null;while(pointer!=root)pointer=parent(current);i+;current=pointer;return i;/求叶结点个数templatevoid binarytree:numofleaf(binarytreenode * root,int & i)binarytreenode * pointer=root;if(pointer.leftchild()=pointer.rightchild()=null)i+;elsenumofleaf(pointer.leftchild(),i);numofleaf(pointer.rightchild(),i);/*templateint binarytree:high(binarytreenode * root,int & i)binarytreenode * pointer=root;if(pointer.leftchild()=pointer.rightchild()=null)i+;*/将一棵树镜面影射templatevoid binarytree:shadow(binarytreenode * root)binarytreenode * temp=null;binarytreenode * pointer=root;using std:queue;queuebinarytreenode * aqueue;if(pointer)aqueue.push(pointer);while(! aqueue.isempty()pointer=aqueue.front();temp=pointer.left;pointer.left=pointer.right;pointer.right=temp;if(pointer.leftchild()aqueue.push(pointer.leftchild();if(pointer.rightchild()aqueue.push(pointer.
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 应急预案汛期学校安全工作应急预案范文
- 期中考试国旗下励志讲话
- 一年级下册语文第四单元基础测评卷(有答案含解析)(教师版)
- 职业健康检查机构备案管理办法
- 2024年无产权车库买卖协议范本(二篇)
- 2024年音响设备租赁协议模板(二篇)
- 2024年租房定金协议(三篇)
- 2024年大型货车租赁合同标准版(二篇)
- 2024年专利转让合同范文(2篇)
- 2024年花卉租赁合同电子版(三篇)
- 2024届高考语文最后一堂课
- 2024年公务员(国考)之行政职业能力测验真题汇编附答案(黄金题型)
- 房屋以旧换新合同书 2024
- 语言、文化与交际智慧树知到期末考试答案2024年
- 广东省莞市东华中学2024年中考押题化学预测卷含解析
- JJG 313-2010测量用电流互感器
- 小学英语人教(精通)版三年级起点《Fun time 1 Recycle 1》优秀教学设计五年级下册-五年级英语教案
- 论我国商业银行个人理财业务风险控制(Risk control of personal financial services in commercial banks in China)
- 文献检索过程ppt课件.ppt
- 部编版语文五年级下册词句段运用复习
- 职业危害告知牌(LNG站).doc
评论
0/150
提交评论