学步园

 第6章  树和二叉树

一、选择题 

部分答案解释如下。

12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1， 因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。

42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B都不全。由本题可解答44题。

47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。

52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。

二、判断题

部分答案解释如下。

6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。

19．任何结点至多只有左子树的二叉树的遍历就不需要栈。

24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1（2i+1<=n）

37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。

38 . 新插入的结点都是叶子结点。

42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。

44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。

三.填空题

1.(1)根结点(2)左子树(3)右子树        2.(1)双亲链表表示法(2)孩子链表表示法(3)孩子兄弟表示法

3．p->lchild==null && p->rchlid==null      4.(1) ++a*b3*4-cd  (2)18       5.平衡因子

6. 9          7. 12            8.(1)2^k-1 (2)2^k-1         9.(1)2^H-1  (2)2^H-1 (3)H=ëlog₂Nû+1  

10. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条件是ëlog₂sû=ëlog₂tû。

11. ëlog₂iû=ëlog₂jû        12.(1)0  (2)(n-1)/2  (3)(n+1)/2  (4) ëlog₂nû +1        13.n

14. N2+1       15.(1) 2^K+1-1 (2) k+1       16. ëN/2û         17. 2^k-2          18. 64  

19. 99         20. 11                     21.(1) n1-1 (2)n2+n3   

22.(1)2^k-2+1（第k层1个结点，总结点个数是2^H-1，其双亲是2^H-1/2=2^k-2）(2) ëlog₂iû+1        23.69