第六章树习题答案.doc

第六章 树 习题答案一、 基础知识题6.1.假设在树中，结点x是结点y的双亲时,用(x,y)来表示树边.已知一棵树边的集合为(i,m),(i,n),(e,i),(b,e),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用树形表示法出此树，并回答下列问题：(1)哪个是根结点? (2)哪些是叶结点? (3)哪个是g的双亲? (4)哪些是g的祖先?(5)哪些是g的孩子? (6)哪些是e的子孙? (7)哪些是e的兄弟?哪些是f的兄弟?(8)结点b和n的层次各是多少? (9)树的深度是多少? (10)以结点c为根的子树的深度是多少? (11) 树的度数是多少?a是根结点；dmnfjkl是叶结点；c是g的双亲；c,a是g的祖先；j,k是g的孩子；imn是e的子孙；d是e的兄弟；g,h是f的兄弟；b的层次是2；n的层次是5；树的深度是5；以c为根的子树深度是3；树的度数是3； 6.2 一棵度为2的有序树与一棵二叉树有何区别?答：一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。 6.3 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。6.4 已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，.nm个度为m的结点，问该树中有多少片叶子?解： 设该树中的叶子数为n0个。该树中的总结点数为n个，则有： n=n0+n1+n2+nm (1)又有除根结点外，树中其他结点都有双亲结点，且是唯一的(由树中的分支表示)，所以，有双亲的结点数为： n-1=0*n0+1*n1+2*n2+m*nm (2) 联立(1)(2)方程组可得： 叶子数为：n0=1+0*n1+1*n2+2*n3+.+(m-1)*nm 6.5一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问： (1)各层的结点数目是多少?(2)编号为i的结点的双亲结点(若存在)的编号是多少?(3)编号为i的结点的第j个孩子结点(若存在)的编号是多少?(4)编号为i的结点的有右兄弟的条件是什么? 其右兄弟的编号是多少?解：(1) 层号为h的结点数目为kh-1(2) 编号为i的结点的双亲结点的编号是：|_ (i-2)/k _|+1(不大于(i-2)/k的最大整数。也就是(i-2)与k整除的结果.以下/表示整除。(3) 编号为i的结点的第j个孩子结点编号是：k*(i-1)+1+j;(4) 编号为i的结点有右兄弟的条件是(i-1)能被k整除右兄弟的编号是i+1. 6.6高度为h的完全二叉树至少有多少个结点?至多有多少个结点?解：高度为h的完全二叉树至少有2h-1个结点，至多有2h-1个结点(也就是满二叉树)。6.7 在具有n个结点的k叉树(k=2)的k叉链表表示中，有多少个空指针?解：n个结点的K叉树共有n*k个指针域，已使用的指针域为n-1,所以空指针的个数为：n(k-1)+1;6.8 假设二叉树包含的结点数据为1，3，7，12。(1)画出两棵高度最大的二叉树；(2)画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。解：(1)高度最大的两棵二叉树如图：1 1/ 3 3/ 7 7/ 2 2/ 12 12 (2)两棵完全二叉树如下：12 12/ / 7 3 7 3/ / 1 2 2 1 6.9试找出分别满足下面条件的所有二叉树：(1)前序序列和中序序列相同； (2)中序序列和后序序列相同；(3)前序序列和后序序列相同； (4)前序、中序、后序序列均相同。答：(1) 前序序列和中序序列相同的二叉树是：空二叉树或没有左子树的二叉树(右单支树)。(2) 中序序列和后序序列相同的二叉树是：空二叉树或没有右子树的二叉树(左单支树)。(3) 前序序列和后序序列相同的二叉树是：空二叉树或只有根的二叉树。(4) 前序、中序、后序序列均相同的二叉树：空树或只有根结点的二叉树。 6.10 试采用顺序存储方法和链接存储方法分别画也6.30所示各二叉树的存储结构。解： (2)链式存储结构：6.11 分别写出图6.30(下图)所示各二叉树的前序、中序和后序序列。 解： (a)前序序列：12345 中序序列：24531 后序序列：54321 (b)前序序列：12345 中序序列：13542 后序序列：54321 (c)前序序列：12357864 中序序列：17583524 后序序列：78563421 (d)前序序列：124735689 中序序列：742153896 后序序列：742589631 6.12 若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。 (1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。 (2)已知一棵二叉树的在序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。 (3)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉树。解： (1)已知二叉树的前序序列为ABDGHCEFI和中序序列GDHBAECIF，则可以根据前序序列找到根结点为A，由此，通过中序序列可知它的两棵子树包分别含有GDHB和ECIF结点，又由前序序列可知B和C分别为两棵子树的根结点.以此类推可画出所有结点： A / B C / / D EF / / G H I (2)以同样的方法可画出该二叉树： A / B F C G / D E H (3)这两棵不同的二叉树为： A A / B B 6.13 对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF，请画出此二叉树。解： 类似于上一题的分析方法，可画出二叉树的所有结点： A / B C / D E F / / G H I J 6.14 试画出图6.30(下图)所示各二叉树的前序、中序和后序线索树及相应的线索链表。答：略 6.15 在何种线索树中，线索对求指定结点在相应次序下的前趋和后继并无帮助?答： 分别在前序线索二叉树和后序线索二叉树中查找前趋和后继时，线索无帮助作用。 6.16 对图6.31所示的森林： (1)求各树的前序序列和后序序列； (2)求森林的前序序列和后序序列； (3)将此森林转换为相应的二叉树； (4)给出(a)所示树的以亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代?解： (1) (a)的前序序列：ABCDEF 后序序列：BDEFCA (b)的前序序列：GHIJK 后序序列：IJKHG (c)的前序序列：LMPQRNO 后序序列：QRPMNOL (2) 此森林的前序序列： ABCDEFGHIJKLMPQRNO01345678902345790123456789*123456789012345678012345689023456789*1234567890123456789*1234567890123456789*12345678901234567890123456789 此森林的后序序列： BDEFCAIJKHGQRPMNOL (3) 森林转化为二叉树的过程见动画：(4) 略 6.17 画出图6.32(下图)所示的各二叉树所对应的森林。解：各二叉树所对应森林如下：(a) A(b) A/B/C(c) A B C(d) A C| B (e) A C F I / | B E L / | DHK | | G J 6.18高度为h的严格二叉树至少有多少个结点?至多有多少个结点?答： 所谓严格二叉树是指该树中没有度数为1的分支结点的二叉树。 所以：高度为h的的严格二叉树至少有2h-1个结点；至多有2h-1个结点(即满二叉树)。 6.19 在什么样的情况下，等长编码是最优的前缀码?答: 在每个字符的使用概率相同的情况下，也即在哈夫曼树中每片叶子的权重相等的时候，等长编码是最优的前缀码。 6.20 下述编码哪一组不是前缀码? 00,01,10,11,0,1,00,11,0,10,110,111答： 第二组不是前缀码。因为0，1分别是00和11的前缀。(前缀码是指该编码集中的任一编码不是其他编码的前缀) 6.21 假设用于通信的电文由字符集a,b,c,d,e,f,g,h中的字母构成，这8个字母在电文中出现的概率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10. (1)为这8个字母设计哈夫曼编码。 (2)若用这三位二进制数(07)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?解： (1)哈夫曼编码 根据上图可得编码表：a:1001b:01c:10111d:1010e:11f:10110g:00h:1000(2)用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为： 4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87% 其平均码长是等长码的87%。 所以平均压缩率为13%。 二、 算法设计题6.22 二叉树的遍历算法可写为通用形式。例如通用的中序遍历为：void Inorder(BinTree,T,void(* visit)(DataType x)if (T)Inorder(T-lchild,Visit);/遍历左子树Visit(T-data);/通过函数指针调用它所指的函数来访问结点Inorder(T-rchild,Visit);/遍历右子树其中Visit是一个函数指针，它指向形如void f(DataType x)的函数。因此我们可以将访问结点的操作写在函数f中通过调用语句Inorder(root,f)将f的地址传递给Visit,来执行遍历操作。请写一个打印结点数据的函数，通过调用上述算法来完成书中6.3节的中序遍历。解：函数如下：void PrintNode(BinTree T)printf(%c,T-data);/定义二叉树链式存储结构typedef char DataType;/定义DataType类型typedef struct nodeDataType data;struct node *lchild, *rchild;/左右孩子子树BinTNode; /结点类型typedef BinTNode *BinTree ;/二叉树类型void Inorder(BinTree T,void(* Visit)(DataType x)if(T)Inorder(T-lchild,Visit);/遍历左子树Visit(T-data); /通过函数指针调用它所指的函数访问结点Inorder(T-rchild,Visit);/遍历右子树6.23 以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。解：(1)求结点数的递归定义为：若为空树，结点数为0若只有根结点，则结点数为1；否则，结点数为根结点的左子树结点数+右子树结点数+1(2)求叶子数的递归定义为：若为空树，叶子数为0若只有根结点，则叶子数为1；否则，叶子数为根结点的左子树叶子数+右子树叶子数typedef char DataType;/定义DataType类型typedef struct nodeDataType data;struct node *lchild, *rchild;/左右孩子子树BinTNode; /结点类型typedef BinTNode *BinTree ;/二叉树类型int Node(BinTree T)/算结点数if(T)if (T-lchild=NULL)&(T-rchild=NULL)return 1;else return Node(T-lchild)+Node(T-rchild)+1;else return 0;int Leaf(BinTree T) /算叶子数if(T)if (T-lchild=NULL)&(T-rchild=NULL)return 1;else return Leaf(T-lchild)+Node(T-rchild);else return 0; 6.24以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法，所谓宽度是指二叉树的各层上，具有结点数最多的那一层上的结点总数。解：(1)根据递归定义：二叉树的高度为：当为空树时，高度为0；当只有一个结点时，高度为1；其他情况：高度为max(根的左子树高度，根的右子树高度)+1int Height(BinTree T)int hl,hr;if(T)/非空树if(t-lchild=NUll)&(t-rchild=NULL)/只含一个根结点return 1;elsehl=height(t-lchild);/根的左子树高度hr=height(t-rchild);/根的右子树高度if (hl=hr)return hl+1;else return h2+1;else return 0;(2)要求二叉树的宽度的话，则可根据树的高度设置一个数组temp。tempi用于存放第i层上的结点数(即宽度)。在访问结点时,把相应计算该结点下一层的孩子数并存入相应数组元素中，遍历左子树后向上返回一层计算右子树的宽度，并取出最大的一个数组元素作为树的宽度。#define M 10 /假设二叉树最多的层数int Width(BinTree T)int static nM;/向量存放各层结点数int static i=1;int static max=0;/最大宽度if(T)if(i=1) /若是访问根结点ni+; /第1层加1i+; /到第2层if(T-lchild)/若有左孩子则该层加1ni+;if(T-rchild)/若有右孩子则该层加1ni+;else /访问子树结点i+; /下一层结点数if(T-lchild)ni+;if(T-rchild)ni+;if(maxlchild);/遍历左子树i-; /往上退一层Width(T-rchild);/遍历右子树return max;/算法结束6.25 以二叉链表为存储结构， 写一算法交换各结点的左右子树。 答：要交换各结点的左右子树，最方便的办法是用后序遍历算法，每访问一个结点时把两棵子树的指针进行交换，最后一次访问是交换根结点的子树。void ChangeBinTree(BinTree *T) /交换子树if(*T) /这里以指针为参数使得交换在实参的结点上进行后序遍历BinTree temp;ChangeBinTree(&(*T)-lchild);ChangeBinTree(&(*T)-rchild);temp=(*T)-lchild;(*T)-lchild=(*T)-rchild;(*T)-rchild=temp;6.26 以二叉链表为存储结构，写一个拷贝二叉树的算法void CopyTree(BinTree root, BinTree *newroot),其中新树的结点是动态申请的，为什么newroot要说明为BinTree型指针的指针?解：因为调用函数只能进行值传递,当返回类型为void时，就必须把实参的地址传给函数，否则函数不会对实际参数进行任何操作,也就得不到所需结果了。所以，newroot要说明为BinTree型指针void CopyTree(BinTree root,BinTree *newroot) /拷贝二叉树if(root)/如果结点非空 /按前序序列拷贝*newroot=(BinTNode *)malloc(sizeof(BinTNode);/生成新结点(*newroot)-data=root-data;/拷贝结点数据CopyTree(root-lchild,&(*newroot)-lchild);/拷贝左子树CopyTree(root-rchild,&(*newroot)-rchild);/拷贝右子树else /如果结点为空*newroot=NULL;/将结点置空6.27 以二叉链表为存储结构，分别写出在二叉树中查找值为x的结点及求x所在结点在树中层数的算法。 解：根据上几题的算法可以得出本题的算法如下：#define M 10 /假设二叉树最多的层数BinTree SearchBTree(BinTree *T,DataType x)/以前序遍历算法查找值为x的结点if(*T)if(*T)-data=x )return *T;SearchBTree(&(*T)-lchild,x);SearchBTree(&(*T)-rchild,x);int InLevel(BinTree T,DataType x)int static l=0;/设一静态变量保存层数if(T)if(l=0)/若是访问根结点l+;/第1层if(T-data=x)return l;if(T-lchild|T-rchild)l+;/若根有子树，则层数加1else /访问子树结点if(T-data=x)return l;if(T-lchild|T-rchild)l+;/若该结点有子树，则层数加1else return 0;InLevel(T-lchild,x);/遍历左子树InLevel(T-rchild,x);/遍历右子树6.28 一棵n个结点的完全二叉树以向量作为存储结构，试写一非递归算法实现对该树的前序遍历。解：以向量为存储结构的完全二叉树，其存储在向量中的结点其实是按层次遍历的次序存放的，可以根据课本第74页的内容设计出算法：typedef char DataType;/设结点数据类型为char#define M 100/设结点数不超过100typedef DataType BinTreeM;void Preorder(BinTree T) /前序遍历算法int n=T0;int pM;/设置一队列存放结点值int i,j;for(i=1;i=n;i+)if (i=1)/根结点j=1;else if(2*j=n)/左子树j=2*j;else if(j%2=0&j1)/双亲之右兄弟j=j/2+1;pi=Tj;/入队printf(%c,pi);/打印结点值6.29 以二叉链表为存储结构，一算法对二叉树进行层次遍历(层次遍历的定义见6.13).提示：应使用队列来保存各层的结点。答： #define M 100 /假设结点数最多为100typedef char DataType;/队列结点值类型typedef struct/定义一个队列int front;int rear;int count;DataType dataM;QBTree;static QBTree Q;/设一全局静态变量保存遍历结果void Levelorder(BinTree T)/层次遍历if(T)if(QueueEmpty(&Q) /根结点及子树结点入队EnQueue(&Q,T-data);if(T-lchild)EnQueue(&Q,T-lchild-data);if(T-rchild)EnQueue(&Q,T-rchild-data);else /子树结点入队if(T-lchild)EnQueue(&Q,T-lchild-data);if(T-rchild)EnQueue(&Q,T-rchild-data);Levelorder(T-lchild);/遍历左子树Levelorder(T-rchild);/遍历右子树6.30以二叉链表为存储结构，写一算法用括号形式(key LT,RT)打印二叉树，其中key是根结点数据，LT和RT是括号形式的左子树和右子树。并且要求空树不打印任何信息，一个结点x的树的打印形式是x而不是(x,)的形式。答：算法如下：void PrintTree(BinTree T)/打印二叉树 (以前序遍历实现)if(T)/非空树printf(%c,T-data);/打印结点值if(T-lchild|T-rchild)printf();/打印括号PrintTree(T-lchild);/打印左子树if(T-lchild&T-rchild)printf(,);/若存在两棵子树打印逗号PrintTree(T-rchild);/打印右子树if(T-lchild|T-rchild)printf();void PrintTree1(BinTree T) /由于题目存在两义性，所以这里另作了一个打印算法打印二叉树 (以前序遍历实现)if(T)/非空树printf(%c,T-data);/打印括号和结点值PrintTree1(T-lchild);/打印左子树if(T-lchild&T-rchild)printf(,);PrintTree1(T-rchild);/打印右子树printf();6.31 以线索链表作为存储结构。分别写出在前序线索树中查找给定结点*p的前序后继，以及在后序线索树中查找 *p的后序前趋的算法。解：算法如下：BinThrNode * SearchPostInPre(BinThrNode *p)/查找结点*p的前序后继if(p)if(p-rtag=Link)&(p-ltag=link)/当左、右都为孩子指针return p-lchild;/*p的前序后继为左孩子else return p-rchild;BinThrNode *SearchPreInPost(BinThrNode *p)/查找*p结点的后序前趋if(p)if(p-ltag=thread)|(p-rtag=thread)/当有左线索或无有孩子 return p-lchild;/*p的后续前趋为p-lchildelse return p-rchild;6.32 完成6.6.1节算法CreatHuffmanTree中调用的三个函数：InitHuffmanTree,InputWeight 和SelectMin。解：整个程序如下：#define n 7 /叶子数目,根据实际需要定义#define m 2*n-1 /结点数目typedef structfloat weight;int lchild,rchild,parent;/左右孩子及双亲指针HTNode;typedef HTNode HuffmanTreem;/是向量类型的void InitHuffmanTree(HuffmanTree T)/初始化int i;for (i=0; im; i+)Ti.weight=0;Ti.lchild=-1;Ti.rchild=-1;Ti.parent=-1;void InputWeight(HuffmanTree T)/输入权值float w;int i;for (i=0; in;i+)printf(n输入第%d个权值:,i+1);scanf(%f,&w);Ti.weight=w;void SelectMin(HuffmanTree T, int i, int *p1,int *p2)/选择两个小的结点float min1=999999;/预设两个值float min2=999999;/并使它大于可能出现的最大权值int j;for (j=0;j=i;j+)if(Tj.parent=-1)if(Tj.weightmin1)min2=min1;/改变最小权，次小权及其位置min1=Tj.weight;/找出最小的权值*p2=*p1;*p1=j;else if(Tj.weightmin2)min2=Tj.weight;/改变次小权及位置*p2=j;/选择结束6.33 分别写出对文件进行哈夫曼编码的算法，以及对已编码文件进行解码的算法。为简单起见，可以假设文件是存放在一个字符向量中。答：具体参见严蔚敏，吴伟民的数据结构第二版 下午13：0017：00度。全体员工都必须自觉遵守工作时间，实行不定时工作制的员工不必打卡。3.1.2.2打卡次数：一日两次，即早上上班打卡一次，下午下班打卡一次。3.1.2.3打卡时间：打卡时间为上班到岗时间和下班离岗时间； 3.1.2.4因公外出不能打卡：因公外出不能打卡应填写外勤登记表,注明外出日期、事由、外勤起止时间。因公外出需事先申请，如因特殊情况不能事先申请，应在事毕到岗当日完成申请、审批手续，否则按旷工处理。因停电、卡钟（工卡）故障未打卡的员工，上班前、下班后要及时到部门考勤员处填写未打卡补签申请表，由直接主管签字证明当日的出勤状况，报部门经理、人力资源部批准后，月底由部门考勤员据此上报考勤。上述情况考勤由各部门或分公司和项目文员协助人力资源部进行管理。3.1.2.5手工考勤制度3.1.2.6手工考勤制申请：由于工作性质，员工无法正常打卡（如外围人员、出差），可由各部门提出人员名单，经主管副总批准后，报人力资源部审批备案。3.1.2.7参与手工考勤的员工，需由其主管部门的部门考勤员(文员)或部门指定人员进行考勤管理，并于每月26日前向人力资源部递交考勤报表。3.1.2.8参与手工考勤的员工如有请假情况发生，应遵守相关请、休假制度，如实填报相