首页 软考中级软件设计师正文

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

扫码进入小程序,获取更多软考真题解析

设某二叉树采用二叉链表表示(即结点的两个指针分别指示左、右孩子)。当该二叉树包含k个节点时,其二叉链表节点中必有( )个空的汉子指针。(2017年软件设计师)        
   A.  k-1
   B.  k
   C.  k+1
   D.  2k





参考答案: C
参考解析:二叉树的的二叉链表存储结构中每个结点有2个指针。每个结点有0个、1个或者2个空指针对应有2个、1个、0个非空指针。
二叉树中边的个数等于非空指针的个数。
假设二叉树中节点的总个数为N,
假设二叉树中边的个数为M
假设二叉树中度为0的结点的个数为n0,
假设二叉树中度为1的结点的个数为n1,
假设二叉树中度为2的结点的个数为n2.
所以有 n0+n1+n2=N -------------(1)
二叉树中除了根结点之外,其他的结点都有一条便进入该结点,所以二叉树中边的总个数为M=N-1;-------(2)
又 M=n1+2*n2;-------------------------(3)
所以由 (1)(2)(3)可得 n0=n2+1;--------------------(4)
设空节点的 个数为 K ,则K=2*n0+n1-------------------(5)
结合(1)(4)(5)可以得到 K=N+1. (空指针的的个数比结点总个数多1)
由(2)可以知道 边数M=N-1;(二叉树的边数为结点个数减1)
由(4)可以知道度为0的结点的个数(叶子结点个数)=度为2的结点个数+1 (n0=n2+1;)

扫码进入小程序,获取更多软考真题解析
版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。

本文链接:https://ruankaoti.com/post/866.html

评论

最近发表