首页 > 试题广场 > 含有n个结点的二叉树采用二叉链表存储时,空指针域的个数为( 
[单选题]

含有n个结点的二叉树采用二叉链表存储时,空指针域的个数为(  ) 。

  • n-1
  • n
  • n+1
  • n+2

n个结点的二叉链表中,有2n个链域,每一条非空链域对应一条树枝,而树支的个数为n-1,因此,空节点个数为2n-(n-1)=n+1
发表于 2019-06-18 18:53:28 回复(0)
C
由n=n0+n1+n2,n0=n2+1,得n=n1+2n2+1;
因为二叉树,所以n1为0或1;
1)当n1为0时,n2=(n-1)/2,空指针:2n-2*(n-1)/2=n+1;
2)  当n1为1时,n2=(n-2)/2,空指针:2n-2*(n-2)/2-1=n+1.
发表于 2019-06-18 16:18:50 回复(0)