设某二叉树采用二叉链表表示(即节点的两个指针分别指示左、右孩子)。当该二叉树包含k个节点时,其二叉链表节点中必有( )个空的孩子指针。

admin2018-09-03  25

问题 设某二叉树采用二叉链表表示(即节点的两个指针分别指示左、右孩子)。当该二叉树包含k个节点时,其二叉链表节点中必有(    )个空的孩子指针。

选项 A、k-1
B、k
C、k+1
D、2k

答案C

解析 所谓二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示着元素的逻辑关系,如下图所示。

二叉链表中每个节点有2个指针,一共有2k个指针。在二叉树中除了根节点之外,其他的节点都有一条边进入该节点,即一个指针指向该节点,所以二叉树中边的总个数为k-1,也就说明非空指针的个数为k-1个。那么空指针的个数为:总的节点数-非空指针的个数=2k-(k-1)=k+1。
转载请注明原文地址:https://kaotiyun.com/show/MuRZ777K
0

相关试题推荐
最新回复(0)