北理工数据结构作业3_第1页
北理工数据结构作业3_第2页
北理工数据结构作业3_第3页
北理工数据结构作业3_第4页
北理工数据结构作业3_第5页
已阅读5页,还剩7页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论