须先定义结点间相互关系的“左右”。本解答中将N是M的左子女,当作N在M的左边,而 N是M的右子女,当作N在M的右边。若定义P是M和N的最近公共祖先,N在P的左子树 中,M在P的右子树中,称N在M的左边,那时的答案是不一样的。 先根遍历时n先被访问中根遍历时n先被访问后根遍历时n先被访问 N在M的左边 N在M的右边 N是M的祖先 N是M的子 60. HIDJKEBLFGCA (D(EED (L 62.后序遍历的顺序是“左子树一右子树一根结点”。因此,二叉树最左下的叶子结点是遍 历的第一个结点。下面的语句段说明了这一过程(设p是二叉树根结点的指针)。 (p!=null) if(p Iwhile(p->lchild!=null I p->rchild!=null) Iwhile(p->lchild!=null)p=p->lchild if(p->rchild!=null)p=p->rchild return(p);//返回后序序列第一个结点的指针 63.采用前序和后序两个序列来判断二叉树上结点n1必定是结点n2的祖先 在前序序列中某结点的祖先都排在其前。若结点n1是n2的祖先,则n1必定在n2之前 而在后序序列中,某结点的祖先排在其后,即若结点n1是n2的祖先,则n必在n2之后 根据这条规则来判断若结点n1在前序序列中在n2之前,在后序序列中又在n2之后,则它 必是结点n2的祖先 64.(1) (2)前序序列: ABCEDFHGIJ(3)后序线索树 中序序列: ECBHFDJIGA 后序序列: ECHFJIGDBA )(y(9 65.最后一个递归调用语句所保留的参数没有意义。这类递归因其在算法最后,通常被称为 尾递归”,可不用栈且将其(递归)消除。如中序遍历递归算法中,最后的递归语句 norder(bt- rchild)可改为下列语句段 bt=bt->rchild while (bt->rchild!=null)
须先定义结点间相互关系的“左右”。本解答中将 N 是 M 的左子女，当作 N 在 M 的左边，而 N 是 M 的右子女，当作 N 在 M 的右边。若定义 P 是 M 和 N 的最近公共祖先，N 在 P 的左子树 中，M 在 P 的右子树中，称 N 在 M 的左边，那时的答案是不一样的。 60．HIDJKEBLFGCA 61． 62．后序遍历的顺序是“左子树—右子树—根结点”。因此，二叉树最左下的叶子结点是遍 历的第一个结点。下面的语句段说明了这一过程（设 p 是二叉树根结点的指针）。 if(p!=null) {while (p->lchild!=null || p->rchild!=null) {while(p->lchild!=null) p=p->lchild; if(p->rchild!=null) p=p->rchild; } } return(p); //返回后序序列第一个结点的指针； 63. 采用前序和后序两个序列来判断二叉树上结点 n1 必定是结点 n2 的祖先。 在前序序列中某结点的祖先都排在其前。若结点 n1 是 n2 的祖先,则 n1 必定在 n2 之前。 而在后序序列中，某结点的祖先排在其后，即若结点 n1 是 n2 的祖先，则 n1 必在 n2 之后。 根据这条规则来判断若结点 n1 在前序序列中在 n2 之前，在后序序列中又在 n2 之后，则它 必是结点 n2 的祖先。 64.(1) （2） 前序序列：ABCEDFHGIJ （3）后序线索树 中序序列：ECBHFDJIGA 后序序列：ECHFJIGDBA 65. 最后一个递归调用语句所保留的参数没有意义。这类递归因其在算法最后，通常被称为 “尾递归”， 可不用栈且将其（递归）消除。 如中序遍历递归算法中，最后的递归语句 inorder (bt->rchild)可改为下列语句段： bt=bt->rchild; while (bt->rchild!=null) 先根遍历时 n 先被访问 中根遍历时 n 先被访问 后根遍历时 n 先被访问 N 在 M 的左边 N 在 M 的右边 N 是 M 的祖先 N 是 M 的子孙 I C A B G D E F J K L H A B C D E F G H I J B A C E D F G H I J null null
inorder(bt-> Child); printf(“%c”,bt->data);//访问根结点,假定结点数据域为 字符 bt=bt ->rchild: I 66.在二叉链表表示的二叉树中,引入线索的目的主要是便于查找结点的前驱和后继。因为 若知道各结点的后继,二叉树的遍历就变成非常简单。二叉链表结构查结点的左右子女非常 方便,但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列, 利用结点的空链域,左链为空时用作前驱指针,右链为空时作为后继指针。再引入左右标记 ltag和rtag,规定ltag=0, lchild指向左子女,ltag=1时, Child指向前驱;当rtag=0 时, rchild指向右子女,rtag=1时, rchild指向后继。这样,在线索二叉树(特别是中序 线索二叉树)上遍历就消除了递归,也不使用栈(后序线索二叉树查后继仍需 要栈。) (L 67题(2 (3)后根遍历森林,结点序列为 BDCAIFJGHELOPMNK 67题(1) 68.(1)前序序列: ABDEHCFG (2)中序序列: DHEBAFCG (3)后序序列: HEDBFGCA 69.(1) ①(D G八(H)(D
{inorder (bt ->lchild); printf(“%c”,bt ->data);//访问根结点，假定结点数据域为 字符 bt=bt ->rchild; } 66.在二叉链表表示的二叉树中， 引入线索的目的主要是便于查找结点的前驱和后继。因为 若知道各结点的后继，二叉树的遍历就变成非常简单。二叉链表结构查结点的左右子女非常 方便，但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列， 利用结点的空链域，左链为空时用作前驱指针，右链为空时作为后继指针。再引入左右标记 ltag 和 rtag ，规定 ltag=0，lchild 指向左子女,ltag=1 时,lchild 指向前驱；当 rtag=0 时 ,rchild 指向右子女，rtag=1 时，rchild 指向后继。这样，在线索二叉树（特别是中序 线索二叉树）上遍历就消除了递归，也不使用栈（后序线索二叉树查后继仍需 要栈。） 67. 67 题(1) 68. （1）前序序列：ABDEHCFG （2）中序序列：DHEBAFCG （3）后序序列：HEDBFGCA 69.（1） 67 题(2) M K L N O P I G E F H J (3)后根遍历森林，结点序列为: BDCAIFJGHELOPMNK C A B D A B E C F D K I G L J H M O N P A B C D F G E H null null A B F C G H D E I J L K A B F C G H D E I J L K null
(2) Bitree InOrder- PRIOR(N,X)//在中序线索二叉树上查找结点N的前驱结点X lif(n->ltag==1)(X=N->lchild; return(X): else ip=N->lchild: while (p->rtag==0) p=p->rchild X=p return(p): I G 70题(3) 70题(1) 70题(2) 前序序列: ABCEDFHG IJ 中序序列: ECBHFDJIGA 后序序列: ECHFJIGDBA 71题(2) 71题(3) 72.后序线索树中结点的后继,要么是其右线索(当结点的rtag=1时),要么是其双亲结点 右子树中最左下的叶子结点。所以,只有当二叉树只有根或树中任一结点均无右子树时,进 行遍历才不用栈,其遍历程序段如下: while(p-1tag==0)p==p- Child;//找最左下叶子结点 while( p->rchild!=null) visit(p>data);/访问结点; p=p-> rchild;}/沿线索向上 对前序线索二叉树,当二叉树非空时,若其结点有左子女(ltag=0),左子女是后继 否则,若结点有右子女(rtag=0),则右子女是后继;若无右子女(rtag=1),右子女是线索, 也指向后继。所以,对任何前序线索二叉树进行前序遍历均不需使用栈 3.左右子树均不空的二叉树先序线索化后,空指针域为1个(最后访问结点的右链为空)。 74.if(p->1tag=0) return(p- lchild);//左子女不空,左子女为直接后继结点 else return(p->rchild) /左子女空,右子女(或右线索)为后继 75.后序线索树中结点的后继(根结点无后继),要么是其右线索(当结点的rtag=1时), 要么是其双亲结点右子树中最左下的叶子结点。对中序线索二叉树某结点,若其左标记等于 1,则左子女为线索,指向直接前驱;否则,其前驱是其左子树上按中序遍历的最后一个结点 76.树的后根遍历(对应二叉树的中序遍历)全线索链表 DataA D
（2）BiTree INORDER-PRIOR(N,X) //在中序线索二叉树上查找结点 N 的前驱结点 X {if(n->ltag==1){X=N->lchild; return (X);} else {p=N->lchild; while (p->rtag==0) p=p->rchild; X=p;return(p);} } 70. 71. 71 题（3） 72. 后序线索树中结点的后继，要么是其右线索（当结点的 rtag=1 时），要么是其双亲结点 右子树中最左下的叶子结点。所以，只有当二叉树只有根或树中任一结点均无右子树时，进 行遍历才不用栈，其遍历程序段如下： while（p->ltag==0）p==p->lchild; //找最左下叶子结点 while（p->rchild!=null）{visit(p->data); //访问结点； p=p->rchild;} //沿线索向上 对前序线索二叉树，当二叉树非空时，若其结点有左子女（ltag=0），左子女是后继； 否则，若结点有右子女（rtag=0），则右子女是后继；若无右子女（rtag=1），右子女是线索， 也指向后继。所以，对任何前序线索二叉树进行前序遍历均不需使用栈。 73．左右子树均不空的二叉树先序线索化后，空指针域为 1 个（最后访问结点的右链为空）。 74．if(p->ltag==0) return(p->lchild);//左子女不空，左子女为直接后继结点 else return(p->rchild); //左子女空，右子女（或右线索）为后继 75. 后序线索树中结点的后继（根结点无后继），要么是其右线索（当结点的 rtag=1 时）， 要么是其双亲结点右子树中最左下的叶子结点。对中序线索二叉树某结点，若其左标记等于 1,则左子女为线索，指向直接前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。 76. 树的后根遍历（对应二叉树的中序遍历）全线索链表 Data A B C D E F G H I J K G B D A I F H E C 70 题（3） 前序序列：ＡＢＣＥＤＦＨＧＩJ 中序序列： E C B H F D J I G A 后序序列： ＥＣＨＦＪＩＧＤＢＡ 71 题（2） A G B D C E F H I 70题 （ 1） A G B D C E F H I 70题 （ 2） null null B A C E D F G H I J B A C E D F G H I J null null
0 Fch nul 0504 0806 9 Rtag|1 Nsib null 10 7题中序线索树 77题哈夫曼编码树 虽然哈夫曼树的带权路径长度是唯一的,但形态不唯一。本题中各字母编码如下: cl:0110c2:10c3:0010c4:011lc5:000c6:010c7:1lc8:0011 78.字符A,B,C,D出现的次数为9,1,5,3。其哈夫曼编码如下A:1,B:000,C:01,D:001 79.(2)wpl=(2+3)*5+6米4+(9+14+15)*3+(16+17)*2=229 78题哈夫曼编码树 79题(1) (3)编码为:15:111,3:10101,14:110,2:10100,6:1011,9:100,16:00,17:01 (4)常用哈夫曼树为通讯用的字符编码,本题中集合的数值解释为字符发生的频率(次数)。 由哈夫曼树构造出哈夫曼编码。译码时,进行编码的“匹配”,即从左往右扫描对方发来的 编码串”,用字符编码去匹配,得到原来的元素(本题中的数)。 80.首先确定是否需加“虚权值”(即权值为0),对m个权值,建k叉树,若(m1)%(k-1)=0, 则不需要加“虚权值”,否则,第一次归并时需(m-1)%(k-1)+1个权值归并。建立k叉树 的过程如下: (1)将m个权值看作m棵只有根结点的k叉树的集合F={T1,T2,…,Tm}。 (2)从F中选k(若需加虚权值,则第一次选(m-1)%(k-1)+1)个权值最小的树作子树, 构成一棵k叉树,k叉树根结点的权值为所选的k个树根结点权值之和,在F中
Ltag 0 1 0 0 0 1 0 1 1 1 1 Fch 2 null 5 7 8 5 11 2 8 9 3 Rtag 1 0 0 1 0 1 1 0 0 1 1 Nsib null 3 4 1 6 3 4 9 10 5 7 77. 虽然哈夫曼树的带权路径长度是唯一的，但形态不唯一。本题中各字母编码如下： c1:0110 c2:10 c3:0010 c4:0111 c5:000 c6:010 c7:11 c8:0011 78. 字符 A，B，C，D 出现的次数为 9,1,5,3。其哈夫曼编码如下 A:1，B:000，C:01，D:001 79．（2）wpl=(2+3)*5+6*4+(9+14+15)*3+(16+17)*2=229 (3) 编码为：15:111, 3:10101, 14:110, 2:10100, 6:1011, 9:100, 16:00, 17:01 (4) 常用哈夫曼树为通讯用的字符编码，本题中集合的数值解释为字符发生的频率（次数）。 由哈夫曼树构造出哈夫曼编码。译码时，进行编码的“匹配”，即从左往右扫描对方发来的 “编码串”，用字符编码去匹配，得到原来的元素（本题中的数）。 80．首先确定是否需加“虚权值”（即权值为 0）,对 m 个权值，建 k 叉树，若（m-1）%(k-1)=0, 则不需要加“虚权值”，否则，第一次归并时需（m-1）%(k-1)+1 个权值归并。建立 k 叉树 的过程如下： （1）将 m 个权值看作 m 棵只有根结点的 k 叉树的集合 F={T1，T2，…，Tm}。 （2）从 F 中选 k（若需加虚权值，则第一次选（m-1）%(k-1)+1）个权值最小的树作子树， 构成一棵 k 叉树，k 叉树根结点的权值为所选的 k 个树根结点权值之和，在 F 中 1 25 10 3 4 11 5 6 36 0 0 0 c5 c3 c8 c1 c4 c6 c7 c2 1 1 0 1 1 0 1 0 1 0 1 77题 哈 夫 曼 编 码 树 16 2 9 6 17 0 1 15 3 14 0 1 1 1 0 0 0 0 1 1 0 1 79题（1） B A J E C D G F H I null null 77题 中 序 线 索 树 1 3 5 9 0 0 0 1 1 1 78 题哈夫曼编码树 385 100 194 49 64 81 91 4 5 30 36 1 9 16 25
删除这k棵子树,并将新k叉树加入到F中 (3)从F中选k个权值最小的树作子树,构成一棵k叉树,其根 结点权值等于所选的k棵树根结点权值之和,在F中删除这k棵树 并将新得到的树加到F中 (4)重复(3),直到F中只有一棵树为止,这就是最优的k叉树 对本题10个权值,构造最优三叉树。 因(10-1)%(3-1)=1 所以第一次用2个权值合并 最小加权路径长度 (1+4)*4+(9+16)*3+(25+36+49+64+81)*2+100*1=705 字符 weight Paaeentllphchrphro 109081 态 图 123 ABC 012 终态图 p00d082.前缓码是一编码不是任何其它编码 4D490d0前级的编码。例如,0和01就不是前缀 5E 2 bs o oo 码,因为编码0是编码01的前缀。仅从 010 oo编码来看,0和01是前缀码,但因历史 11 011 的原因,它不被称为前缀码,而是把 59dd编码不是另一编码前缓的编码称为前级 11d4|d 码 15112030 利用二叉树可以构造前缀码,例如, 013 以A,B,C,D为叶子可构成二叉树,将 0 pd2d在分枝解释为0,右分枝解释成1,从根 结点到叶子结点的0、1串就是叶子的前 缀码。用哈夫曼树可构造出最优二叉树 使编码长度最短 83.哈夫曼树只有度为0的叶子结点和度为2的分枝结点,设数量分别为n0和n2,则树的 结点数n为n=n0+n2。另根据二叉树性质:任意二叉树中度为0的结点数n0和度为2的结 点数n2间的关系是n2=n0-1,代入上式,则n=n0+n2=2n0-1 84.(1)T树的最大深度Kmax=6(除根外,每层均是两个结点) T树的最小深度Kmin=4(具有6个叶子的完全二叉树是其中的一种形态 (2)非叶子结点数是5。(n2=n0-1)(3)哈夫曼树见下图,其带权路径长度wpl=51 84题图 85.(1)错误,循环结束条件top=0不能满足,因为在top>1情况下,执行top:=top-1 (2)错误(3)错误(4)正确(5)结点的深度与其右孩子深度相同,比左孩 子深度少1
删除这 k 棵子树，并将新 k 叉树加入到 F 中。 （3）从 F 中选 k 个权值最小的树作子树，构成一棵 k 叉树，其根 结点权值等于所选的 k 棵树根结点权值之和，在 F 中删除这 k 棵树， 并将新得到的树加到 F 中。 (4) 重复（3），直到 F 中只有一棵树为止，这就是最优的 k 叉树。 对本题 10 个权值，构造最优三叉树。 因（10-1）%(3-1)=1， 所以第一次用 2 个权值合并。 最小加权路径长度： （1+4）*4+(9+16)*3+(25+36+49+64+81)*2+100*1=705 81 ．初态图 终态图 82．前缀码是一编码不是任何其它编码 前缀的编码。例如，0 和 01 就不是前缀 码，因为编码 0 是编码 01 的前缀。仅从 编码来看，0 和 01 是前缀码，但因历史 的原因，它不被称为前缀码，而是把一 编码不是另一编码前缀的编码称为前缀 码。 利用二叉树可以构造前缀码，例如， 以 A，B，C，D 为叶子可构成二叉树，将 左分枝解释为 0，右分枝解释成 1，从根 结点到叶子结点的 0、1 串就是叶子的前 缀码。用哈夫曼树可构造出最优二叉树， 使编码长度最短。 83．哈夫曼树只有度为 0 的叶子结点和度为 2 的分枝结点，设数量分别为 n0 和 n2，则树的 结点数 n 为 n=n0+n2。 另根据二叉树性质：任意二叉树中度为 0 的结点数 n0 和度为 2 的结 点数 n2 间的关系是 n2=n0-1,代入上式，则 n=n0+n2=2n0-1。 84．（1）T 树的最大深度 Kmax=6（除根外，每层均是两个结点） T 树的最小深度 Kmin=4（具有 6 个叶子的完全二叉树是其中的一种形态） （2）非叶子结点数是 5。（n2=n0-1） （3）哈夫曼树见下图，其带权路径长度 wpl=51 1 2 6 3 4 5 84题 图 85．（1）错误，循环结束条件 top=0 不能满足，因为在 top>1 情况下，执行 top:=top-1 (2)错误 （3）错误 （4）正确 （5）结点的深度与其右孩子深度相同，比左孩 子深度少 1。 字符 weight Parent lch rch 1 A 3 0 0 0 2 B 12 0 0 0 3 C 7 0 0 0 4 D 4 0 0 0 5 E 2 0 0 0 6 F 8 0 0 0 7 G 11 0 0 0 8 0 0 0 9 0 0 0 10 0 0 0 11 0 0 0 12 0 0 0 13 0 0 0 字符 weight parent lch rch 1 A 3 8 0 0 2 B 12 12 0 0 3 C 7 10 0 0 4 D 4 9 0 0 5 E 2 8 0 0 6 F 8 10 0 0 7 G 11 11 0 0 8 5 9 5 1 9 9 11 4 8 10 15 12 3 6 11 20 13 9 7 12 27 13 2 10 13 47 0 11 12