


版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、树和二叉树以下问题要求统一在一个大程序里解决。10、按先序遍历的扩展序列建立二叉树的存储构造11、二叉树先序、中序、后序遍历的递归算法12、二叉树中序遍历的非递归算法13、二叉树层次遍历的非递归算法14、求二叉树的深度(后序遍历)15、建立树的存储构造16、求树的深度17、源程序代码:/tree.cpp:Definestheentrypointfortheconsoleapplication./#includestdafx.h#includestdio.h#includestdlib.h#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defin
2、eOK1#defineERROR0#defineTRUE1#defineFALSE0#defineOVERFLOW-1typedefcharTElemType;/元素数据类型typedefintStatus;/*二叉链表储存构造*/typedefstructBiTNodeTElemTypedata;structBiTNode*lchild,*rchild;BiTNode,*BiTree;boolCreateBiTree(BiTree&T)/先序序列建立二叉树charch;scanf(%c,&ch);if(ch=*)T=NULL;elseif(!(T=(BiTNode*)malloc(sizeo
3、f(BiTNode)returnERROR;T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);returnOK;StatusPrintElement(TElemTypee)/访问函数printf(%c,e);returnOK;StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemType)/先序遍历二叉树的递归算法if(T)if(Visit(T-data)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverse(T-rchild,Vi
4、sit)returnOK;returnERROR;elsereturnOK;StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemType)/中序遍历二叉树的递归算法if(T)if(InOrderTraverse(T-lchild,Visit)if(Visit(T-data)if(InOrderTraverse(T-rchild,Visit)returnOK;returnERROR;elsereturnOK;StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemType)/后序遍历二叉树的递归算法i
5、f(T)if(PostOrderTraverse(T-lchild,Visit)if(PostOrderTraverse(T-rchild,Visit)if(Visit(T-data)returnOK;returnERROR;elsereturnOK;/*栈存储构造及操作*/typedefstructBiTree*base;BiTree*top;intstacksize;Stack;StatusInitStack(Stack&S)/构造空栈S.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree);if(!S.base)exit(OVERFLOW
6、);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;StatusGetTop(StackS,BiTree&e)/读栈顶元素if(S.top=S.base)returnERROR;e=*(S.top-1);returnOK;StatusPush(Stack&S,BiTreee)/入栈if(S.top-S.base=S.stacksize)S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree);if(!S.base)exit(OVERFLOW);S.to
7、p=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;returnOK;StatusPop(Stack&S,BiTree&e)/出栈if(S.top=S.base)returnERROR;e=*-S.top;returnOK;StatusStackEmpty(StackS)/判栈空if(S.base=S.top)returnTRUE;elsereturnFALSE;StatusInOrderTraverse2(BiTreeT,Status(*Visit)(TElemType)/中序遍历二叉树的非递归算法StackS;BiTreep
8、;InitStack(S);Push(S,T);while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-lchild);Pop(S,p);if(!StackEmpty(S)Pop(S,p);if(!Visit(p-data)returnERROR;Push(S,p-rchild);returnOK;#defineMAXLEN100voidLevelOrderTraverse(BiTreeT,Status(*Visit)(TElemType)/层次遍历二叉树structnodeBiTreevecMAXLEN;intf,r;q;q.f=0;q.r=0;if
9、(T!=NULL)Visit(T-data);q.vecq.r=T;q.r=q.r+1;while(q.flchild!=NULL)Visit(T-lchild-data);q.vecq.r=T-lchild;q.r=q.r+1;if(T-rchild!=NULL)Visit(T-rchild-data);q.vecq.r=T-rchild;q.r=q.r+1;intBiTreeDepth(BiTreeT)/求二叉树的深度intdepthval,depthLeft,depthRight;if(!T)depthval=0;elsedepthLeft=BiTreeDepth(T-lchild);d
10、epthRight=BiTreeDepth(T-rchild);depthval=1+(depthLeftdepthRight?depthLeft:depthRight);returndepthval;/*树的二叉链表储存构造*/typedefstructCSNodeTElemTypedata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;/*队列存储构造及操作*/typedefstructQNodeCSTreedata;structQNode*next;QNode,*QueuePtr;typedefstructQueuePtrfron
11、t;QueuePtrrear;LinkQueue;StatusInitQueue(LinkQueue&Q)/构造空队列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;returnOK;StatusDestoryQueue(LinkQueue&Q)/销毁队列while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;returnOK;StatusEnQueue(LinkQueue&Q,CSTreee
12、)/入队QueuePtrp;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnOK;StatusDeQueue(LinkQueue&Q,CSTree&e)/出队QueuePtrp;if(Q.front=Q.rear)returnERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);returnOK;StatusGetHead
13、(LinkQueue&Q,CSTree&e)/读队头QueuePtrp;if(Q.front=Q.rear)returnERROR;p=Q.front-next;e=p-data;returnOK;CSTreeGetTreeNode(TElemTypee)/建立树的孩子/-兄弟链表结点CSTreep;p=(CSTree)malloc(sizeof(CSNode);if(!p)exit(OVERFLOW);p-data=e;p-firstchild=NULL;p-nextsibling=NULL;returnp;StatusCreatTree(CSTree&T)/建立树的孩子/-兄弟链表char
14、first=,second=;intresult=0;LinkQueueQ;CSTreep,s,r;InitQueue(Q);T=NULL;for(scanf(%c%c,&first,&second);second!=#;result=scanf(%c%c,&first,&second)p=GetTreeNode(second);EnQueue(Q,p);if(first=#)T=p;elseGetHead(Q,s);while(s-data!=first)DeQueue(Q,s);GetHead(Q,s);if(!(s-firstchild)s-firstchild=p;r=p;elser-
15、nextsibling=p;r=p;returnOK;intTreeDepth(CSTreeT)/求树的深度inth1,h2;if(!T)return0;elseh1=TreeDepth(T-firstchild);h2=TreeDepth(T-nextsibling);return(h1+1)h2)?(h1+1):h2);intmain(intargc,char*argv)BiTreetestT;printf(请输入二叉树先序序列如AB*C*:);CreateBiTree(testT);printf(n);printf(二叉树的深度是:);printf(%d,BiTreeDepth(testT);printf(n);printf(先序递归遍历顺序:);PreOrderTraverse(testT,PrintElement);printf(n);printf(中序递归遍历顺序:);InOrderTraverse(testT,PrintElement);printf(n);printf(后序递归遍历顺序:);PostOrderTraverse(testT,PrintElement);printf(n);printf(层次非递归遍历顺序:);LevelOrderTraverse(testT,PrintElement
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 智慧城市环保监测网络布局与可持续发展战略
- 抖音商户广告投放效果评估制度
- 全球铀矿资源分布优化与核能产业技术创新研究报告
- 公交优先战略2025年城市交通拥堵治理的路径优化与建议报告
- CDA-IN-4-生命科学试剂-MCE
- 广东科贸职业学院《科学社会学》2023-2024学年第一学期期末试卷
- 陕西电子信息职业技术学院《精神健康》2023-2024学年第一学期期末试卷
- 湖北省恩施州利川市谋道镇苏马荡教育集团2024年九上化学期末综合测试试题含解析
- 鹤壁能源化工职业学院《影像进阶设计》2023-2024学年第一学期期末试卷
- 黑龙江三江美术职业学院《儿童生理与卫生学》2023-2024学年第一学期期末试卷
- 福建省南平市2022-2023学年高二下学期期末生物试题(解析版)
- 英语初一升初二衔接
- 翰威特任职资格撰写培训材料
- 物业工程部半年工作总结PPT模板下载
- 物资设备询价汇总表
- GB/T 24186-2022工程机械用高强度耐磨钢板和钢带
- 劳动合同(通用版)
- 英语口语 购物课件
- 膀胱镜检查记录
- DBJ50-112-2016 现浇混凝土桥梁梁柱式模板支撑架安全技术规范
- 汽车维修安全生产管理制度大全
评论
0/150
提交评论