东北大学：《数据结构》课程教学资源（学习资料）第六章 参考答案

第六章参考答案 、名词解释(略) 、填空题 1、分支层次、根、直接前趋 2、子孙、祖先 3、空、只含根、非空左子树、非空右子树、非空左右子树 4、21 6、n2+1 7、最大值、完全 8、foor(logn)+1 9、根、foor(i/2)、左孩子、右孩子、2、右孩子、2i+1 顺序、链式 1234 根根 指向该结点的一个孩子、空指针NUL 2n、n-l、n+1 二叉链表、三叉链表 16、 虚结点 17, *count++, countleaf(l->chile, count) 18、访问根结点、遍历左子树、遍历右子树 19、DLR、LDR、LRD、先根(或前序)遍历、中根(或中序)遍历、后根(或后序) 遍历 先根遍历、后根遍历、层次遍历 21 非终端结点、终端结点 WPL (T) i<k, x,TI]. wt, k+i, k+i, m+n, x,y 第 先根 26, floor(n/2), 1, n, floor(n/2)+1 27、 后面 相同 左子树、右子树、左子树、右子树 30、 树 31 最短、较近 (A),(E、G、I、J、K、 P、Q、R),(3),(4),(5),(J、K)(C) 树、二叉树 只有一个根结点的树、空二叉树 37

1 第六章 参考答案 一、名词解释（略） 二、填空题 1、 分支层次、根、直接前趋 2、 子孙、祖先 3、 空、只含根、非空左子树、非空右子树、非空左右子树 4、 2 i-1 5、 2 k -1 6、 n2+1 7、 最大值、完全 8、 floor(log2n)+1 9、 根、floor(i/2)、左孩子、右孩子、2i、右孩子、2i+1 10、 顺序、链式 11、 根 12、 根、root 13、 指向该结点的一个孩子、空指针 NULL 14、 2n、n-1、n+1 15、 二叉链表、三叉链表 16、 虚结点 17、 *count++,countleaf(l->rchile,count) 18、 访问根结点、遍历左子树、遍历右子树 19、 DLR、LDR、LRD、先根（或前序）遍历、中根（或中序）遍历、后根（或后序） 遍历 20、 先根遍历、后根遍历、层次遍历 21、 非终端结点、终端结点 22、 WPL（T）＝ 23、 i<k,x,T[j].wt,k+i,k+i,m+n,x,y 24、 第一 25、 先根 26、 floor(n/2),l,n,floor(n/2)+1 27、 后面 28、 相同 29、 左子树、右子树、左子树、右子树 30、 树 31、 最短、较近 32、 2m-1 33、 （A），（E、G、I、J、K、L、N、O、P、Q、R），（3），（4），（5），（J、K）（C） 34、 1、0 35、 树、二叉树 36、 只有一个根结点的树、空二叉树 37、 n-1

