北理工数据结构作业3.doc

《北理工数据结构作业3.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章作业1、简述一棵度为2的树与一棵二叉树有何区别？答：1）度为2的树一定有度为2的结点，而二叉树节点的度只要满足小于等于2即可，因此不一定有度为2的结点；2）度为2的树结点的孩子的顺序是无序的，而二叉树结点的孩子是有序的。2、假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。清画出该树。答：ABCDFGIEHJ3、假设二叉树如下，请分别写出先序、中序和后序遍历结果，并画出该二叉树对应的森林。ABCDEFGH答：先序遍历：ABDGCEFH中序遍历：DGBAECHF后序遍历：GD

2、BEHFCA该二叉树对应的森林：ABCDEFGH1、画出与下列已知序列对应的树T。树的先根次序访问的序列为：GFKDAIEBCHJ；树的后根次序访问的序列为：DIAEKFCJHBG。GFBKCHEJIAD1、请编写一个递归算法，将二叉树中所有结点的左、右子树相互交换。typedefstructBiTNode{TelemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;voidExchange(BiTree&T){BiTreeTemp;If(T->lc

3、hild

4、

5、T->rchild){Temp=T->lchild;T->lchild=T->rchild;T->rchild=Temp;}if(T->lchild)Exchange(T->lchild);if(T->rchild)Exchange(T->rchild);}1、请设计按层次顺序（同一层自左向右）遍历二叉树的算法。StatusLevelTraverse(BiTree&T,Status(*Visit)(TelemTypee)){LinkQueueQ;BiTreeb;InitQueue(Q);if(T)

6、{EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,b);Visit(b->data);if(b->lchild)EnQueue(Q,b->lchild);if(b->rchild)EnQueue(Q,b->rchild);}}returnOK;}实验三1、遍历二叉树。请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。答：示例：先序建树:依次输入二叉树的结点号，孩子为空的时候输入空格:输入：abdfce输出：先序遍

7、历二叉树为:abdfce中序遍历二叉树为:dfbaec后序遍历二叉树为:fdbeca代码如下：#include#include#defineOVERFLOW-2typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;BiTreecreate(BiTreeT){charch;scanf("%c",&ch);if(ch=='')T=NULL;else{T=(BiTree)mallo

8、c(sizeof(BiTNode));if(!T)exit(OVERFLOW);T->data=ch;T->lchild=create(T->lchild);T->rchild=create(T->rchild);}returnT;}voidPreOrderTraverse(BiTreeT){if(T){printf("%c",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}voidInOrderTraverse(BiTre

9、eT){if(T){InOrderTraverse(T->lchild);printf("%c",T->data);InOrderTraverse(T->rchild);}}voidPostOrderTraverse(BiTreeT){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c",T->data);}}voidmain(){BiTreeT;printf("先序建树:依次输入二叉树的结点号，孩子为空的时候输

10、入空格:");T=create(T);printf("先序遍历二叉树为:");PreOrderTraverse(T);printf("中序遍历二叉树为:");InOrderTraverse(T);printf("后序遍历二叉树为:");PostOrderTraverse(T);}2、按层次遍历二叉树。答：示例：先序建树:依次输入二叉树的结点号，孩子为空的时候输入空格:输入：abdfc