完全二叉树共有2*n-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。