🏷️ 知识点：Ds.05.02.02

一棵有n个结点的二叉树采用二叉链存储结点，其中空指针数为（ ）。

A. n B. n+1 C. n−1 D. 2n

[tag_link]

correct answer: B

结论

二叉链共有2n个指针域，非空边n−1，空指针为2n−(n−1)=n+1。

推导

二叉链共有2n个指针域，非空边n−1，空指针为2n−(n−1)=n+1。

易错点

空指针数不是n−1，后者是非空边数。

设有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。

易错点

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

在一个用数组表示的完全二叉树中，根结点下标为1，下标17和19结点的最近公共祖先下标是（ ）。

A. 1 B. 2 C. 4 D. 8

[tag_link]

correct answer: C

结论

17的祖先为8、4、2、1，19的祖先为9、4、2、1，最近公共祖先下标为4。

推导

17的祖先为8、4、2、1，19的祖先为9、4、2、1，最近公共祖先下标为4。

易错点

父下标为⌊i/2⌋（根下标1）。

具有n个结点的三叉树用三叉链表表示，则树中空指针域的个数为（ ）。

A. 3n+1 B. 2n+1 C. 3n−1 D. 3n

[tag_link]

correct answer: B

结论

三叉链有3n个指针域，树边n−1个非空，空域=3n−(n−1)=2n+1。

推导

三叉链有3n个指针域，树边n−1个非空，空域=3n−(n−1)=2n+1。

易错点

不要把三叉链误当二叉链。

已知一棵二叉树按顺序存储结构进行存储，设计一个算法，求编号分别为i和j的两个结点的最近公共祖先结点的值。

[tag_link]

参考答案

采用1基顺序存储，先验证i、j对应结点存在；反复将较大编号替换为floor(index/2)，直到i=j，返回T[i]。

推导过程

顺序二叉树中结点的双亲编号为floor(k/2)。循环每次提升较深结点，编号相等时即为最近公共祖先；若任一位置为空则报告结点不存在。

评分要点

验证存在性；使用floor(k/2)逐级上移；处理根/相等/不存在边界。

易错点

混用0基父子公式，或只比较一次父结点。