题目
一棵二叉树采用链式存储,n个结点的二叉树共有()个指针域为空。A. n-1B. nC. n+1D. 不确定
一棵二叉树采用链式存储,n个结点的二叉树共有()个指针域为空。
A. n-1
B. n
C. n+1
D. 不确定
题目解答
答案
C. n+1
解析
本题考查二叉树链式存储结构中指针域的相关知识。解题思路是先明确二叉树链式存储结构中每个结点的指针域数量,再计算出总的指针域数量,最后根据二叉树中边(即非空指针域)的数量与结点数量的关系,求出空指针域的数量。
步骤一:计算总的指针域数量
在二叉树的链式存储结构中,每个结点都有两个指针域,分别指向左孩子和右孩子。已知二叉树有 $n$ 个结点,那么总的指针域数量为每个结点的指针域数量乘以结点的总数,即:
$2\times n = 2n$
步骤二:计算非空指针域的数量
在二叉树中,除了根结点外,每个结点都有一个父结点,也就是每个结点都对应一条从父结点指向它的边,而每条边对应一个非空指针域。所以,非空指针域的数量比结点的数量少 $1$,即非空指针域的数量为 $n - 1$。
步骤三:计算空指针域的数量
空指针域的数量等于总的指针域数量减去非空指针域的数量,即:
$2n-(n - 1)=2n - n + 1=n + 1$