




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第六章作业1、 简述一棵度为2的树与一棵二叉树有何区别?答:1) 度为2的树一定有度为2的结点,而二叉树节点的度只要满足小于等于2即可,因此不一定有度为2的结点;2) 度为2的树结点的孩子的顺序是无序的,而二叉树结点的孩子是有序的。2、 假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。清画出该树。答:ABCDFGIEHJ3、 假设二叉树如下,请分别写出先序、中序和后序遍历结果,并画出该二叉树对应的森林。ABCDEFGH答:先序遍历:ABDGCEFH中序遍历:DGBAECHF后序遍历:GDBEHFCA该二叉树对应的森林:ABCDEFGH4、 画出与下列已知序列对应
2、的树T。树的先根次序访问的序列为:GFKDAIEBCHJ;树的后根次序访问的序列为:DIAEKFCJHBG。GFBKCHEJIAD5、 请编写一个递归算法,将二叉树中所有结点的左、右子树相互交换。typedef struct BiTNode TelemType data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;void Exchange(BiTree &T) BiTree Temp; If(T-lchild|T-rchild) Temp=T-lchild; T-lchild=T-rchild; T-rchild=Temp; if(T-lc
3、hild) Exchange(T-lchild); if(T-rchild) Exchange(T-rchild);6、 请设计按层次顺序(同一层自左向右)遍历二叉树的算法。Status LevelTraverse(BiTree &T,Status (*Visit)(TelemType e)LinkQueue Q;BiTree b;InitQueue(Q);if(T) EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,b); Visit(b-data); if(b-lchild)EnQueue(Q,b-lchild); if(b-rchild)EnQue
4、ue(Q,b-rchild); return OK;实验三1、遍历二叉树。请输入一棵二叉树的扩展的前序序列,经过处理后生成一棵二叉树,然后对于该二叉树输出前序、中序和后序遍历序列。答:示例:先序建树:依次输入二叉树的结点号,孩子为空的时候输入空格:输入:abd f ce 输出:先序遍历二叉树为:abdfce中序遍历二叉树为:dfbaec后序遍历二叉树为:fdbeca代码如下:#include#include#define OVERFLOW -2typedef struct BiTNodechar data;struct BiTNode *lchild,*rchild;BiTNode,*BiTr
5、ee;BiTree create(BiTree T)char ch;scanf(%c,&ch);if(ch= )T=NULL;elseT=(BiTree)malloc(sizeof(BiTNode);if(!T)exit(OVERFLOW);T-data=ch;T-lchild=create(T-lchild);T-rchild=create(T-rchild);return T;void PreOrderTraverse(BiTree T) if(T) printf(%c,T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchi
6、ld); void InOrderTraverse(BiTree T) if(T) InOrderTraverse(T-lchild); printf(%c,T-data); InOrderTraverse(T-rchild); void PostOrderTraverse(BiTree T) if(T) PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(%c,T-data); void main() BiTree T;printf(先序建树:依次输入二叉树的结点号,孩子为空的时候输入空格:n);T=create(
7、T);printf(n先序遍历二叉树为:);PreOrderTraverse(T);printf(n中序遍历二叉树为:);InOrderTraverse(T);printf(n后序遍历二叉树为:);PostOrderTraverse(T);2、按层次遍历二叉树。答:示例:先序建树:依次输入二叉树的结点号,孩子为空的时候输入空格:输入:abd f ce 输出:层次遍历二叉树:abcdef代码如下:#include#include#include#define OK 1#define ERROR 0#define OVERFLOW -2typedef struct BiTNodechar data
8、;struct BiTNode *lchild,*rchild;/左右孩子指针BiTNode,*BiTree;typedef struct QNodeBiTree data;struct QNode *next;QNode,*QueuePtr;typedef struct QueuePtr front;/对头指针QueuePtr rear;/队尾指针LinkQueue;int InitQueue(LinkQueue &Q)/构造一个空队列Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.fron
9、t-next=NULL;return OK;int EnQueue(LinkQueue &Q,BiTree e)/插入元素e为Q的新的对位队尾元素QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);/存储分配失败p-data=e; p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;int DeQueue(LinkQueue &Q,BiTree &e)/若队列不空,则删除Q的队头元素,用e返回其值,并返回OK/否则返回ERRORQueuePtr p;if(Q.front=Q.re
10、ar) return ERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;int QueueEmpty(LinkQueue Q)if(Q.front=Q.rear)return 1;else return 0;BiTree CreateBiTree(BiTree &T)/按照先序次序输入二叉树中结点的值(一个字符),空格字符表示空树,/构造二叉链表表示的二叉树T。char ch;scanf(%c,&ch);if(ch= ) T=NULL;else T=(BiTree)malloc(sizeof(BiTNode); if(!T)exit(OVERFLOW); T-data=ch;/生成根结点 T-lchild=CreateBiTree(T-lchild);/构造左子树 T-rchild=CreateBiTree(T-rchild);/构造右子树return T;void LevelTraverse(BiTree T)LinkQueue Q;BiTree b;InitQueue(Q);if(T) EnQueue(Q,T); while(!QueueEmpty(Q) DeQueue(Q,b); printf(%c,b-data)
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- JJF(烟草)4.1-2024烟草及烟草制品连续流动法测定常规化学成分测量不确定度评定指南第1部分:水溶性糖
- 考研复习-风景园林基础考研试题附参考答案详解【基础题】
- 考研复习-风景园林基础考研试题(全优)附答案详解
- 风景园林基础考研资料试题及参考答案详解【典型题】
- 2025-2026年高校教师资格证之《高等教育法规》通关题库附答案详解(综合卷)
- 2025年江西省高速公路投资集团有限责任公司招聘笔试备考题库含答案详解(预热题)
- 2024年山东华兴机械集团有限责任公司人员招聘笔试备考题库含答案详解(综合卷)
- 2025年黑龙江省五常市辅警招聘考试试题题库附答案详解(综合题)
- 2025年河北省定州市辅警招聘考试试题题库含答案详解(能力提升)
- 2025年K12课外辅导行业双减政策下线上线下融合模式探索报告
- 综合实践活动六年级上册全册讲课课件
- 道路运输企业和城市客运企业安全生产重大事故隐患判定标准2023
- 国家开放大学-传感器与测试技术实验报告(实验成绩)
- 天津开放大学《集装箱班轮运输业务与法律》终结性考试复习题库(附答案)
- 部编版小学语文六年级下册毕业升学模拟测试卷3份 (含答案) (二十一)
- 码头水手作业安全操作规程
- 2023企业法律顾问协议范本
- 反应釜课程设计
- 环境试验项目表
- 标识标牌制作服务方案(投标方案)
- 工程变更矩阵图
评论
0/150
提交评论