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

易错点

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