一个二叉树采用二叉链表存储,其中n个结点包含多少个空指针?

答案解析

核心考点:二叉链表存储二叉树的空指针数量。 解题思路分析:二叉树的二叉链表表示中,每个结点有两个指针域,分别指向左孩子和右孩子。除了根节点外,每个结点都会被一个父节点的指针指向。一个n结点的二叉树有2n个指针域,其中n-1个指针指向了结点(即n-1条边),剩下的就是空指针。因此空指针数量为 2n - (n-1) -1,简化后为n+1。 选项分析: A. n-1:这是不正确的,空指针数比结点数多一个。 B. n:这是不正确的,空指针数不等于结点数。 C. n+1:这是正确的,一个n节点的二叉树采用二叉链表表示,有n+1个空指针。 D. 2n:这是不正确的, 2n是总指针数,而不是空指针数。 易错点提醒: 容易忘记考虑根节点没有父指针,导致计算错误。
正确答案:C
随机推荐
开始刷题