河北大学：《数据结构》课程教学资源（习题解答）第七章 树与森林

本章解答只给出算法描述,1~7题略。 1.一棵度为2的树与一棵二叉树有何区别?树与二叉树之间有何区别? 2对于图2所示的树,试给出: (1)双亲数组表示法示意图: (2)孩子链表表示法示意图 (3)孩子兄弟链表表示法示意图 (2题图) 3画出下图所示的森林经转换后所对应的二叉树,并指出在二叉链表中某结点所对应的森 林中结点为叶子结点的条件。 (3题图) (4题图) 4将右上图所示的二叉树转换成相应的森林。 5在具有n(m1)个结点的各棵树中,其中深度最小的那棵树的深度是多少?它共有多 少叶子和非叶子结点?其中深度最大的那棵树的深度是多少?它共有多少叶子和非叶子结 点? 6画出和下列已知序列对应的树T: 树的先根次序访问序列为: GFKDAIEBCH 树的后根访问次序为: DIAEKFCJHBG 7画出和下列已知序列对应的森林F 森林的先序次序访问序列为: ABCDEFGHIJKL 森林的中序访问次序为: CBEFDGAJIKLH 8.对以孩子一兄弟链表表示的树编写计算树的深度的算法 typedef struct TreeNodei datatype struct TreeNode *child, *nextsibling 3 Nodettpe, *CSTree int high(CSTree t) if (t==NULL return(0) 14

144 本章解答只给出算法描述，1~7 题略。 ⒈一棵度为 2 的树与一棵二叉树有何区别？树与二叉树之间有何区别？ ⒉对于图 2 所示的树，试给出： ⑴双亲数组表示法示意图； ⑵孩子链表表示法示意图； ⑶孩子兄弟链表表示法示意图。 ⒊画出下图所示的森林经转换后所对应的二叉树，并指出在二叉链表中某结点所对应的森 林中结点为叶子结点的条件。 (3 题图 ) （4 题图） ⒋将右上图所示的二叉树转换成相应的森林。 ⒌在具有 n（n>1）个结点的各棵树中，其中深度最小的那棵树的深度是多少？它共有多 少叶子和非叶子结点？其中深度最大的那棵树的深度是多少？它共有多少叶子和非叶子结 点？ ⒍画出和下列已知序列对应的树 T： 树的先根次序访问序列为：GFKDAIEBCHJ； 树的后根访问次序为：DIAEKFCJHBG。 ⒎画出和下列已知序列对应的森林 F： 森林的先序次序访问序列为：ABCDEFGHIJKL； 森林的中序访问次序为：CBEFDGAJIKLH。 ⒏对以孩子－兄弟链表表示的树编写计算树的深度的算法。 typedef struct TreeNode{ datatype data; struct TreeNode *child, *nextsibling ; }NodeTtpe , *CSTree; int high(CSTree t ) { if ( t= =NULL ) return ( 0 ) ; B C D I G H A F E J G H D E F B C A G F E D I B C A H J K M N （2 题图）

else hl=high(t->child h2=high(t->nextsibling ) return(max(h1+l,h2)) 9对以孩子链表表示的树编写计算树的深度的算法。 算法略 10.对以双亲链表表示的树编写计算树的深度的算法。 typedef structmath)

145 else { h1=high(t->child ) ; h2=high(t->nextsibling ); return(max(h1+1,h2)); } } ⒐对以孩子链表表示的树编写计算树的深度的算法。 算法略 ⒑对以双亲链表表示的树编写计算树的深度的算法。 typedef struct{ datatype data; int parent ; }NodeType; int high(NodeType t[ ], int n) { maxh=0; for (i=0 ;imaxh)

max=h return( max)

146 maxh=h; } return(maxh); }