四叉树的有关问题

四叉树的问题
一个包含n个结点的四叉树，每一个节点都有4个指向孩子节点的指针，这4n个指针有（3*n+1）个空指针.
4*n-(n-1) = 3*n+1
为什么
------解决方案--------------------
因为每个树都有一个头结点。头结点下面是4个子结点，然后每个子结点又有4个子节点。
例如一个2层的四叉树，就会有5个结点，但头结点并不能计算进去。他的4个子节点下面接的都是空指针，可以得出空指针的个数为4*4=16个。这个时候n=5，则4*n-(n-1)=4*5-(5-1)=16。


















































------解决方案--------------------
最简单的理解就是，n个节点一定就有4n个指针。
除了root节点，所有的节点都用了一个指针，就是用了n-1个
所以答案就是 4n -n +1 = 3n +1 
------解决方案--------------------
等比数列求和公式可以用在这里，很容易算出最后一层的节点数是(3n+1)/4
然后空指针数再＊4
http://baike.baidu.com/link?url=HXEsRDz6ys1KJ5EVGaavIS4o7SB2acCYM76pK9t6Vt6fwBL61s0xbEVsKNPTcqtzMQ1zWWHWTMJ-_n75xU4rNq