n-2m+1 39 、答案见图 WPL=165 41、m-1 42、本题有一定的难度,其求解方法如下:设总结点数为n度为0、1、2、3的结点数分别 为no,n1,n3,则有下面两个等式成立 n=nO+nl+n2+n3/*结点数* n-1=n1+2n2+3n3/分支数* 两式相减得nO=1+n2+2n3=1+3+2x4=12(12) 三、单项选择 1、①2、③3、④4、④5、②6、④7 ④9、③10、① ll、④12、②13、④14、①15、②16、①17、②18、④19、①20、② 21、④22、③23、①24、②25、 ③27、③28、①29、②30、④ 31、④32、②33、②34、③35、 四、简答及应用题 1.二叉链表的类型定义如下: typedef struct btnode *bitreptr; struct btnode( datatype data; bi bitreptr root 其中,data域称为数据域,用于存储二叉树结点中的数据元素; Child域称为左孩子指 针域,用于存放指向本结点左孩子的指针(简称左指针)。 rchild域称为右孩子指针域,用 于存放指向本结点右孩子的指针(简称右指针)。 2.三叉链表与二叉链表的主要区别在于,它的结点比二叉链表的结点多一个指针域 该域用于存储一指向本结点双亲的指针。三叉链表的类型定义如下: typedef struct ttnode *ttnodeptr struct ttnode tnodeptr Child, rchild, parent ttnodeptr root 3. typedef struct tagnode /*表结点类型* 2

2 38、 n-2m+1 39、 5、答案见图 A B A C C B A C C B A C B A B 40、 WPL＝165 62 37 25 19 18 13 12 10 9 7 6 5 4 41、m-1 42、本题有一定的难度，其求解方法如下：设总结点数为 n 度为 0、1、2、3 的结点数分别 为 n0,n1,n3,则有下面两个等式成立： n=n0+n1+n2+n3 /*结点数*/ n-1=n1+2n2+3n3 /*分支数*/ 两式相减得 n0=1+n2+2n3=1+3+2x4=12 (12) 三、单项选择 1、①2、③3、④4、④5、②6、④7、③8、④9、③10、① 11、④12、②13、④14、①15、②16、①17、②18、④19、①20、② 21、④22、③23、①24、②25、②26、③27、③28、①29、②30、④ 31、④32、②33、②34、③35、①36、③37、③ 四、简答及应用题 1． 二叉链表的类型定义如下： typedef struct btnode *bitreptr; struct btnode{ datatype data; bitreptr lchild,rehild; } bitreptr root; 其中，data 域称为数据域，用于存储二叉树结点中的数据元素；lchild 域称为左孩子指 针域，用于存放指向本结点左孩子的指针（简称左指针）。rchild 域称为右孩子指针域，用 于存放指向本结点右孩子的指针（简称右指针）。 2．三叉链表与二叉链表的主要区别在于，它的结点比二叉链表的结点多一个指针域， 该域用于存储一指向本结点双亲的指针。三叉链表的类型定义如下： typedef struct ttnode *ttnodeptr; struct ttnode {datatype data; ttnodeptr lchild, rchild, parent; } ttnodeptr root; 3．typedef struct tagnode /*表结点类型*/

