一个包含n个节点的四叉树,每个节点都有四个指向孩子节点的指针,这4n个指针中有多少个空指针?
2n+1
3n-1
3n
3n+1
因为每个树都有一个头结点。头结点下面是4个子结点,然后每个子结点又有4个子节点。 例如一个2层的四叉树,就会有5个结点,但头结点并不能计算进去。他的4个子节点下面接的都是空指针,可以得出空指针的个数为4*4=16个。
对于含有N个结点的树,除了头结点外还有N-1个结点,每一个节点都有一条线连接到上一层(由叶到根可以遍历),则共有N-1个指针非空。总的指针数为4N。则空指针为:
4N-(N-1)=3N+1。
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题