数据结构习题及解析第6 章树和二叉树基础知识题6.1①已知一棵树边的集合为{ <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为根的子树的深度是多少？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的结点,…n k个度为k 的结点,问该树中有多少个叶子结点?6.6③已知在一棵含有n个结点的树中,只有度为k的分支结点和度为0的叶子结点.试求该树含有的叶子结点的数目.6.7③一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？6.8④证明：一棵满k叉树上的叶子结点数n0和非叶子结点数n1 之间满足以下关系：n0 =（k - 1）n1+ 16.9②试分别推导出含有n个结点和含有n0个叶子结点的完全三叉树的深度H。

6.10④对于那些所有非叶子结点均有非空左右子树的二叉树：（1）试问：有n个叶子结点的树中共有多少个结点？（2）试证明：∑2-（l i-1）=1 其中n 为叶子节点的个数，l i表示第i 个叶子节点所在的层次（设根结点所在层次为1）。

6.11③在二叉树的顺序存储结构中，实际上隐含这双亲的信息，因此可和三叉链表对应。

假设每个指针域占4个字节的存储，每个信息域占k 个字节的存储，试问：对于一棵有n 个结点的二叉树，且在顺序存储结构中最后一个结点的下标为m ，在什么条件下顺序存储结构比三叉链表更节省空间？6.12② 对应6.3所得各种形态的二叉树，分别写出前序、中序、后序遍历的序列。

6.13② 假设n 和m 为二叉树中二结点，用“1”、“0”或“φ”（分别表示肯定、恰恰相反或者不一定）填写下表：注意：如果（1）离a 和 b 最近的共同祖先p 存在且（2）a 在p 的左子树中，b 在p 的右子树中，则称a 在b 的左方（即b 在a 的右方）。

6.14② 找出所有满足下列条件的二叉树；（a ） 它们在先序遍历和中序遍历时，得到的结点访问序列相同； （b ） 它们在后序遍历和中序遍历时，得到的结点访问序列相同；（c ） 它们在先序遍历和后序遍历时，得到的结点访问序列相同；6.15②请对右图所示二叉树进行后序线索化，为每个空指针建立相应的前驱或后继线索。

6.16②将下列二叉链表改为先序线索链表（不画出树的形态）。

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个字母设计哈夫编码，使用0——7的二进制表示形式是另一种编码方案，对于上述实例，比较这两种方案的优缺点。

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…. u n 中序序列为u p1 u p2…..u p p则序列1,2,…..,n可以通过一个栈得到序列p1，p2…. p n ;反之,若以上述中的结论作为前提,则存在一棵二叉树,若其前序序列是u1，u2…. u n ,则其中序序列为u p1 u p2…..u p p.算法设计题6.33③假定用两个一维数组L[1…n]和R[1..n]作为有n个结点的二叉树的存储结构,L[i]和R[i]分别指出结点i的左孩子和右孩子,0表示空,试写一算法判别结点是否为结点V的子孙.6.34③同6.33题条件。

先由L和R建立一维数组T[1…n],使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题所示二叉树的三元组序列输入格式为：＾ALABLACRBDLCELCFRDGRFHL＾＾L试编写算法，由输入的三元数组序列建二叉树的二叉链表。

6.51⑤编写算法，输出以二叉树表示的算术表达式，若该表达式中含有括号，则在输出时应添上。

6.52④一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积，试写一算法求二叉树的繁茂度。

6.53⑤试编写算法，求给定二叉树上从根结点到叶子结点的一条其路径长度等于树的深度减一的路径（即列出从根结点到该叶子结点的结点序列），若这样的路径存在多条，则输出路径终点（叶子结点）在“最左”的时间复杂度。

6.54③已知一棵完全二叉树存于顺序表sa中，sa.elm[st]含结点值。

试编写算法由此顺序存储结构建立该二叉树的二叉链表。

6.55④二叉链表的结点增加DescNum域，试编写算法，求二叉树的每个结点的子孙数目并存入其DescNum域。

请给出算法的时间复杂度。

6.56③试写一个算法，在先序后继线索二叉树中，查找给定结点*p在先序序列中的后继（假设二叉树的根结点未知）。

并讨论实现此算法对存储结构有何要求？6.57③试编写一算法，在后序后继线索二叉树中，查找给定结点*p在后序序列中的后继（二叉树的根结点指针并为给出），并讨论实现算法对存储结构有何要求？6.58试写出一算法，在中序全线索二叉树的结点*p之下，插入一棵以结点*x为根只有左子树的中序全线索二叉树，使*x为根的二叉树成为*p的左子树，若*p原来有左子树，则令它为*x 的右子树，完成插入之后的二叉树应保持全线索化特性。