fint child /*孩子结点在表头数据组中的序号* ode *next 表结点指针域 def struct /头结点类型* /*结点数据元素* link headpt /*头结点指针域* i headnode typedef headnode childlink[anode;表头结点数组 带双亲的孩子链表表示法,其类型定义与孩子链表类似,只需将头结点的定义改为: typedef struct i datatype data 4.就图简答题4.1(a)中的二叉树 (1)根结点是A (2)叶结点是:D,F,J (3)G的双亲是:E (4)G的祖先是:A: (5)G的孩子是:H; (6)E的子孙是:F,G,H,I,J; (7E的兄弟是:B:C的兄弟是:C无兄弟;(8)结点B和I的层数分别是2,5; (9)树的深度是:6; 0以结点G为根的子树的深度是:4 0D树的度数是:2。 就图简答题4.1(b)中的树 (1)根结点是A (2)叶结点是:D,F,G,H,I,J 3G的双亲是:C (4)G的祖先是:A (5)G的孩子是:G无孩子; (6)E的子孙是:H,I,J (7)E的兄弟是:D:C的兄弟是:B;(8)结点B和I的层数分别是2,4 (9)树的深度是:4 0以结点G为根的子树的深度是:1 0D树的度数是:3。 5.(a)因为该图所示结构,有两个结点没有直接前趋,即有两个根结点,而树只能有 个根结点 (b)因为找不到树的根结点,所以不满足树的定义 (c)因为最上面一个结点的后继结点分不出两个不相交的子集,不满足树的定义。 6.答案见图简答题6所示。 7.答案见图简答题7-2所示 8.先根序列: ABCDEFGHIJ; 中根序列: BCDAFEHJIG; 后根序列: DCBFJIHGEA 9.(1)二叉树中任意一个结点都无左孩子; (2)二叉树中任意一个结点都无右孩子; (3)至多只有一个结点的二叉树 10.由后根遍历序列得到二叉树的根结点A(后根序列中最后一个结点):在中序序列中, A的左力是A的左子树上的结点,A的右边是A的右子树上的结点:再到后根序列中找左子

3 {int child; /*孩子结点在表头数据组中的序号*/ struct tagnode *next; /*表结点指针域*/ }node,*link; typedef struct /*头结点类型*/ {datatype data; /*结点数据元素*/ link headptr; /*头结点指针域*/ }headnode; typedef headnode childlink[axnode]; /*表头结点数组*/ 带双亲的孩子链表表示法，其类型定义与孩子链表类似，只需将头结点的定义改为： typedef struct {datatype data; int parent; link headptr; }headnodel; 4．就图简答题 4.1（a）中的二叉树 ⑴根结点是 A； ⑵叶结点是：D，F，J； ⑶G 的双亲是：E； ⑷G 的祖先是：A； ⑸G 的孩子是：H； ⑹E 的子孙是：F，G，H，I，J； ⑺E 的兄弟是：B；C 的兄弟是：C 无兄弟；⑻结点 B 和 I 的层数分别是 2，5； ⑼树的深度是：6； ⑽以结点 G 为根的子树的深度是：4； ⑾树的度数是：2。 就图简答题 4.1(b)中的树 ⑴根结点是 A； ⑵叶结点是：D，F，G，H，I，J； ⑶G 的双亲是：C； ⑷G 的祖先是：A； ⑸G 的孩子是：G 无孩子； ⑹E 的子孙是：H，I，J； ⑺E 的兄弟是：D；C 的兄弟是：B； ⑻结点 B 和 I 的层数分别是 2，4； ⑼树的深度是：4； ⑽以结点 G 为根的子树的深度是：1； ⑾树的度数是：3。 5．(a)因为该图所示结构，有两个结点没有直接前趋，即有两个根结点，而树只能有一 个根结点。 (b)因为找不到树的根结点，所以不满足树的定义。 (c)因为最上面一个结点的后继结点分不出两个不相交的子集，不满足树的定义。 6．答案见图简答题 6 所示。 7．答案见图简答题 7-2 所示。 8．先根序列：A B C D E F G H I J; 中根序列：B C D A F E H J I G; 后根序列：D C B F J I H G E A。 9．⑴二叉树中任意一个结点都无左孩子； ⑵二叉树中任意一个结点都无右孩子； ⑶至多只有一个结点的二叉树。 10．由后根遍历序列得到二叉树的根结点 A（后根序列中最后一个结点）；在中序序列中， A 的左力是 A 的左子树上的结点，A 的右边是 A 的右子树上的结点；再到后根序列中找左子

