欢迎来到天天文库
浏览记录
ID:57729485
大小:43.00 KB
页数:12页
时间:2020-09-02
《北理工数据结构作业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
此文档下载收益归作者所有