3.6 习题答案

1. D 2. D 3. D 4. D 5. B 6. C 7. C 8. B 9. F,B 10. B 11. C
12. D 13. D 14. B 15. C 16. C

17 树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解
释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。

树和二叉树的区别有三：一是二叉树的度至多为2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下， 也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。

20 (1)根据二叉树度为2 结点个数等于叶子结点个数减1的性质，故具有n个叶
子结点且非叶子结点均有左左子树的二叉树的结点数是2n-1。
(2)证明：当i=1时，2-（1-1）=20=1，公式成立。设当i=n-1时公式成立，证明当i=n时公式仍成立。
设某叶子结点的层号为t，当将该结点变为内部结点，从而再增加两个叶子结点时，这两个叶子结点的层号都是t+1，对于公式的变化，是减少了一个原来的叶子结点，增加了两个新叶子结点，反映到公式中，因为2-(t-1)=2-(t+1-1)+2-(t+1-1)，所以结果不变，这就证明当i=n时公式仍成立。证毕。
21 由二叉树的前序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右
子树两部分。例如，任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。


（2）设二叉树的前序遍历序列为P1，P2，...，Pm，中序遍历序列为S1,S2,...，Sm。因为前序遍历是"根左右"，中序遍历是"左根右"，则前序遍历序列中第一个结点是根结点（P1）。到中序序列中查询到Si=P1,根据中序遍历时根结点将中序序列分成两部分的原则，有：
若i=1，即S1=P1，则这时的二叉树没有左子树; 否则，S1,S2,...,Si-1是左子树的中序遍历序列,用该序列和前序序列P2,P3，...，Pi去构造该二叉树的左子树。
若i=m,即Sm=P1,则这时的二叉树没有右子树; 否则,Si+1,Si+2,...，Sm是右子树的中序遍历序列，用该序列和前序序列中Pi+1,Pi+2,...,Pm,去构造该二叉树的右子树。算法描述请参见下面算法设计第56题。

（3）若前序序列是abcd，并非由这四个字母的任意组合（4!=24）都能构造出二叉树。因为以abcd为输入序列，通过栈只能得到1/(n+1)*2n!/(n!*n!)=14 种，即以abcd为前序序列的二叉树的数目是14。任取以abcd作为中序遍历序列，并不全能与前序的abcd序列构成二叉树。例如：若取中序列dcab就不能。
该14棵二叉树的形态及中序序列略。
23 采用前序和后序两个序列来判断二叉树上结点n1必定是结点n2的祖先。
在前序序列中某结点的祖先都排在其前。若结点n1是n2的祖先,则n1必定在n2之前。而在后序序列中，某结点的祖先排在其后，即若结点n1是n2的祖先，则n1必在n2之后。根据这条规则来判断若结点n1在前序序列中在n2之前，在后序序列中又在n2之后，则它必是结点n2的祖先。

[算法讨论]完全二叉树证明还有其它方法。判断时易犯的错误是证明其左子树和右子数都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。

28 [题目分析] 由于以双亲表示法作树的存储结构，找结点的双亲容易。因此我
们可求出每一结点的层次，取其最大层次就是树有深度。对每一结点，找其双亲，双亲的双亲，直至（根）结点双亲为0为止。

29 [题目分析]由孩子兄弟链表表示的树，求高度的递归模型是：若树为空，高
度为零；若第一子女为空，高度为1和兄弟子树的高度的大者；否则，高度为第一子女树高度加1和兄弟子树高度的大者。其非递归算法使用队列，逐层遍历树，取得树的高度。

31 [题目分析]带头结点的中序线索树，其头结点的lchild指向二叉树的根结点，
头结点的rchild域指向中序遍历的最后一个结点。而二叉树按中序遍历的第一个结点的lchild和最后一个结点的rchild指向头结点。故从头结点找到根结点后，顺"后继"访问二叉树。在中序线索树中，找前序的后继，已在第65题进行了详细的讨论，这里不再赘述。中序线索树在上面的"四、应用题"已画过多个，这里也不重复。