树和右子树的根结点,依次类推,直到画出该二叉树,如图简答题10所示。 11.答案见图简答题11-2所示。 12.先根序列:ABE C GDHIJ 后根序列: EKLFBGCHIJDA: 层次序列: A BCDEFGHIJKL。 13.答案见图简答题13-2所示 14.答案见图简答题14-2所示 (a)(b)(c)(d)(e) 15.答案见图简答题15-1所示 16.利用先根遍历方法查找结点*A的直接后继 当A- lchild<>NUL时,A的先根后继结点是A-> Child:否则,当A-> rchild<NULL 时,A的先根后继结点是A-> rchild 16.利用先根遍历方法查找结点*A的直接后继: 当A- Child<>NUL时,A的先根后继结点是A-> lchild:否则,当A-> rchild<>NULL 时,A的先根后继结点是A- rchild 利用中根遍历方法查找结点*A的直接后继: 当A-> Child<>NUL时,*A的中根前趋是其左子树的“最右下结点 A-> rchild<NULL时,*A的中根后继是其右子树的“最左下结点”。 利用后根遍历方法查找结点*A的直接前趋 当 A->rchild<NUL时,A的后根前趋结点是 A->rchild:否则,A-> rchild<>NULL时 A的后根前趋结点是A-> Child; 17.本题的解题过程如下: ①由前根序列各A是二叉树的根结点:由中根序列知 GDHBE是A的左子树中的结点,CIJF 是A的右子树中的结点。 ②由前根序列知B是A的左子树的根结点;由中根序列知GDH是B的左子树中的结点 E是B的右子树中的结点 ③由前根序列知D是B的左子树的根结点;由中根序列知G是B的左子树中的结点,H 是B的右子树中的结点 ④由前根序列知C是A的右子树的根结点;由中根序列知IJF是C的右子树中的结点(C 的左子树为空)。 ⑤由前根序列知F是C的右子树的根结点;由中根序列知IJ是F的左子树中的结点,(F 的右子树为空)。 ⑥由前根序列知I是F的左子树的根结点:由中根序列知J是F的右子树中的结点,(F 的左子树为空)。 完整的二叉树如图简答题17所示 18.第一步,先以给定的权值构造出哈夫曼树,如图简答题18所示。 第二步,假没规定哈夫曼树上所有的左指针用0表示,所有的右指针用1表示

4 树和右子树的根结点，依次类推，直到画出该二叉树，如图简答题 10 所示。 11．答案见图简答题 11-2 所示。 12．先根序列：A B E F K L C G D H I J； 后根序列：E K L F B G C H I J D A； 层次序列：A B C D E F G H I J K L。 13．答案见图简答题 13-2 所示。 14．答案见图简答题 14-2 所示。 (a)(b)(c)(d)(e) 15.答案见图简答题 15-1 所示。 16．利用先根遍历方法查找结点*A 的直接后继： 当 A->lchild<>NULL 时，A 的先根后继结点是 A->lchild；否则，当 A->rchild<>NULL 时，A 的先根后继结点是 A->rchild。 16．利用先根遍历方法查找结点*A 的直接后继： 当 A->lchild<>NULL 时，A 的先根后继结点是 A->lchild；否则，当 A->rchild<>NULL 时，A 的先根后继结点是 A->rchild。 利用中根遍历方法查找结点*A 的直接后继： 当 A->lchild<>NULL 时 ， *A 的 中 根 前趋 是 其左 子 树 的“ 最 右下 结 点 ”； 当 A->rchild<>NULL 时，*A 的中根后继是其右子树的“最左下结点”。 利用后根遍历方法查找结点*A 的直接前趋： 当 A->rchild<>NULL 时，A 的后根前趋结点是 A->rchild；否则，A->rchild<>NULL 时， A 的后根前趋结点是 A->lchild； 17．本题的解题过程如下： ①由前根序列各 A 是二叉树的根结点；由中根序列知 GDHBE 是 A 的左子树中的结点，CIJF 是 A 的右子树中的结点。 ②由前根序列知 B 是 A 的左子树的根结点；由中根序列知 GDH 是 B 的左子树中的结点， E 是 B 的右子树中的结点。 ③由前根序列知 D 是 B 的左子树的根结点；由中根序列知 G 是 B 的左子树中的结点，H 是 B 的右子树中的结点 ④由前根序列知 C 是 A 的右子树的根结点；由中根序列知 IJF 是 C 的右子树中的结点（C 的左子树为空）。 ⑤由前根序列知 F 是 C 的右子树的根结点；由中根序列知 IJ 是 F 的左子树中的结点，（F 的右子树为空）。 ⑥由前根序列知 I 是 F 的左子树的根结点；由中根序列知 J 是 F 的右子树中的结点，（F 的左子树为空）。 完整的二叉树如图简答题 17 所示。 18．第一步，先以给定的权值构造出哈夫曼树，如图简答题 18 所示。 第二步，假没规定哈夫曼树上所有的左指针用 0 表示，所有的右指针用 1 表示

