2. 从业资格
  3. 设某二叉树采用二叉链表表示（即结点的两个指针分别指示左、右孩子）。当该二叉树包含

设某二叉树采用二叉链表表示（即结点的两个指针分别指示左、右孩子）。当该二叉树包含

练习题库2022-08-02  59
问题 设某二叉树采用二叉链表表示（即结点的两个指针分别指示左、右孩子）。当该二叉树包含k个结点时，其二叉链表结点中必有（　　）个空的孩子指针。A.k-1B.kC.k+1D.2k
选项 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://tihaiku.com/congyezige/2410505.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

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