数据结构第6章作业.pdf

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

1、第六章作业参见《数据结构题集》第6章部分P38。1、一棵度为2的树与一棵二叉树有何区别？（题集6.2）二叉树是颗有序树，但度为2的树则未必有序。2、假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树（题集6.29）。3、假设二叉树如下，请分别写出先序、中序和后序遍历结果，并画出该二叉树对应的森林。ABCDEFGH答：先序遍历：ABDGCEFH中序遍历：DGBAECHF后序遍历：GDBEHFCA4、画出与下列已知序列对应的树T。（题集6.23）树的先根次序访问

2、的序列为：GFKDAIEBCHJ；树的后根次序访问的序列为：DIAEKFCJHBG。5、请编写一个递归算法，将二叉树中所有结点的左、右子树相互交换。（题集6.43）6、6.43解：//按先序交换二叉树的左右子树StatusExchangeBiTree(BiTree&T){BiTreep;if(T){p=T->lchild;T->lchild=T->rchild;T->rchild=p;ExchangeBiTree(T->lchild);ExchangeBiTree(T->rchild);}retu

3、rnOK;}7、对于那些所有非叶子结点均有非空左右子树的二叉树，试问：有n个叶子结点的树中共有多少个结点？2n-18、森林与二叉树的转换。（题集6.21）树二叉树根根第一个孩子左孩子右兄弟右孩子8、选做：请设计按层次顺序（同一层自左向右）遍历二叉树的算法。（题集6.47）typedefBiTreeQElemType;#include"c:YinincludeQueue.h"StatusLevelOrderTraverse(BiTree&T,Status(*Visit)(TElemTypee)

4、){QElemTypep;Queueq;InitQueue(q);if(T)EnQueue(q,T);while(!QueueEmpty(q)){DeQueue(q,p);Visit(p->data);if(p->lchild)EnQueue(q,p->lchild);if(p->rchild)EnQueue(q,p->rchild);}returnOK;}（注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。可复制、编制，期待你的好评与关注）