数据结构 第6章作业

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

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

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

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

4、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;}