设一棵完全二叉树中有 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个空指针域
所以有13个节点缺失
所以 空指针域 244*2+6*2+1=501
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题