Question

完全二叉树有2*n-1 的节点，则它的叶子节点数为？

Answer 1

完全二叉树的节点数是奇数，说明此完全二叉树也是满二叉树，也就是说每个内部节点正好都有2个叶结点。
设内部节点数为a，叶节点数为b，结点总数为m，明显有a+b=m (1)
非空满二叉树中所有节点的出度正好等于入度，每个内部节点出度为2，叶节点出度为0，所有节点的出度和为2a；根节点入度为0，其他节点的入度为1，所有节点的入度和为a+b-1;因此有2a=a+b-1 (2)
由(1),(2)得 b=(m+1)/2, a=(m-1)/2, b=a+1
也就是说，非空满二叉树的叶节点数正好比内部节点数多1

此完全二叉树的结点总数为2n-1，因此其叶结点数为n。
http://zhidao.baidu.com/question/328594066.html

Answer 2

完全二叉树总节点数：1+2+4+8+…+2^m =1*[1-2^(m+1)]/(1-2) = 2^(m+1) – 1 =2*n-1
即：2^(m+1) =2*n 即 2^m=n 随意叶子节点数为n...