数据结构习题及解析
第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的结点,…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  14
Info
A
B
C
D
E
F
G
H
I
J
K
L
M
N
Ltag
Lchild
2
4
6
0
7
0
10
0
12
13
0
0
0
0
Rtag
Rchild
3
5
0
0
8
9
11
0
0
0
14
0
0
0
  6.17③ 阅读下列算法，若有错，则改之。
BiTree InSucc（BiTree  q）{
// 已知q 是指向中序线索二叉树上某个结点的指针，
// 本函数返回指向*q的后继的指针。
      r= q->rchild;
      if (!r->rtag)
        while (!r->rtag)  r=r->rchild;
      return  r;
  }  //InSucc
6.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…. un 中序序列为up1  up2…..upp  则序列1,2,…..,n可以通过一个栈得到序列  p1，p2…. pn   ;反之,若以上述中的结论作为前提,则存在一棵二叉树,若其前序序列是u1，u2…. un ,则其中序序列为  up1  up2…..upp.
算法设计题
6.33③假定用两个一维数组L[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题所示二叉树的三元组序列输入格式为：
＾ AL
ABL
ACR
BDL
CEL
CFR
DGR
FHL
＾＾L
试编写算法，由输入的三元数组序列建二叉树的二叉链表。
6.51⑤编写算法，输出以二叉树表示的算术表达式，若该表达式中含有括号，则在输出时应添上。
6.52④一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积，试写一算法求二叉树的繁茂度。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。