数据结构习题02399

-数据结构习题及解析第6 章 树和二叉树基础知识题6.1 已知一棵树边的集合为 , ，请画出这棵树，并回答下列问题：（1） 哪个是根结点？（2） 哪些是叶子结点？（3） 哪个是结点G的双亲？（4） 哪些是结点G的祖先？（5） 哪些是结点G的孩子？（6） 哪些是结点E的子孙？（7） 哪些是结点E的兄弟？哪些是结点F的兄弟？（8） 结点B和N的层次号分别是什么？（9） 树的深度是多少？（10） 以结点C为根的子树的深度是多少？ 6.2一棵度为2的树与一棵二叉树有何区别？ 6.3试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 6.4一棵深度为H的满k叉树有如下性质；第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树，如果按层次顺序从1开始对全部结点的编号，问：（1） 各层的结点树目是多少？（2） 编号为p的结点的父结点（若存在）的编号是多少？（3） 编号为p的结点的第i 个儿子结点（若存在）的编号是多少？（4） 编号为p的结点有右兄弟的条件什么？其右兄弟的编号是多少？ 6.5已知一棵树为k的树中有n1 个度为1的结点，n2 个度为2的结点,nk 个度为k的结点,问该树中有多少个叶子结点? 6.6已知在一棵含有n个结点的树中,只有度为k的分支结点和度为0的叶子结点.试求该树含有的叶子结点的数目. 6.7一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？ 6.8证明：一棵满k叉树上的叶子结点数n0 和 非叶子结点数n1 之间满足以下关系：n0 =（k - 1）n1 + 1 6.9试分别推导出含有n个结点和含有n0 个叶子结点的完全三叉树的深度H。 6.10对于那些所有非叶子结点均有非空左右子树的二叉树：（1） 试问：有n个叶子结点的树中共有多少个结点？（2） 试证明：2-（li-1 ） =1 其中n 为叶子节点的个数，li 表示第 i 个叶子节点所在的层次（设根结点所在层次为1）。 6.11 在二叉树的顺序存储结构中，实际上隐含这双亲的信息，因此可和三叉链表对应。假设每个指针域占4个字节的存储，每个信息域占k个字节的存储，试问：对于一棵有n个结点的二叉树，且在顺序存储结构中最后一个结点的下标为m，在什么条件下顺序存储结构比三叉链表更节省空间？ 6.12 对应6.3所得各种形态的二叉树，分别写出前序、中序、后序遍历的序列。 6.13 假设n和m为二叉树中二结点，用“1”、“0”或“”（分别表示肯定、恰恰相反或者不一定）填写下表： 答问已知前序遍历时 n在m前？中序遍历时 n在m前？后序遍历时 n在m前？ n在m左方n在m左方n在m祖先n在m子孙 注意：如果（1）离a 和 b 最近的共同祖先p存在且（2）a 在p 的左子树中，b在p的右子树中，则称a在b的左方（即b在a的右方）。6.14 找出所有满足下列条件的二叉树；（a） 它们在先序遍历和中序遍历时，得到的结点访问序列相同；（b） 它们在后序遍历和中序遍历时，得到的结点访问序列相同；（c） 它们在先序遍历和后序遍历时，得到的结点访问序列相同； 6.15请对右图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索。 6.16将下列二叉链表改为先序线索链表（不画出树的形态）。 1 2 3 4 5 6 7 8 9 10 11 12 13 14InfoABCDEFGHIJKLMNLtag Lchild24607010012130000RtagRchild3500891100014000 6.17 阅读下列算法，若有错，则改之。BiTree InSucc（BiTree q） / 已知q 是指向中序线索二叉树上某个结点的指针， / 本函数返回指向*q的后继的指针。 r= q-rchild; if (!r-rtag) while (!r-rtag) r=r-rchild; return r; /InSucc6.18试讨论，能否在一棵中序全线索二叉树上查找给定结点*p 在后序序列中的后继。6.19 分别画出和下列树对应的各个二叉树；6.20将下列森林转换为相应的二叉树，并分别按以下说明进行线索化；（1） 先序前驱线索化；（2） 中序全线索化；（3） 后序后继线索化。6.21画出和下列二叉树相应的森林；6.22对于6.19题中给出的各树分别求出以下遍历序列； （1）先序遍历 （2） 后序遍历6.23画出和下列已知序列对应的树T： 树的先根次序访问序列为GFKDAIEBCHG 树的后跟次序访问序列为DIAEKFCJHBG。6.24画出和下列已知序列对应的森林F： 森林的先根次序访问序列为ABCDEFGHIJKL 树的后跟次序访问序列为CBEFDGAJIKLH。6.25证明：在结点数多于1的哈夫曼树中不存在度为 1的结点。6.26 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别是0.07。0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫编码，使用07的二进制表示形式是另一种编码方案，对于上述实例，比较这两种方案的优缺点。6.27假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出树。6.28假设一棵二叉树的中序序列为D CBGEAHFIJK和后序序列为DCEGBFHKJIA。请画出树。6.29假设一棵二叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出树。6.30证明：树中结点u 是结点v的祖先，当且仅当在先序 序列中u在v之前，且在后序序列中u在v之后。6.31证明：由一棵二叉树的先序序列和中序序列可唯一确定这棵二叉树。6.32证明；如果一棵二叉树的先序序列是u1，u2. un 中序序列为up1 up2.upp 则序列1,2,.,n可以通过一个栈得到序列 p1，p2. pn ;反之,若以上述中的结论作为前提,则存在一棵二叉树,若其前序序列是u1，u2. un ,则其中序序列为 up1 up2.upp. 算法设计题 6.33假定用两个一维数组L1n和R1.n作为有n个结点的二叉树的存储结构,Li和Ri分别指出结点i的左孩子和右孩子,0表示空,试写一算法判别结点是否为结点V的子孙.6.34同6.33题条件。先由L和R建立一维数组T1n,使T中第 i ( i=1,2,n )个分量指示结点i 的双亲,然后写判别结点u是否为结点v的子孙的算法.6.35 假设二叉树中左分支的标号为”0”,右分支的标号为”1”,并对二叉树增设一个头结点,令根结点为其右孩子,则从头结点到树中任一点所经分支的序列为一个二进制序列,可以作是某个十进制数的二进制表示.例如,右图所示二叉树中,和节点A对应的二进制序列为”110”,即十进制整数6的二进制表示,已知一棵非空二叉树以顺序存储结构表示,试写一尽可能简单的算法,求出与树的顺序存储结构中下标值为i 的结点对应的十进制数.以下6.36至6.38和6.41至6.53题中,均以二叉链表作为二叉树的存储结构.6.36若已知两棵二叉树B1和B2皆为空,或者皆不为空且B1的左右子树 和B2的左子树分别相似,则称二叉树B1和B2相似,试编写算法,判别给定两棵二叉树是否相似.6.37试利用栈的基本操作写出先序遍历的非递归形式的算法。6.38同6.37条件，写出后序遍历的非递归形式的算法（提示：为分辨后序遍历时两次进栈的不同返回点，需在指针进栈时同时将一个标志进栈）。6.39若在二叉链表的结点中增设两个域：双亲域（parent）以指示其双亲结点，标志域（mark取值0.2）以区分在遍历过程中达到该结点时应继续向左或向右或访问该结点，试以存储结构编写不用栈进行后序遍历的递推形式的算法。6.40若在二叉链表的结点中只增设一个双亲域以指示其双亲结点，则在遍历过程中能否不设栈？试以存储结构编写不设栈进行中序遍历的递推形式的算法。6.41编写递归算，在二叉树中求位于先序序列中第k个位置的结点的值。6.42编写递归算法，计算二叉树中叶子结点的数目。6.43编写递归算法，将二叉树中所有结点的左、右子树相互交换。6.44编写递归算法，求二叉树中以元素值为x 的结点为根的子树的深度。6.45编写递归算法，对于二叉树中的每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。6.46编写复制一棵二叉树的非递归算法。6.47已知在二叉树中，*root 为根结点，*p和*q为二叉树中的两个结点，试编写求距离它们最近的共同祖先的算法。6.48编写按层次顺序中（同一层自左向右）遍历二叉树的算法。6.49编写算法判别给定二叉树是否为完全二叉树。6.50假设以三元组（F，C，L/R）的形式输入一棵二叉树的诸边（其中F表示双亲结点的标识，C表示孩子结点标识，L/R表示C为F的左孩子或右孩子），且在输入的三元组序列中，C是按层次顺序出现的，设结点的标识是字符型，F=时C为根结点标识，若C也为，则表示输入结束，例如，6.15题所示二叉树的三元组序列输入格式为： ALABLACRBDLCELCFRDGRFHLL试编写算法，由输入的三元数组序列建二叉树的二叉链表。6.51编写算法，输出以二叉树表示的算术表达式，若该表达式中含有括号，则在输出时应添上。6.52一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积，试写一算法求二叉树的繁茂度。6.53试编写算法，求给定二叉树上从根结点到叶子结点的一条其路径长度等于树的深度减一的路径（即列出从根结点到该叶子结点的结点序列），若这样的路径存在多条，则输出路径终点（叶子结点）在“最左”的时间复杂度。6.54已知一棵完全二叉树存于顺序表sa中，sa.elm1.sa.last含结点值。试编写算法由此顺序存储结构建立该二叉树的二叉链表。6.55二叉链表的结点增加DescNum域，试编写算法，求二叉树的每个结点的子孙数目并存入其DescNum域。请给出算法的 时间复杂度。6.56试写一个算法，在先序后继线索二叉树中，查找给定结点*p在先序序列中的后继（假设二叉树的根结点未知）。并讨论实现此算法对存储结构有何要求？6.57试编写一算法，在后序后继线索二叉树中 ，查找给定结点*p在后序序列中的后继（二叉树的根结点指针并为给出），并讨论实现算法对存储结构有何要求？6.58试写出一算法，在中序全线索二叉树的结点*p之下，插入一棵以结点*x为根只有左子树的中序全线索二叉树，使*x为根的二叉树成为*p的左子树，若*p原来有左子树，则令它为*x 的右子树，完成插入之后的二叉树应保持全线索化特性。6.59试编写算法完成下列操作：无重复的输出以孩子兄弟链表存储的树T中所有的边。输出的形式为（k1 k2），（ki kj）. （ki kj）其中，ki， kj 为树结点中的结点标识。6.60试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。6.61试编写算法，求一棵以孩子-兄弟链表表示的树的深度。6.62对以孩子-兄弟链表表示的树编写计算树的深度的算法。6.63对以双亲表示的树编写计算树的深度的算法。6.65已知一棵二叉树的前序虚痨和中序序列分别存储于两个一维数组中，试将编写算法建立该二叉树的二叉链表。6.66假设有n个结点的树T采用了双亲表示法，写出由此建立树的孩子-兄弟链表的算法。6.67假设以二元组（F，C）的形式输入一棵树的诸边（其中F表示双亲结点的标识，C表示孩子结点标识），且在输入的二元组序列中，C是按层次顺序出现的，F=时 C为根结点标识，若C也为，则表示输入结束，例如，如下所示树的输入序列为： A AB AC AD CE CF 试编写算法，由输入的二元组序列建立树的孩子-兄弟链表。6.68已知一棵树的由根至叶子结点按层次输入的结点序列及每个结点的度（每层中自左向右输入），试写出构造此树的孩子-兄弟链表的算法。6.69假设以二叉链表存储的二叉树中，每个结点所含数据元素均为单字母，试编写算法，按树状打印二叉树的算法，例如：左下二叉树印为右下形状， CFEADB 6.70如果用大小写字母标识二叉树结点，则一棵二叉树可以用符合下面语法图的字符序列表示，试写一个递归算法，有这种形式的字符序列，建立相应的二叉树的二叉链表存储结构。 例如：6.69题所示二叉树的 输入形式为A（B（#，D），C（E（#，F），#）。 6.71 假设树上每个结点所含的数据元素为一个字母，并且以孩子-兄弟链表为树的存储结构，试写一个按凹入表方式打印一棵树的算法，例如；左下所示树印为右下形状。 A BEFCGD6.72以孩子链表为树的存储结构，重做6.71题。6.73若用大写字母标识树的结点，则可利用带标号的广义表形式表示一棵树，其语法图如下：