首页 > 试题广场 >

设一棵完全二叉树中有 500 个结点,则该二叉树 的深度为

[填空题]

设一棵完全二叉树中有 500 个结点,则该二叉树 的深度为 1;若用二叉链表作为该完全二叉树的存储结构,则共有2个空指针域。

n个节点的完全二叉树深度为[lbn]+1=lb(500)+1=9.(向下取整)或者lb(n+1)=9(向上取整)。将二叉树中节点从1到500编号,最后一个节点500对应的最后一个双亲节点编号为500/2=250,故有250个叶子节点。又500的双亲节点右孩子节点应该为2*250+1=501,无右孩子节点,故右指针域为空,,共501个空指针域

发表于 2017-06-15 23:02:23 回复(3)
1+2+4+8+16+32+64128245 = 500
这样算深度是9
满二叉树节点总数的公式为:
若第九层全满, 总的节点数应为513

所以有13个节点缺失

所以 空指针域 244*2+6*2+1=501

编辑于 2020-04-04 12:29:59 回复(1)
共500个结点,得完全二叉树的深度为:9。
对于完全二叉树的指针域,有这样一个关系,总指针域=2n(每个结点有2个),非空指针域有n-1个(去掉根节点,根节点没有双亲结点),空指针域有:2n-(n-1)=n+1。
所以共有501个空指针域。
以下是我回顾求叶子结点数的推导,和解这道题没有很大必要关系。
层数和结点数对应为:
第一层 1
第二层 2
第三层 4
第四层 8
第五层 16
第六层 32
第七层 64
第八层 128
第九层 256
若前8层是满二叉树,前8层共有255个结点。
第9层叶子结点数为:500-255=245 则第8层的非叶子结点数,也就是第九层这些叶子结点数的双亲,245/2=123,第八层共有128个结点,所以128-123=5个叶子结点
总叶子结点数=第9层叶子结点数+第8层叶子结点数=245+5=250个叶子结点。
每个叶子结点有2个空指针域,也就是500个空指针域,再加上根结点的1个,是501个。
有一个简单的公式,把总结点数除以2,向下取整,就可以得到完全二叉树的叶子结点数。
比如共500个结点,就有500/2=250个叶子结点。共有99个结点,就有99/2=50个叶子结点。
发表于 2023-04-14 16:21:52 回复(0)
第一问:log2(500)向下取整+1   或者   log2(500+1)向上取整
第二问:空指针数是n+1,这是二叉树的推导,n个节点的二叉树有2n个指针域、有n-1个非空指针,则空指针=2n-(n-1)=n+1
发表于 2023-03-13 11:59:58 回复(0)
发表于 2019-11-05 23:21:02 回复(2)
501怎么算的?有人解释一下吗??二插链表的指针域不是左孩子右兄弟的结构吗??
发表于 2017-06-25 18:57:25 回复(1)