(1)哪个是根结点？ (2)哪些是叶子结点？
(3)哪个是结点G的双亲？ (4)哪些是结点G的祖先？ (5)哪些是结点G的孩子？ (6)哪些是结点E的子孙？
(7)哪些是结点E的兄弟？哪些是结点F的兄弟？ (8)结点B和N的层次号分别是什么？ (9)树的深度是多少？
(10)以结点C为根的子树的深度是多少？
4．将算术表达式((a+b)+c*(d+e)+f*(g+h)转化为二叉树。
5. 一棵二叉树的结点数据采用顺序存储结构，存储于数组BT中，如题表6-1所示。画出该二叉树的链接表示形式。数组BT的存放形式是相对于满二叉树中编号为数组下标值的结点值。若该结点不存在，则取0值。
6．假设前序遍历某棵树的结点次序为SACEFBDGHIJK；后序遍历该树的结点次序为CFEABHGIKJDS，请画出这棵树。 7．已知一棵树如题图6-5所示，将其转换为其孩子兄弟表示的二叉树。并画出该二叉树的后序线索二叉树。 8．试找出分别满足下列条件的所有二叉树： (1)前序遍历序列和中序遍历序列相同。 (2)中序遍历序列和后序遍历序列相同。 (3)前序遍历序列和后序遍历序列相同。
9．已知信息为“ABCD BCD CB DB ACB”，请按此信息构造哈夫曼树，求出每一字符的最优编码。 10.己知中序线索二叉树采用二叉链表存储结构，链结点的构造为：
6 / 17
其中若ltag为0，则lchild指向结点的前驱，否则lchild指向左孩子结点；若rtag为0，则rchild指向结点的后继，否则rchild指向右孩子结点。下面的算法返回x所指结点的直接后继结点的位置。若该算法有错，则请改正错误；若无错，请写“正确”二字。
BiTree INSUCC (BiTree x) { s=X->rchild; if（s->rtag）
while （s->ltag） s=s->rchild; return s； )
五、算法设计题
1．编写对二叉树进行中序遍历的非递归算法，并对算法执行题图6-6所示的二叉树的情况进行跟踪（即给出各阶段栈的变化及输出的结点序列）。 栈已经定义：InitStack(S)（初始化）、Empty(S)（判栈空）、Push(S，p)（入栈）、Pop(S，p)（出栈）等操作。
2．假设在表示一棵二叉树的二叉链表上增加两个域：双亲域用于指示其双亲结点，标志域flag（可取0...2）的值，用以区分在遍历过程中到达该结点时继续向右或向左或访问该结点。试以此存储结构编写不用栈进行后序遍历的递归形式的算法。
3．一棵具有n个结点的完全二叉树，以一维数组作为存储结构，试设计一个对该完全二叉树进行前序遍历的算法。 4．设中序线索树的结点由5个域组成。 Info：给出结点的数据域。 LT:标志域，为0或1。
LL：当LT为1时，给出该结点的左孩子的地址。 当LT为0时，给出按中序遍历的前驱结点地址。 RT:标志域，为0或1。
7 / 17
RL：当 RT为1时，给出该结点的右孩子的地址。 当RT 为O时，给出按中序遍历的后继结点地址。
请编写 程序，在具有上述结点结构的中序线索二叉树上，求某一结点p按后序遍历次序的后继结点的地址q，设该中序线索二叉树的根结点地址为r。 另外，请注意必须满足：
(l)额外空间的使用只能为O(1)。 (2)程序为非递归形式。
5．假设二叉树采用链接方法存储，编写一个函数按凹入表表示法打印出该二叉树。
6．给出中序线索树的结点结构，设计算法在不使用栈和递归的情况下前序遍历一棵中序线索树，并分析它的时间复杂度。 7．以二叉链表为存储结构，写出交换各结点左右子树的算法。
8．假设二叉树采用链接方法存储，编写一个函数按凹入表表示法打印出该二叉树。
第六章 树和二叉树
第6章树和二叉树
一、选择题（参考答案）
1．B 2．B 3．C 4．A，C 5．C 6．C 7．A 8．B 9．A，B
10. (1)C (2)A (3)C (4)A (5)C (6)A (7)C 11．B 12.A 13．B 14．A 15．B 16．D 17．A 18．C 19．D 20．D 二、填空题（参考答案） 1．树的总结点数-1。
2．前驱：1，后继，任意多个。
3. kl, k2, k4, k5, k7,2,k5, k6, kl,3,4。 4.3，4，6，1，1，2，A，F，G。
i-l
5.(1) k, (2) ?
? , (3) n-l×k+n+1,(4)i≠nk+l(n=0,l,2，…),n+1.
6．前序遍历，中序遍历。 7．前序，中序，后序，前序，后序。 8. 2i-1， 「2/n, ?2/n?. 9.6个。
8 / 17
10. 160 11. 2n，n-l，n+l。 12．A
13.树可采用二叉树的存储结构并可利用二叉树的已有算法解决树的有关问题。 14.只有1个结点的树，空树。 15.I，F。 16.前序遍历序列为：EACBDGF，森林包括1棵树。
17. HIDJKEBLFGCA0 18. 2n-l。
19. 560 20．n+l。
21.顺序存储和链式存储，双亲链表表示法，孩子链表表示法，孩子兄弟链表表示法 三、判断题
1. √ 2. √ 3. √ 4.× 5. √ 6.× 7.× 8. √ 9.× 10.× 四、算法和操作题
1．假设一棵二叉树广义表表示为a(b(c)，d(e，D)，分别写出对它进行前序、中序、后序遍历的结果。 【解答】前序：a，b，c，d，e，D 中序：c，b，a，e，d，D 后序：c，b，e，D，d，a
2．已知一棵二叉树的中序和后序序列，求该二叉树的高度和双支、单支及叶子结点数。 【解答】中序序列：c，b，d，e，a，g，i，h，j，f 后序序列：c，e，d，b，i，j，h，g，f，a
由中序和后序（前序）遍历序列可惟一确定一棵二叉树，基本思想是后序（前序）定根，中序分左右。由后序序列可知该树的根结点为a，由中序遍历序列可知该树的左子树为{c，b，d，e}，右子树为{g，i，h，j，f）;再由后序序列可知该树的左子树的根结点为b，右子树的根结点为f．再由中序遍历序列可知b结点的左子树为{c}，右子树为{d，e）;再由后序遍历序列可知右子树{d，e}的根结点为d，再由中序遍历序列可知d的左子树为空，右子树为{e}。对以f为根结点的子树可做类似的分析。最后得到由中序和后序序列决定的二叉树为：
a(b(c，d(，e))，f(g(，h(i，j))))，由此可知该树：
高度：5 双分支：3 单分支：3 叶结点：4。
3．已知一棵树边的集合为{
【解答】根据边集画出的树如下所示：
(1)根结点是：A。
(2)叶子结点是：D，M，N，F，J，K，L。
9 / 17
(3)结点G的双亲是：C。 (4)结点G的祖先是：A，C。 (5)结点G的孩子是：J，K。 (6)结点E的子孙是：I，M，N。
(7)结点E的兄弟是：D;结点F的兄弟是：G，H。 (8)结点B和N的层次号分别是：2，5。 (9)树的深度是：5。
(10)以结点C为根的子树的深度是：3。
4．将算术表达式((a+b)+c*(d+e)+f*(g+h)转化为二叉树。 【解答】转化成如下二叉树：
5．-棵二叉树的结点数据采用顺序存储结构，存储于数组BT中，如题表6-1所示。画出该二叉树的链接表示形式。数组BT的存放形式是相对于满二叉树中编号为数组下标值的结点值。若该结点不存在，则取0值。
题表6-1
【解答】二叉树的链式表示为：
6．若前序遍历某树的结点次序：SACEFBDGHIJK;后序遍历的结点次序为： CFEABHGIKJDS，画出这棵树。 【解答】画出树如下：
10 / 17
数据结构课后习题标准答案第六章
