一个包含n个节点的四叉树，每个节点都有四个指向孩子节点的指针

[不定项选择题]

一个包含n个节点的四叉树，每个节点都有四个指向孩子节点的指针，这4n个指针中有多少个空指针？

查看答案及解析

杨浩

因为每个树都有一个头结点。头结点下面是4个子结点，然后每个子结点又有4个子节点。
例如一个2层的四叉树，就会有5个结点，但头结点并不能计算进去。他的4个子节点下面接的都是空指针，可以得出空指针的个数为4*4=16个。

对于含有N个结点的树，除了头结点外还有N-1个结点，每一个节点都有一条线连接到上一层（由叶到根可以遍历），则共有N-1个指针非空。总的指针数为4N。则空指针为：

4N-（N-1）=3N+1。

发表于 2021-08-17 09:24:43 回复(0)

提交观点

问题信息

小米集团测试开发工程师 2021

上传者：小小

难度：

1条回答 31收藏 519浏览

扫一扫，把题目装进口袋