数列问题：一个完全二叉树中，如果叶子结点的个数为n。则这颗二叉树一共有几个结点
一个完全二叉树中，如果叶子结点的个数为n。则这颗二叉树一共有几个结点
http://baike.baidu.com/view/427107.htm
完全二叉树就是结点的深度相差不超过1。
叶子结点就是没有孩子的结点。
经验证，coolisen的答案是正确的。
对于争论。我以为，树是特殊的图，没必要在概念上过于纠结。
我感觉应该是2n-(!(n&1)) （&是二进制按位取与，！是逻辑非）
我问这个问题，是因为当时我想用完全二叉树解决这样的问题：
http://zhidao.baidu.com/question/434826384.html?quesup2&oldq=1
后来发现，建成完全二叉树，程序会很不好处理。
应该建成满2叉树，让叶子节点数为2^(int)log(2,n),多余的用0补齐，这样就完美的解决这个问题了。思路见2楼的追问。
这个周末结贴，大家可以讨论一下
有二叉树基本性质n0=n2+1和总结的个数=n0+n1+n2，=》节点个数=n0+n0-1+n1,即2n0-1+n1
其中n0为度为0的节点，也就是叶子节点，n1为度为1的节点，由于完全二叉树中度为1的节点只有1个，或者没有，并且这两种情况普遍存在，故节点数=2n0-1+1或者2n0-1，由于n0=n，故二叉树共有2n或者2n-1个节点。
其中n0为度为0的节点，也就是叶子节点，n1为度为1的节点，由于完全二叉树中度为1的节点只有1个，或者没有，并且这两种情况普遍存在，故节点数=2n0-1+1或者2n0-1，由于n0=n，故二叉树共有2n或者2n-1个节点。
温馨提示：内容为网友见解，仅供参考
第1个回答 2012-06-11
解：因是完全二叉树，故度数只能是1,2,3.设度数为2的结点为m，则全部结点数为m+n+1
所有度数之和=3m+n+2=边的2倍，另一方面，树中边的数目=结点数-1
所以：3m+n+2=2(m+n)，解得：m=n-2，故全部结点数为2n-1
重新看了上述解答，感觉没错。完全二叉树的概念保证了每个点的出度为2或者0，为2时，该点的度数为3，为0时度数为1，就是叶子。
既然楼主就这样讲了，就再不说什么了，对完全二叉树的概念的描述，很多书上有定义的。
所有度数之和=3m+n+2=边的2倍，另一方面，树中边的数目=结点数-1
所以：3m+n+2=2(m+n)，解得：m=n-2，故全部结点数为2n-1
重新看了上述解答，感觉没错。完全二叉树的概念保证了每个点的出度为2或者0，为2时，该点的度数为3，为0时度数为1，就是叶子。
既然楼主就这样讲了，就再不说什么了，对完全二叉树的概念的描述，很多书上有定义的。
相似回答
