树和⼆叉树-第6章-《数据结构题集》习题解析-严蔚敏吴伟民版习题集解析部分
第6章树和⼆叉树
——《数据结构题集》-严蔚敏.吴伟民版
先序中序后序遍历二叉树源码使⽤说明链接☛☛☛
课本源码合辑链接☛☛☛
习题集全解析链接☛☛☛
相关测试数据下载链接☛
本习题⽂档的存放⽬录：数据结构\▼配套习题解析\▼06 树和⼆叉树
⽂档中源码的存放⽬录：数据结构\▼配套习题解析\▼06 树和⼆叉树\▼习题测试⽂档-06
源码测试数据存放⽬录：数据结构\▼配套习题解析\▼06 树和⼆叉树\▼习题测试⽂档-06\Data
⼀、基础知识题
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)试证明：，其中n为叶⼦结点的个数，li表⽰第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❷将下列⼆叉链表改为先序线索链表（不画出树的形态）。
1234567891011121314 Info A B C D E F G H I J K L M N
Ltag00010101001111
Lchild246273101412131391011
Rtag00110001110111
Rchild3565891131213140118
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：树的先根次序访问序列为GFKDAIEBCHJ; 树的后根次序访问序列为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❸假设⼀棵⼆叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。请画出该树。
6.29❸假设⼀棵⼆叉树的层序序列为ABCDEFGHIJ和中序序列为DBGEHJACIF。请画出该树。
6.30❹证明：树中结点u是结点v的祖先，当且仅当在先序序列中u在v之前，且在后序序列中u在v之后。
6.31❹证明：由⼀棵⼆叉树的先序序列和中序序列可唯⼀确定这课⼆叉树。
6.32❺证明：如果⼀棵⼆叉树的先序序列是u1，u2，…，un，中序序列是up1，up2，…，upn，则序列1,2，…，n可以通过⼀个栈得到序列p1，p2，…，pn；反之，若以上述中的结论作为前提，则存在⼀棵⼆叉树，若其前序序列是u1，u2，…，un，则其中序序列为up1，up2，…，upn。
⼆、算法设计题
⼆叉树顺序存储
6.33❸假定⽤两个⼀维数组L[n+1]和R[n+1]作为有n个结点的⼆叉树的存储结构，L[i]和r[i]分别指⽰结点i（i=1,2,…,n）的左孩⼦和右孩⼦，0表⽰空。试写⼀个算法判别结点u是否为结点v的⼦孙。
6.34❸同6.33题的条件。先由L和R建⽴⼀维数组T[n+1]，使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、1、2）以区分在遍历过程中到达该结点时应继续向左或向右或访问该结点。试以此存储结构编写不⽤栈进⾏后序遍历的递推形式的算法。
6.40❸若在⼆叉链表的结点中只增设⼀个双亲域以指⽰其双亲结点，则在遍历过程中能否不设栈？试以此存储结构编写不设栈进⾏中序遍历的递推形式的算法。
6.41❸编写递归算法，在⼆叉树中求位于先序序列中第k个位置的结点的值。
6.42❸编写递归算法，计算⼆叉树中叶⼦结点的数⽬。
6.43❸编写递归算法，将⼆叉树中所有结点的左、右⼦树相互交换。
6.44❹编写递归算法：求⼆叉树中以元素值为x的结点为根的⼦树的深度。
6.46❸编写复制⼀棵⼆叉树的⾮递归算法。
6.47❹编写按层次顺序（同⼀层⾃左⾄右）遍历⼆叉树的算法。
6.48❺已知在⼆叉树中，*root为根结点，*p和*q为⼆叉树中两个结点，试编写求距离它们最近的共同祖先的算法。
6.49❹编写算法判别给定⼆叉树是否为完全⼆叉树。
6.50❺假设以三元组（F，C，L/R）的形式输⼊⼀棵⼆叉树的诸边（其中F表⽰双亲结点的标识，C表⽰孩⼦结点标识，L/R表⽰C为F的左孩⼦或右孩⼦），且在输⼊的三元组序列中，C是按层次顺序出现的。设结点的标识是字符类型。F=‘^’时C为根结点标识，若C也为‘^’，则表⽰输⼊结束。例如，6.15题所⽰的⼆叉树的三元组序列输⼊格式为：
试编写算法，由输⼊的三元组序列建⽴⼆叉树的⼆叉链表。
6.51❺编写⼀个算法，输出以⼆叉树表⽰的算术表达式，若该表达式中含有括号，则在输出时应添上。
6.52❹⼀棵⼆叉树的繁茂度定义为各层结点数的最⼤值与树的⾼度的乘积。试写⼀算法，求⼆叉树的繁茂度。
6.53❺试编写算法，求给定⼆叉树上从根结点到叶⼦结点的⼀条其路径长度等于树的深度减⼀的路径（即列出从根结点到该叶⼦结点的结点序列），若这样的路径存在多条，则输出路径终点（叶⼦结点）在“最左”的⼀条。
6.54❸假设以顺序表sa表⽰⼀棵完全⼆叉树，sa.elem[1..sa.last]中存放树中各结点的数据元素。试编写算法由此顺序存储结构建⽴该⼆叉树

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