北理工数据结构作业3

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)