资源描述
一、基础知识题6.1设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，求树T中的叶子数。【解答】 设度为m的树中度为0,1,2,m的结点数分别为n0, n1, n2, nm，结点总数为n，分枝数为B，则下面二式成立n= n0+n1+n2+nm (1)n=B+1= n1+2n2+mnm+1 (2)由(1)和(2)得叶子结点数n0=1+即： n0=1+(1-1)*4+(2-1)*2+(3-1)*1+(4-1)*1=86.2一棵完全二叉树上有1001个结点，求叶子结点的个数。【解答】因为在任意二叉树中度为2 的结点数n2和叶子结点数n0有如下关系：n2=n0-1,所以设二叉树的结点数为n, 度为1的结点数为n1，则 n= n0+ n1+ n2 n=2n0+n1-1 1002=2n0+n1由于在完全二叉树中，度为1的结点数n1至多为1，叶子数n0是整数。本题中度为1的结点数n1只能是0，故叶子结点的个数n0为501.注：解本题时要使用以上公式，不要先判断完全二叉树高10，前9层是满二叉树，第10层都是叶子，。虽然解法也对，但步骤多且复杂，极易出错。6.3 一棵124个叶结点的完全二叉树，最多有多少个结点。【解答】由公式n=2n0+n1-1,当n1为1时，结点数达到最多248个。6.4一棵完全二叉树有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉树有501个结点，结果如何？请写出推导过程。【解答】由公式n=2n0+n1-1，带入具体数得，500=2n0+n1-1，叶子数是整数，度为1的结点数只能为1，故叶子数为250，度为2的结点数是249。若完全二叉树有501个结点，则叶子数251，度为2的结点数是250，度为1的结点数为0。6.5某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数是多少。【解答】由公式n=2n0+n1-1，得该二叉树的总结点数是69。6.6 求一棵具有1025个结点的二叉树的高h。【解答】该二叉树最高为1025（只有一个叶子结点），最低高为11。因为210-11025211-1，故1025个结点的二叉树最低高为11。6.7 一棵二叉树高度为h，所有结点的度或为0，或为2，则这棵二叉树最少有多少结点。【解答】第一层只一个根结点，其余各层都两个结点，这棵二叉树最少结点数是2h-1。6.8将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度是多少。【解答】设含n个结点的完全三叉树的高度为h，则有nn2n0)的满二叉树对应的森林由多少棵树构成。【解答】因为在二叉树转换为森林时，二叉树的根结点，根结点的右子女，右子女的右子女，都是树的根，所以，高度为h(h0)的满二叉树对应的森林由h棵树构成。6.11 某二叉树结点的中序序列为BDAECF，后序序列为DBEFCA，则该二叉树对应的森林包括几棵树？【解答】3棵树。（本题不需画出完整的二叉树，更不需要画出森林，只需画出二叉树的右子树就可求解。如上题所述，二叉树的根结点，根结点的右子女，右子女的右子女，在二叉树转为森林时，都是树的根。）6.12 对任意一棵树，设它有n个结点，这n个结点的度数之和为多少？【解答】n-1。度数其实就是分支个数。根结点无分支所指，其余结点有且只有一个分支所指。6.13 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是多少？【解答】对二叉树线索化时，只有空链域才可加线索。一棵左子树为空的二叉树在先序线索化时，根结点的左链为空，应加上指向前驱的线索，但根结点无前驱，故该链域为空。同样分析知道最后遍历的结点的右链域为空。故一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是2个。6.14 一棵左、右子树均不空的二叉树在先序线索化后，其中空的链域的个数是多少?【解答】1个。6.15 设B是由森林F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有几个？【解答】n+1。森林中任何一个非终端结点在转换成二叉树时，其第一个子女结点成为该非终端结点的左子女，其余子女结点成为刚生成的左子女结点的右子女，右子女结点的右子女，最右子女结点的右链域为空。照此分析，n个非终端结点在转换后，其子女结点中共有n个空链域。另外，森林中各棵树的根结点可以看做互为兄弟，转换成二叉树后也产生1个空链域。因此，本题的答案是n+1。6.16 试分别找出满足以下条件的所有二叉树： (1)二叉树的前序序列与中序序列相同； (2) 二叉树的中序序列与后序序列相同； (3)二叉树的前序序列与后序序列相同；(4) 二叉树的前序序列与层次序列相同；(5) 二叉树的前序、中序与后序序列均相同。【解答】前序遍历二叉树的顺序是“根左子树右子树”，中序遍历的顺序是“左子树根右子树”，后序遍历顺序是：“左子树右子树根，根据以上原则，本题解答如下：若前序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。若前序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。若二叉树的前序、中序与后序序列均相同，则或为空树，或为只有根结点的二叉树。6.17 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，试画出这棵二叉树，对二叉树进行中序线索化，并将该二叉树转换为森林。【解答】6.18 已知一棵二叉树的后序遍历序列为EICBGAHDF，同时知道该二叉树的中序遍历序列为CEIFGBADH，试画出该二叉树。6.19设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用#表示，现前序遍历二叉树，访问的结点序列为ABD#C#E#F#，写出中序和后序遍历二叉树时结点的访问序列。【解答】中序遍历二叉树时结点的访问序列：#D#B#C#E#A#F#后序遍历二叉树时结点的访问序列。#D#ECB#FA6.20有n个结点的k叉树（k2）用k叉链表表示时，有多少个空指针？【解答】k叉树（k2）用k叉链表表示时,每个结点有k个指针，除根结点没有指针指向外，其余每个结点都有一个指针指向，故空指针的个数为： nk-(n-1)=n(k-1)+16.21 一棵高度为h的满k叉树有如下性质：根结点所在层次为0；第h层上的结点都是叶子结点；其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问：(1)各层的结点个数是多少?(2)编号为i的结点的双亲结点（若存在）的编号是多少?(3)编号为i的结点的第m个孩子结点（若存在）的编号是多少？(4)编号为i的结点有右兄弟的条件是什么？其右兄弟结点的编号是多少？【解答】(1)kl(l为层数，按题意，根结点为0层)（2）因为该树每层上均有kl个结点，从根开始编号为1，则结点i的从右向左数第个孩子的结点编号为ki。设n 为结点i的子女，则关系式(i-1)k+2=n1)的前一结点编号为i-1（其最右边子女编号是(i-1)*k+1），故结点 i的第 m个孩子的编号是(i-1)*k+1+m。(4) 根据以上分析，结点i有右兄弟的条件是，它不是双亲的从右数的第一子女，即 (i-1)%k!=0，其右兄弟编号是i+1。6.22证明任一结点个数为n(n0) 的二叉树的高度至少为(logn)+1。【解答】最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最大值。设n个结点的二叉树的最低高度是h，则n应满足2h-1n2h-1关系式。解此不等式，并考虑h是整数，则有h=logn+1，即任一结点个数为n 的二叉树的高度至少为(logn)+1。6.23 已知A1.N是一棵顺序存储的完全二叉树，如何求出Ai和Aj的最近的共同祖先？【解答】根据顺序存储的完全二叉树的性质，编号为i的结点的双亲的编号是i/2，故Ai和Aj的最近公共祖先可如下求出： while(i/2!=j/2)if(ij) i=i/2;elsej=j/2;退出while后，若i/2=0,则最近公共祖先为根结点，否则最近公共祖先是i/2。6.24已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？【解答】结点个数在20到40的满二叉树且结点数是素数的数是31，其叶子数是16。6.25求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。【解答】根据完全二叉树的性质，最后一个结点（编号为n）的双亲结点的编号是n/2，这是最后一个分枝结点，在它之后是第一个终端（叶子）结点，故序号最小的叶子结点的下标是n/2+1。6.26 试证明:同一棵二叉树的所有叶子结点，在前序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如前序abc，后序bca，中序bac。【证明】前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。三种遍历中只是访问“根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相同的相对位置出现。6.27设具有四个结点的二叉树的前序遍历序列为；为长度等于4的由，排列构成的字符序列，若任取作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么？试列出具有四个结点二叉树的全部形态及相应的中序遍历序列。【解答】若前序序列是abcd，并非由这四个字母的任意组合（4!=24）都能构造出二叉树。因为以abcd为输入序列，通过栈只能得到1/(n+1)*2n!/(n!*n!)=14 种，即以abcd为前序序列的二叉树的数目是14。任取以abcd作为中序遍历序列，并不全能与前序的abcd序列构成二叉树。例如：若取中序序列dcab就不能。该14棵二叉树的形态及中序序列略。6.28已知某二叉树的每个结点，要么其左、右子树皆为空，要么其左、右子树皆不空。又知该二叉树的前序序列为：JFDBACEHXIK；后序序列为：ACBEDXIHFKJ。请给出该二叉树的中序序列，并画出相应的二叉树树形。【解答】一般说来，仅仅知道二叉树的前序遍历序列和后序遍历序列并不能确定这棵二叉树，因为并不知道左子树和右子树两部分各有多少个结点。但本题有特殊性，即每个结点“要么其左、右子树皆为空，要么其左、右子树皆不空”。具体说，前序序列的第一个结点是二叉树的根，若该结点后再无其它结点，则二叉树只有根结点；否则，该结点必有左右子树，且根结点后的第一个结点就是“左子树的根”。到后序序列中查找这个“左子树的根”，它将后序序列分成左右两部分：左部分(包括所查到的“左子树的根结点”)是二叉树的左子树(可能为空)，右部分(除去最后的根结点)则是右子树(可能为空)。这样，在确定根结点后，就可以将后序遍历序列（从而也将前序遍历序列）分成左子树和右子树两部分了。本题中，先看前序遍历序列，第一个结点是J，所以J是二叉树的根，J后面还有结点，说明J有左、右子树，J后面的F必是左子树的根。到后序遍历序列中找到F,F将后序遍历序列分成两部分：左面ACBEDXIH，说明FACBEDXIH是根J的左子树；右面K(K的右面J已知是根)，说明K是根J的右子树。这样，问题就转化为“以前序序列FDBACEHXI和后序序列ACBEDXIHF去构造根J的左子树”，以及“以前序序列K和后序序列K去构造根J的右子树”了。如此构造下去，所构造的二叉树如下。易见，中序序列为ABCDEFXHIJK。6.29 已知一个森林的先序序列和后序序列如下，请构造出该森林。先序序列：ABCDEFGHIJKLMNO后序序列：CDEBFHIJGAMLONK【解答】森林的先序序列和后序序列对应其转换的二叉树的先序序列和中序序列，应先据此构造二叉树，再构造出森林。6.30 画出同时满足下列两条件的两棵不同的二叉树。(1)按先根序遍历二叉树顺序为ABCDE。(2)高度为5其对应的树（森林）的高度最大为4。【解答】 6.31用一维数组存放的一棵完全二叉树；ABCDEFGHIJKL。请写出后序遍历该二叉树的结点访问序列。【解答】后序遍历该二叉树的结点访问序列为：DECGHFBKJLIA6.32一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。先序序列为：C D E G H I K中序序列为：C B F A _ J K I G后序序列为：E F D B J I H A【解答】6.33设树形T在后根次序下的结点排列和各结点相应的度数如下：后根次序：次数：请画出的树形结构图。【解答】在树在后根遍历次序下，根结点在最后，任何结点的子树的所有结点都直接排在该结点之前。例如，挨着根结点的是根结点的最右边的子女。每棵子树的所有结点都聚集在一起，中间不会插入其它结点，也不会丢掉子树的任何结点。按照这种理论解答本题，在遍历次序中从右到左分析，A是根，它有4个子女，H是它的最右边的子女（第4子女）。H有2个子女，L是H的最右边的子女，L无子女，故I是H的第1子女。I又有2个子女：K和J，二者均无子女。由此推断出下一个结点G是根结点A的第3子女。，继续构造，直至最左面的结点B，结果树形如下：6.34 若森林共有n个结点和b条边(blchild & t-rchild) n2+;else if(t-lchild & !t-rchild | !t-lchild & t-rchild) n1+;elsen0+;if(t-lchild!=null) Count(t-lchild);if(t-rchild!=null) Count(t-rchild); Count6.38一棵n个结点的完全二叉树存放在二叉树的顺序存储结构中，试编写非递归算法对该树进行先序遍历。【题目分析】二叉树的顺序存储是按完全二叉树的顺序存储，双亲与子女结点下标间有确定关系。顺序存储结构的二叉树用结点下标大于n（完全二叉树）或0（对一般二叉树的“虚结点”）判空。本题是完全二叉树。【算法6.38】voidPreOrder(ElemType bt,intn)对以顺序结构存储的完全二叉树bt进行前序遍历inti=1,top=0,s;top是栈s的栈顶指针，栈容量足够大while(i0)while(i=n)printf(bti); 访问根结点；if(2*i+10) i=stop-; 取出栈顶元素while结束PreOrder6.39以二叉链表作为存储结构的二叉树，按后序遍历时输出的结点顺序为a1， a2，an。试编写一算法，要求输出后序序列的逆序an，an-1，a2，a1。【题目分析】二叉树后序遍历是按“左子树右子树根结点”的顺序遍历二叉树，根据题意，若将遍历顺序改为“根结点右子树左子树”，就可以实现题目要求。【算法6.39】voidPostOrder(BiTree bt)/对二叉树bt进行先右后左的“先根”遍历if(bt) printf(bt-data); /访问根结点 PostOrder(bt-rchild);/先根遍历右子树 PostOrder(bt-lchild);/先根遍历左子树 6.40以二叉链表作为存储结构，设计算法交换二叉树中所有结点的左、右子树。【算法6.40】voidexchange(BiTree bt)将二叉树bt所有结点的左右子树交换if(bt)BiTree s；s=bt-lchild; bt-lchild=bt-rchild; bt-rchild=s; 左右子女交换exchange(bt-lchild);交换左子树上所有结点的左右子树exchange(bt-rchild);交换右子树上所有结点的左右子树if 结束【算法讨论】将上述算法中两个递归调用语句放在前面，将交换语句放在最后，则是以后序遍历方式交换所有结点的左右子树。中序遍历方式不适合本题。6.41以二叉链表为存储结构，写出在二叉树中求值为x的结点在树中层次数的算法。题目分析按层次遍历，设一队列Q，用front和rear分别指向队头和队尾元素，last指向各层最右结点位置。【算法6.41】intLevel_x(BiTree bt，ElemType x)求值为x的结点在树中层次数if(bt!=null)intfront=0,last=1,rear=1,level=1;level记层次数BiTree Q;Q1=bt;根结点入队while(frontdata=x)printf(“%3dn”,level); return level;值为x的结点在树中层次数if(bt-lchild!=null) Q+rear=bt-lchild;左子女入队列if(bt-rchild!=null) Q+rear=bt-rchild;右子女入队列if(front=last) last=rear; level+; 本层最后一个结点已处理完 算法结束6.42已知深度为h的二叉树以一维数组作为存储结构。试编写算法求该二叉树中叶子的个数。【题目分析】按完全二叉树形式顺序存储二叉树时，无元素的位置要当作“虚结点”。设虚结点取二叉树结点以外的值（这里设为0）。设结点序号为i,则当i(2h-1)/2时，若i位置不是虚结点，则必为叶子结点。【算法6.42】intLeaves(intBT,int n)计算深度为h以一维数组BT作为存储结构的二叉树的叶子结点数，n为数组长度intnum=0;记叶子结点数for(i=0;in;i+)if(BTi!=0)if(i=n/2)if(BT2*i=0 & 2*i+1=n & BT2*i+1=0) num+;若结点无孩子，则是叶子else if(BTi!=0) num+;存储在数组后一半的元素是叶子结点returnnum;结束Leaves6.43已知二叉树以一维数组作为存储结构。试编写算法求下标为i和j的两个结点的最近共同祖先结点的值。【题目分析】二叉树顺序存储，是按完全二叉树的格式存储，利用完全二叉树双亲结点与子女结点编号间的关系，求下标为i和j的两结点的双亲，双亲的双亲，等等，直至找到最近的公共祖先。【算法6.43】voidAncestor(ElemType bt,intn,i,j,)求顺序存储在bt1.n的二叉树中下标为i和j的两个结点的最近公共祖先结点if(i1 | jj) i=i/2; 下标为i的结点的双亲结点的下标elsej=j/2;下标为j的结点的双亲结点的下标printf(“所查结点的最近公共祖先的下标是%d，值是%d”,i,Ai);设元素类型整型。Ancestor6.44已知一棵完全二叉树顺序存储于向量s1.n中，试编写算法由此顺序存储结构建立该二叉树的二叉链表。【算法6.44】BiTree Creat(ElemType A,inti)n个结点的完全二叉树存于一维数组A中，本算法建立二叉链表表示的完全二叉树BiTree tree;if(idata=Ai;if(2*in) tree-lchild=null；elsetree-lchild=Creat(A,2*i)；if(2*i+1n) tree-rchild=null；elsetree-rchild=Creat(A,2*i+1)；return(tree)；Creat【算法讨论】初始调用时,i=1。6.45编写算法判别给定二叉树是否为完全二叉树。【题目分析】判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。具体说，在层次遍历时，若碰到一个空指针后，在遍历结束前又碰到结点，则结论为该二叉树不是完全二叉树。【算法6.45】intJudgeComplete(BiTree bt)判断二叉树是否是完全二叉树,如是，返回1，否则，返回0inttag=0; 出现空指针时，置tag=1BiTree p=bt, Q; Q是队列，元素是二叉树结点指针，容量足够大if(p=null)return(1);QueueInit(Q); QueueIn(Q,p); 初始化队列，根结点指针入队while(!QueueEmpty(Q)p=QueueOut(Q);出队if(p-lchild & !tag) QueueIn(Q,p-lchild);左子女入队elseif(p-lchild)return0; 前边已有结点空，本结点不空 elsetag=1; 首次出现结点为空if(p-rchild & !tag) QueueIn(Q,p-rchild);右子女入队elseif(p-rchild)return0;elsetag=1; whilereturn1; JudgeComplete算法讨论完全二叉树证明还有其它方法。判断时易犯的错误是证明其左子树和右子树都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。6.46设树以双亲表示法存储，编写计算树的深度的算法。【题目分析】以双亲表示法作树的存储结构，对每一结点，找其双亲，双亲的双亲，直至（根）结点,就可求出每一结点的层次，取其结点的最大层次就是树的深度。【算法6.46】intDepth(Ptree t)求以双亲表示法为存储结构的树的深度intmaxdepth=0;for(i=1;i0)temp+; f=t.nodesf.parent; 深度加1,并取新的双亲if(tempmaxdepth)maxdepth=temp;最大深度更新return(maxdepth);返回树的深度 结束Depth6.47已知在二叉树中，*root为根结点，*p和*q为二叉树中两个结点，试编写求距离它们最近的共同祖先的算法。【题目分析】后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。采用后序非递归遍历。栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈拷入另一辅助栈中。再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（相等）的元素就是结点p 和q的最近公共祖先。【算法6.47】先设二叉树的结点结构为：typedefstructBiTree t;inttag;tag=0表示结点的左子女已访问，tag=1为右子女已访问stack;stack s,s1;栈，容量足够大BiTree Ancestor(BiTree root, BiTree p, BiTree q, BiTree r)求二叉树上结点p和q的最近的共同祖先结点rtop=0; bt=root;while(bt!=null |top0)while(bt!=null & bt!=p & bt!=q)结点入栈s+top.t=bt;stop.tag=0;bt=bt-lchild; 沿左分枝向下if(bt=p)不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点for(i=1;i0;i-)将栈中元素的树结点到s1去匹配pp=si.t;for(j=top1;j0;j-)if(s1j.t=pp)printf(“共同的祖先已找到n”)；return(pp);while(top!=0 & stop.tag=1) top-; 退栈if(top!=0)stop.tag=1;bt=stop.t-rchild;沿右分枝向下遍历结束while(bt!=null |top0)return(null);、p无公共祖先结束Ancestor6.48以二叉链表作为存储结构，设计按层次遍历二叉树的算法。【算法6.48】voidLevel(BiTree bt) 层次遍历二叉树if(bt)QueueInit(Q); Q是以二叉树结点指针为元素的队列QueueIn(Q,bt)；while(!QueueEmpty(Q)p=QueueOut(Q);出队printf(p-data);访问结点if(p-lchild) QueueIn(Q,p-lchild); 非空左子女入队if(p-rchild) QueueIn(Q,p-rchild); 非空右子女入队if(bt)6.49编写算法查找二叉链表中数据域值为x的结点（假定各结点的数据域值各不相同），并打印出x所有祖先的数据域值。【题目分析】后序遍历最后访问根结点，当访问到值为x的结点时，栈中所有元素均为该结点的祖先。【算法6.49】voidSearch(BiTree bt,ElemType x)在二叉树bt中，查找值为x的结点，并打印其所有祖先typedefstructBiTree t;inttag;tag=0表示左子女被访问，tag=1右子女被访问stack;stack s;栈容量足够大top=0;while(bt!=null|top0)while(bt!=null & bt-data!=x)结点入栈 s+top.t=bt; stop.tag=0; bt=bt-lchild;沿左分枝向下if(bt-data=x)printf(“所查结点的所有祖先结点的值为:n”);找到x for(i=1;idata);return; 输出祖先值后结束while(top!=0 & stop.tag=1) top-;退栈（空遍历）if(top!=0)stop.tag=1;bt=stop.t-rchild; 沿右分枝向下遍历while(bt!=null|top0) 结束search6.50设计这样的二叉树，用它可以表示父子、夫妻和兄弟三种关系，并编写一个查找任意父亲结点的所有儿子结点的过程。【题目分析】用二叉树表示出父子，夫妻和兄弟三种关系，可以用根结点表示父（祖先），根结点的左子女表示妻，妻的右子女表示子。这种二叉树可以看成类似树的孩子兄弟链表表示法；根结点是父，根无右子女，左子女表示妻，妻的右子女（右子女的右子女等）均可看成兄弟（即父的所有儿子），兄弟结点又成为新的父，其左子女是兄弟（父的儿子）妻，妻的右子女（右子女的右子女等）又为儿子的儿子等等。首先递归查找某父亲结点，若查找成功，则其左子女是妻，妻的右子女及右子女的右子女等均为父亲的儿子。【算法6.50】BiTree Search(BiTree t,ElemType father)在二叉树上查找值为father的结点inttag=0;if(t=null) p=null;二叉树上无father结点elseif(t-data=father)tag=1; p=t;查找成功elsep=Search(t-lchild,father);if(tag=0)p=Search(t-rchild,father);returnp;结束SearchvoidPrintSons(BiTree t,ElemType x)在二叉树上查找结点值为x的所有的儿子p=Serach(t,x); 在二叉树t上查找父结点xif(p & p-lchild) 存在父结点,且有妻q=p-lchild; q=q-rchild;先指向其妻结点，再找到第一个儿子while(q!=null)printf(q-data); q=q-rchild;输出父的所有儿子 结束PrintSons6.51 编写递归算法判定两棵二叉树是否相等。【题目分析】首先判断二叉树的根是否相等，如是，再判断其左、右子树是否相等。【算法6.51】intBTEqual(BiTree t, BiTree x)判定二叉树t和二叉树x是否相等if(!t & !x)returntrue; if(t & x & t-data=x-data & BTEqual(t-lchild,x-lchild) & BTEqual(t-rchild,x-rchild)returnture; else returnfalse;6.52已知一棵高度为具有个结点的二叉树，按顺序方式存储，编写将树中最大序号叶子结点的祖先结点全部打印输出的算法。【题目分析】二叉树中最大序号的叶子结点,是在顺序存储方式下编号最大的结点【算法6.52】voidAncesstor(ElemType bt)打印最大序号叶子结点的全部祖先c=m;m=2K-1while(btc=0) c-;找最大序号叶子结点,该结点存储时在最后f=c/2; c的双亲结点fwhile(f!=0) 从结点c的双亲结点直到根结点，路径上所有结点均为祖先结点printf(btf); f=f/2; 逆序输出，最老的祖先最后输出结束6.53设二叉树以二叉链表作为存储结构，编写算法对二叉树进行非递归的中序遍历。【算法6.53】voidInOrder(BiTree bt)对二叉树进行非递归中序遍历 BiTree s,p=bt;s是元素为二叉树结点指针的栈，容量足够大inttop=0;while(p | top0) while(p) s+top=p; bt=p-lchild; 沿左子树向下if(top0)p=stop-; printf(p-data); p=p-rchild; 退栈，访问，转右子树结束6.54设T是一棵满二叉树，写一个把T的后序遍历序列转换为先序遍历序列的递归算法。【题目分析】对一般二叉树，仅根据一个先序（或中序、或后序）遍历，不能确定另一个遍历序列。但由于满二叉树“任一结点的左右子树均含有数量相等的结点”，根据此性质，可将任一遍历序列转为另一遍历序列。【算法6.54】voidPostToPre(ElemType post,pre,intl1,h1,l2,h2)将满二叉树的后序序列转为先序序列，l1,h1,l2,h2是序列初始和最后结点的下标。if(h1=l1)prel2=posth1;根结点visit(prel2);访问根结点half=(h1-l1)/2;左或右子树的结点数PostToPre(post,pre,l1,l1+half-1,l2+1,l2+half)将左子树后序序列转为先序序列PostToPre(post,pre,l1+half,h1-1,l2+half+1,h2)将右子树后序序列转为先序序列 PostToPre t6.55若二叉树BT的每个结点，其左、右子树都为空，或者其左、右子树都不空，这种二叉树有时称为“严格二叉树”。由“严格二叉树”的前序序列和后序序列可以唯一确定该二叉树。写出根据这种二叉树的前序序列和后序序列确定该二叉树的递归算法。【问题分析】前序序列的第一个结点是二叉树的根，若该结点后再无其它结点，则该结点是叶子；否则，该结点必有左、右子树，且根结点后的第一个结点就是左子树的根。到后序序列中查找这个左子树的根，它将后序序列分成左、右两部分：左部分(包括所查到的结点)是二叉树的左子树(可能为空)，右部分(除去最后的根结点)则是右子树(可能为空)。这样，在确定根结点后，可递归确定左、右子树。【算法6.55】void creat(BiTree *BT,char pren,char postn,int l1,int h1,int l2,int h2)由严格二叉树的前序序列pre(l1:h1)和后序序列post(l2:h2)建立二叉树 BiTree p=*BT;if(l1data=prel1;前序序列的第一个元素是根if(l1=h1) p-lchild=p-rchild=null; 叶子结点else分支结点 for(int i=l2;ilchild), pre,post,l1+1,l1+L,l2,i);creat(&(p-rchild), pre,post,l1+L+1,h1,i+1,h2-1);elseif结束6.56编写一个递归算法，利用叶结点中空的右链指针域rchild，将所有叶结点自左至右链接成一个单链表，算法返回最左叶结点的地址（链头）。【题目分析】叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。【算法6.56】LinkedList head,pre=null;全局变量LinkedList InOrder(BiTree bt)中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为headif(bt)InOrder(bt-lchild);中序遍历左子树if(bt-lchild=null & bt-rchild=null)叶子结点if(pre=null) head=bt; pre=bt;处理第一个叶子结点 elsepre-rchild=bt; pre=bt; 将叶子结点链入链表 InOrder(bt-rchild);中序遍历右子树 pre-rchild=null; 设置链表尾return(head); InOrder6.57已知有一棵二叉链表表示的二叉树，编写算法，输出从根结点到叶子结点的最长一枝上的所有结点。【题目分析】后序遍历时栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针大于已保存的最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。【算法6.57】voidLongestPath(BiTree bt)求二叉树从根结点到叶子结点的最长一枝上的所有结点BiTree p=bt,l,s;l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点inti，top=0,tag,longest=0;while(p | top0) while(p)s+top=p；tagtop=0; p=p-lchild;沿左分枝向下if(tagtop=1) 当前结点的右分枝已遍历if(!stop-lchild & !stop-rchild)只有到叶子结点时，才查看路径长度if(toplongest)for(i=1;i0 & tagtop=1) top-;退栈if(top0)tagtop=1; p=stop.rchild; 沿右子分枝向下while(p!=null|top0)结束LongestPath6.58试编写一算法对二叉树进行前序线索化。【题目分析】线索化是在遍历中完成的，因此，对于二叉树进行前序、中序、后序遍历，在“访问根结点”处进行加线索的改造，就可实现前序，中序和后序的线索化。【算法6.58】BiThrTree pre=null;设置前驱voidPreOrderThreat(BiThrTree BT)对以线索链表为存储结构的二叉树BT进行前序线索化if(BT!=null)if(BT-lchild=null)BT-ltag=1; BT-lchild=pre;设置左线索if(pre!=null & pre-rtag=1) pre-rchild=BT; 设置前驱的右线索；if(BT-rchild=null) BT-rtag=1; 为建立右链作准备pre=BT; 前驱后移if(BT-ltag=0) PreOrderThreat(BT-lchild); 左子树前序线索化PreOrderThreat(BT-rchild); 右子树前序线索化if(BT!=null) 结束PreOrderThreat6.59试编写一算法对二叉树进行中序线索化。【算法6.59】BiThrTree pre=null;voidInOrderThreat(BiThrTree T)对二叉树进行中序线索化if(T)InOrderThreat(T-lchild);左子树中序线索化if(T-lchild=null)T-ltag=1; T-lchild=pre; 左线索为preif(pre!=null & pre-rtag=1) pre-rchild=T;给前驱加后继线索if(T-rchild=null) T-rtag=1; 置右标记，为右线索作准备pre=BT; 前驱指针后移InOrderThreat(T-rchild); 右子树中序线索化if结束InOrderThreat6.60设p指向前序线索二叉树t的某结点，编写算法求*p结点的后继结点。【题目分析】在前序线索二叉树中，求*p结点的后继结点，若*p结点有左子女，则左子女是其后继结点；若*p结点无左子女而有右子女，则右子女是其后继；若*p结点无左、右子女，线索p-rchild指向其后继。【算法6.60】BiThrTree PreorderNext(BiThrTreep)if (p-ltag=0) /结点有左子女 return(p-lchild);/结点的左子女为其前序后继else return(p-rchild);/p-rchild为其前序后继
展开阅读全文