含n个结点的完全二叉树的深度depth=[log2 (n)]+1 , [x]表示不大于x的最大整数

含n个结点的完全二叉树有多少个叶子结点呢?因为最后一个结点的父结点为[n/2],所以叶子结点为[n/2]+1,[n/2]+2,...,n-1,n,共n-[n/2]个,所以n1=n-[n/2].
如果n为奇数,n1=n-(n-1)/2 => n=2n1-1
如果n为偶数,n1=n-n/2 => n=2n1,代入前式得到结果.

谢谢你，可我问的是满三叉树，是不是把公式里的2换成3就可以了？

这是一个数列问题，深度分别为[log3(2n+1)]+1,[log3(n1)]+2，[X]表示对X取整
对于满3叉数，第Y层含3^(Y-1）个结点，所以深度为x的完全3叉数含的结点数为

N=3^0+3^1+3^2+……+3^(x-2)+k,其中k∈(3^(x-2),3^(x-1)]。化简为

[3^(x-1)-1]/2+k.将k的端点值代入得：N∈([3^(x-1)-1]/2,(3^x-1)/2].令N=n得

到深度X=[log3(2n+1)]+1。
同理，对于深度为X的完全3叉树，也有两种极限情况。一种是最第层全是叶子结

点(即满3叉树)，此时叶子结点数为N=3^(X-1);另一种是最底层只有一个叶子结点

，此时的叶子结点数N=[3^(X-2)-1]+1=3^(X-2).所以N∈[3^(X-2)，3^(X-1)]。令

N=n1得到深度X=[log3(n1)]+2。

我真的不想打击你啊

[quote]我真的不想打击你啊
[/quote]

楼上有何高见。