第六章参考答案 、名词解释(略) 、填空题 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 rchild 16.利用先根遍历方法查找结点*A的直接后继: 当A- Child<>NUL时,A的先根后继结点是A-> lchild:否则,当A-> rchild<>NULL 时,A的先根后继结点是A- rchild 利用中根遍历方法查找结点*A的直接后继: 当A-> Child<>NUL时,*A的中根前趋是其左子树的“最右下结点 A-> rchildrchildrchild:否则,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;
(3)void DELLEFT(ttnodeptr BT, datatype X) if (BT!=null)if (BT->data == Child =null; BT->rchild=null; i else DELLEFT(BT->lchild, X); DELLEFT(BT->rchild, X): 1 3采用递归方法,对每一个结点先求其左右子树的深度,取较大值加1作为此结点的 深度。 Int depth(bitreptr BT fif (BT==null)return (0) else (I=heth(BT->lchild); r=heth(BT->rchild return((b>?l r)+1) 4按照题目要求,附加一个工作栈以完成对该树的非递归遍历,思路如下: 每访问一个结点,将此结点压入栈,查看此结点是否有左子树,若有, 访问左子树,转(1)执行。 (2) 从栈弹出一结点,如果此结点有右子树,访问右子树并转第(1)步 执行,否则转第(2)步执行。 Void preorder( datatype a[n], int n f INISTACK(sd) /*初始工作栈sd*/ 1=1; PUSH(sd,O) If(data==t2->data) /*t1和t2的值相等*
6 } (3)void DELLEFT(ttnodeptr 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);} } 3.采用递归方法，对每一个结点先求其左右子树的深度，取较大值加 1 作为此结点的 深度。 Int depth (bitreptr BT) {if (BT= =null)return（0); else {l=hepth (BT->lchild); r=hepth(BT->rchild); return((l>r?l:r)+1); } 4.按照题目要求，附加一个工作栈以完成对该树的非递归遍历，思路如下： （1） 每访问一个结点，将此结点压入栈，查看此结点是否有左子树，若有， 访问左子树，转（1）执行。 （2） 从栈弹出一结点，如果此结点有右子树，访问右子树并转第（1）步 执行，否则转第（2）步执行。 Void preorder(datatype a[n],int n ) { INISTACK(sd); /*初始工作栈 sd*/ I=1; PUSH(sd,0); If (idata = =t2->data) /*t1 和 t2 的值相等*/
Return(same tree(tl->lchild, t2->lchild)&& Same tree(tl->rchild, t2->rchild)) 6采用后根遍历递归访问的方法,交换每一个结点的左右子树 Void exch tree(bitreptr BT) fif (BTI=null) /*非空* exch tree(BT>lhid),/交换左子树所有结点指针*/ exch tree(BT-> rchild),/交换右子树所有结点指针* p=BT->lchild 倖交换根结点左右指针 BT->lchild=BT->rchild;->rchild=p; 7设置一个栈用于装入查找结点的所有祖先 栈的元素结构说明如下 typedef struct ( bitreptr p: Int tag, i snode int search(bitreptr T, datatype X) t top=0 /栈s初置为0* while((Ti=null)&&(T->datal=X)ll(topl=0)) fwhile(((Ti=null)&&(T->data!=X)) t top ++ stop -p=t; stop .tag=0 /*结点入栈,置标志0*/ T=T->lchild /找左子树* if(((T =null)&&(T->data==X)) /*找到* i for(I=1; K0)&&(s[op]tag=1)top-;/*退出右子树已访问过的结点* if(top>0){s[top]tag=1,T=s{top];T=T> schild;/*置访问标志为1,访问右子树* return(0); 8.(1) PARENTO(TX)的功能是查找值为X的结点的双亲。查找的方法是,在表头数组中 依次顺序查看每个头结点的链域,查找是否含水量有值为X的结点,如有,则返回其结点 的值 Headnode parent( headnode 1, datatype X)/*n表示树的结点数*/ f(Tk]data=X) return(nu),/*根结点值是X返回空值*/
7 Return (same_tree (t1->lchild, t2->lchild)&& Same_tree(t1->rchild,t2->rchild)); } 6.采用后根遍历递归访问的方法，交换每一个结点的左右子树。 Void exchg_tree(bitreptr BT) {if (BT!=null) /*非空*/ {exchg_tree(BT->lchild); /*交换左子树所有结点指针*/ exchg_tree(BT->rchild); /*交换右子树所有结点指针*/ p=BT->lchild; /*交换根结点左右指针*/ BT->lchild=BT->rchild; ->rchild =p; } } 7.设置一个栈用于装入查找结点的所有祖先。 栈的元素结构说明如下： typedef struct {bitreptr p; int tag; }snode; int search(bitreptr T,datatype X) {top =0; /*栈 s 初置为 0*/ while ((T!=null)&&(T->data!=X)||(top!=0)) {while (((T!=null)&&(T->data!=X)) {top ++; s[top ].p=T; s[top].tag=0; /*结点入栈，置标志 0*/ T=T->lchild; /*找左子树*/ } if (((T!=null)&&(T->data==X)) /*找到*/ {for (I=1;Idata); /*输出*/ return(1); } else while ((top>0)&&(s[top].tag==1)) top --; /*退出右子树已访问过的结点*/ if (top>0){s[top].tag=1;T=s[top]; T=T->rchild;/*置访问标志为 1，访问右子树*/ } } return(0); } 8. （1） PARENT(T,X)的功能是查找值为 X 的结点的双亲。查找的方法是，在表头数组中 依次顺序查看每个头结点的链域，查找是否含水量有值为 X 的结点，如有，则返回其结点 的值。 Headnode parent (headnode T,datatype X ) /*n 表示树的结点数*／ {k=0; if (T[k].data= =X) return(null); ／*根结点值是Ｘ返回空值*／ while (k<n)
ip=k]. headptr /*取子树指针* while(p!=nul d=p->child; /*取孩子序号* if( ro data==X) return(Tk]),/*查找到X,返回父结点* /*取下一个孩子 return(null) /没有找到,返回空值* (2)HILD(T,Ⅹ,D)的功能是在树T中查找值为X的结点的第I个孩子。算法思路是: 先在表头结点中查找值为X的结点,然后再由此结点的链表找第I个孩子,如找到则返回 这个孩子的指针值 Headnode child( headnode T, datatype X, int D) k=0, whle(knext;};/*查找第I个孩子 f(p!= null)&&(=I) return(p)/找到第I个孩子* else return(null) /*没找到,返回定指针* else return(null) /没有找到结点X (3) DELETE(TXD)的功能是删除值为X的结点的第I个孩子。算法思路是:先在表头数组中 查找值为Ⅹ的结点。找到后再沿此结点的链表查找第I个孩子,如存在将其删除。 Void delete(headnode T, datatype X, int D) while(knext;}/*查第I个孩子* if ((p! null)&&(==l) /*找到第I个孩子* ft=p->child; q->next=p->next free(p) 删除第I个孩子结点* while(t<n iTt=Tt+ll t++: i else printf(“x没有第I棵子树”) else printf(T中不存在结点X"); 9.(1)用孩子兄弟链表为存储结构,实现 PARENT(T,Ⅹ)运算。 本题算法的思路是:①当根结点非空进栈:②当栈非空p=pop(s)(退栈操作),取元素p的 左子树T:③当T非空且值为X,返回双亲P。否则,若T非空,让T进栈,T取它的右子树
8 {p=T[k].headptr; /*取子树指针*/ while (p!=null) {j=p->child; /*取孩子序号*/ if (T[j].data= =X) return(T[k]); /*查找到 X，返回父结点*/ p=p->next; /*取下一个孩子*/ } k++; } return(null); /*没有找到，返回空值*/ } （2）HILD（T，X，I）的功能是在树 T 中查找值为 X 的结点的第 I 个孩子。算法思路是： 先在表头结点中查找值为 X 的结点，然后再由此结点的链表找第 I 个孩子，如找到则返回 这个孩子的指针值。 Headnode child(headnode T,datatype X,int I) {k=0; while ((knext;};/*查找第 I 个孩子*/ if ((p!=null)&&(j= =I)) return(p); /*找到第 I 个孩子*/ else return(null); /*没找到，返回定指针*/ } else return(null); /*没有找到结点 X*/ } (3) DELETE(T,X,I)的功能是删除值为 X 的结点的第 I 个孩子。算法思路是：先在表头数组中 查找值为 X 的结点。找到后再沿此结点的链表查找第 I 个孩子，如存在将其删除。 Void delete (headnode T,datatype X,int I) {k=0; while ((knext;} /*查第 I 个孩子*/ if ((p!null)&&(j==I)) /*找到第 I 个孩子*/ {t=p->child; q->next=p->next;free(p); /*删除第 I 个孩子结点*/ while(t<n){T[t]=T[t+1];t++;} } else printf(“X 没有第 I 棵子树”)； } else printf(“T 中不存在结点 X”)； } 9．（1）用孩子兄弟链表为存储结构，实现 PARENT（T，X）运算。 本题算法的思路是：①当根结点非空进栈；②当栈非空 p=pop(s)(退栈操作)，取元素 p 的 左子树 T；③当 T 非空且值为 X，返回双亲 P。否则，若 T 非空，让 T 进栈，T 取它的右子树
转③执行:④转②执行。 本题用到栈S存放查找到的每一个结点,栈中元素结构说明如下: typedef struct bitreptr p: )s[max size bitreptr Parent (bitreptr t, datatype X) Itop =1; s[top] p=T /*若头结点非空,进栈* while((T!=null)II(top>0)) p=s[top].p;topj--;T=p- rchild;/*退栈*/ while(( t->data!=)&&(T-rchild!=null)) (top++s[top] p=T: T=T->rchild: K /*若此结点值不为X,查找其兄弟域*/ if(T!=mul1)&&(T->data==X) re turn(p);/找到返回其双亲结点*/ return(null) (2)用孩子兄弟链表为存储结构,实现CHLD(T,X,I)运算。 算法CHLD(T,Ⅹ,Ⅰ)的功能是查找结点Ⅹ的第I个孩子。本算法在查找结点Ⅹ时,同 (1)基本思路相仿,只在找到结点X时,再查找它是否有第I个孩子 Bitreptr CHILD( bitreptr T, datatype X,int)/*用的栈S同(1)* fif (Ti=null) t top=l; stop -p=T /若头结点非空,进栈* while((T=null )Il(top >0)) fwhhile((TI=null )&&(T->data=X)) {top++;s{top]p=T,T=T> Child}/若此结点值不为X,查找其左子树*/ if ((TI=null)&&(T->data==X)) d =0; p=T->lchild *找到结点Ⅹ,查找第I个孩子* while(pl=null)&&(rchild if ==D)return(p) /*找到返回结点*p else return(null) /*没有找到返回空指针* while( (top>0)&&(stop -p->rchild==null)) top if(top>O)(T=s[top]-p->rchild top--i i return(null) (3)用孩子兄弟链表为存储结构,现实 DELETE(T,X,D)的运算。 Void DELETE(bitreptr T, datatype X, int D) {top=1;stop]p=T,/*若头结点非空,进栈* while((Ti=null)lI(top>o)) f while((TI=null)&&(T-datal=X))(top++ s[top)-p=T; T=T->lchild f(t->data==X)/*找到结点*
9 转③执行；④转②执行。 本题用到栈 S 存放查找到的每一个结点，栈中元素结构说明如下： typedef struct {bitreptr p;}s[max_size]; bitreptr PARENT(bitreptr T,datatype X) { if (t!=null) {top =1; s[top].p=T; /*若头结点非空，进栈*/ while ((T!=null)||(top>0)) {p=s[top].p;topj--; T=p->rchild；/*退栈*/ while ((T->data!=X)&&(T->rchild!=null)) {top++;s[top].p=T; T=T->rchild;} /*若此结点值不为 X，查找其兄弟域*/ if ((T!=null)&&(T->data= =X))return(p) ;/*找到返回其双亲结点*/ } } return(null); } (2)用孩子兄弟链表为存储结构，实现 CHILD（T，X，I）运算。 算法 CHILD（T，X，I）的功能是查找结点 X 的第 I 个孩子。本算法在查找结点 X 时，同 （1）基本思路相仿，只在找到结点 X 时，再查找它是否有第 I 个孩子。 Bitreptr CHILD(bitreptr T,datatype X,int I ) /*用的栈 S 同（1）*/ {if (T!=null) {top =1; s[top].p =T; /*若头结点非空，进栈*/ while ((T!=null )||(top >0)) {whhile ((T!=null )&&(T->data==X)) {top ++; s[top].p=T; T=T->lchild } /*若此结点值不为 X，查找其左子树*/ if ((T!=null)&&(T->data= =X)) {j=0; p=T->lchild ; /*找到结点 X，查找第 I 个孩子*/ while ((p!=null)&&(jrchild;} if (j= =I) return(p); /*找到返回结点*p*/ else return(null); /*没有找到返回空指针*/ } while ((top>0)&&(s[top].p->rchild= =null)) top--; if (top>0){T=s[top].p->rchild ;top--;} } }return(null); } (3) 用孩子兄弟链表为存储结构，现实 DELETE（T，X，I）的运算。 Void DELETE(bitreptr T,datatype X,int I) {if (T!=null) {top=1; s[top].p=T; /*若头结点非空，进栈*/ while((T!=null)||(top>0)) {while ((T!=null)&&(T->data!=X)){top++;s[top].p=T; T=T->lchild;} if (t->data= =X) /*找到结点*/
{j=o,p=T- Child;/*查找第I个孩子* while((p!=null)&&(rchild if((p!=nul&&(==) T> rchild=p-> achild;fre(p);}/找到第I个孩子删除 else printf(“没有找到第I个孩子”) return while((top>0)&&(T->rchild!=null))top if(top>O)IT=s[top]. rchild; top-- printf(“没有找到结点X返回”) (4)用静态双亲链表为存储结构,实现 PARENT(T,X)运算 静态双亲链表的类型定义如下 #define size typedef struct { datatype data;/*数据域* Int parent;/*双亲域(静态指针域)* typedef node t[size];/静态双亲链表*/ node parent( node TU, datatype X)/*n表示树的结点数* hile(k=0)return(null); else{ printf(“x在根结点”, return(null);} else k++, printf((找不到Z结点”!); return(nul) (5)用静态双亲链表为存储结构,实现CHLD(T,X,I)运算。 算法 CHILD(T,X,D)的功能是查找结点Ⅹ的第I个孩子。本算法在查找结点Ⅹ时,同 (4)基本思路相仿,只在找到结点X时,再查找它是否有第I个孩子。 Node CHIld(node T[, datatypeX, int D) k while(k- if (t[k] data==X) j=0,h=k, while(++k<n if(T(k -parent=h)if(==l)return(T(kD) else j++: printf((“找不到X结点的第I个孩子!”), return(null felse k++
10 {j=o; p=T->lchild; /*查找第 I 个孩子*/ while ((p!=null)&&(jrchild;} if ((p!=null)&&(j= =I) {T->rchild =p->rchild ;free(p);} /*找到第 I 个孩子删除*/ else printf(“ 没有找到第 I 个孩子”)； return; } while((top>0) &&(T->rchild!=null))top--; if (top>0){T=s[top].rchild;top--;} } printf(“没有找到结点 X 返回”)； } } （4）.用静态双亲链表为存储结构，实现 PARENT（T，X）运算。 静态双亲链表的类型定义如下： #define size typedef struct { datatype data; /*数据域*/ int parent; /*双亲域（静态指针域）*/ }node; typedef node T[size]; /*静态双亲链表*/ node PARENT(node T[],datatype X) /*n 表示树的结点数*/ {k=0; while (k=0) return (null); else {printf(“X 在根结点”); return(null);} else k++; printf (“找不到 Z 结点”!); return(null); } (5)用静态双亲链表为存储结构，实现 CHILD（T，X，I）运算。 算法 CHILD（T，X，I）的功能是查找结点 X 的第 I 个孩子。本算法在查找结点 X 时，同 （4）基本思路相仿，只在找到结点 X 时，再查找它是否有第 I 个孩子。 Node CHILD（node T[]，datatypeX，int I） {k=0; while (k<n) if (T[k].data= =X) {j=0;h=k; while (++k<n) if (T[k].parent= =h) if ((j= =I) return(T[k]); else j++; printf (“找不到 X 结点的第 I 个孩子！”); return(null); }else k++;