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

admin2018-09-03 46

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

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

答案C

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

二叉链表中每个节点有2个指针，一共有2k个指针。在二叉树中除了根节点之外，其他的节点都有一条边进入该节点，即一个指针指向该节点，所以二叉树中边的总个数为k-1，也就说明非空指针的个数为k-1个。那么空指针的个数为：总的节点数-非空指针的个数=2k-(k-1)=k+1。

转载请注明原文地址:https://www.kaotiyun.com/show/MuRZ777K

软件设计师上午基础知识考试

相关试题推荐

随机试题

最新回复(0)