设有n（n≥1）个结点的二叉树采用三叉链表表示，其中每个结点包含三个指针，分别指向左孩子、右孩子及双亲（不存在则为空），下列说法中正确的是（ ）。 Ⅰ．树中空指针的数量为n+2 Ⅱ．所有度为2的结点均被三个指针所指向 Ⅲ．每个叶结点均被一个指针所指向

A. I B. I、Ⅱ C. I、Ⅲ D. Ⅱ、Ⅲ

[tag_link]

correct answer: A

结论

三叉链非空指针含n−1条孩子边和n−1条双亲边，空域=3n−(2n−2)=n+2；根为度2时仅两指针指向它，故仅I。

推导

三叉链非空指针含n−1条孩子边和n−1条双亲边，空域=3n−(2n−2)=n+2；根为度2时仅两指针指向它，故仅I。

易错点

‘被指向’要区分孩子指针与双亲指针，根结点没有双亲指针。