第三步,从根开始沿每一条通向叶子的路径上的数字,这些数字就是对应叶子结点所代 表的字母的哈夫曼编码。8个字母所应的哈夫曼编码为 7-0010 19---10 2-000006-0001 3-00001 10--0011 图简答题18 19.仼意一棵二叉树只有先转换成完全二叉树后,才能用顺序存储结构进行存储。转换 后的二叉树如图19-2所示。任意二叉树的顺序存储结构示意图如图19-3所示 图简答题192 图简答题193 20.转换后的二叉树如图简答题20-2所示。 图简答题202 五、算法设计 1.(1) bitreptr PARENT(bitreptr BT, bitreptr p, datatype data)/*调用前p为空指针*/ if(BT!=NULL)if(BT->data=X) return(p);/*找到,返回其父结点*/ else p=bt: PARENT(BT->Child, p, X) /*查找其左子树* PARENT(BT->rchild, p, X) /*查找其右子树*/ (2)void CREATE(datatype X, bitreptr LBT, bitreptr RBT) I BT=malloc(size) /*申请根结点*/ BT->data=x: BT->lchild=LBT: BT->rchild=RBI (3)void DELLEFT(bitreptr BT, datatype X if (BT!=null )if(BT->data =X) BT->lchild=null, BT->rchild=null else( DELLEFT(BT->lchild, X); DELLEFT(BT->rchild, X) 2. (1)ttnodeptr PARENT(ttndoeptr BT, datatype data) if(BT!= null) if(BI->data=X) return(BI-> patent);/找到,返回其父结点* else ( PARENT (BT->lchild, X), PARENT(BT->rchild, X); (2)void CREATE(datatype X, ttnodeptr LBT, ttnodeper RBT ( BT-malloc(size) /*申请根结点 BT->data=x: BT->lchild=LBT: BT->rchild=RBI LBT->parent= BT;R BT->parent=BT

5 第三步，从根开始沿每一条通向叶子的路径上的数字，这些数字就是对应叶子结点所代 表的字母的哈夫曼编码。8 个字母所应的哈夫曼编码为： 7---0010 19---10 2---00000 6---0001 32---01 3---00001 21---11 10---0011 图简答题 18 19．任意一棵二叉树只有先转换成完全二叉树后，才能用顺序存储结构进行存储。转换 后的二叉树如图 19-2 所示。任意二叉树的顺序存储结构示意图如图 19-3 所示。 图简答题 19-2 A B C D E F G …… 图简答题 19-3 20．转换后的二叉树如图简答题 20-2 所示。 图简答题 20-2 五、算法设计 1．⑴bitreptr PARENT(bitreptr BT, bitreptr p, datatype data) /*调用前 p 为空指针*/ {if(BT!=NULL)if(BT->data==X) return(p); /*找到,返回其父结点*/ else{p=BT; PARENT(BT->lchild, p, X); /*查找其左子树*/ PARENT(BT->rchild, p, X); /*查找其右子树*/ } } ⑵void CREATE(datatype X, bitreptr LBT, bitreptr RBT) { BT=malloc(size); /*申请根结点*/ BT->data=x;BT->lchild=LBT; BT->rchild=RBT; } (3)void DELLEFT(bitreptr BT,datatype X) {if (BT!=null ) if (BT->data = X) {BT->lchild=null,BT->rchild=null;} else{DELLEFT(BT->lchild,X); DELLEFT(BT->rchild,X);} } 2.(1) ttnodeptr PARENT(ttndoeptr BT, datatype data) { if (BT!=null) if (BT->data = X) return (BT->patrnt); /*找到，返回其父结点*/ else {PARENT (BT->lchild,X);PARENT(BT->rchild,X);} } (2) void CREATE(datatype X, ttnodeptr LBT, ttnodeper RBT) {BT=malloc(size); /*申请根结点*/ BT->data=x; BT->lchild=LBT; BT->rchild=RBT; LBT->parent = BT; R BT->parent = BT;