二叉树结点计算
1.深度为m的满二叉树有2^m-1个结点.
因为满二叉树的定义为:一颗深度为k且有2^k-1个结点的二叉树称为满二叉树.
2.若要树深为最小,显然要使除最后一层外的每一层都有尽可能多的结点,即要二叉树为完全二叉树.
由二叉树的一个重要性质:具有n个结点的完全二叉树的深度为[log2n]+1.(这是在根节点层次为1时,若为0,将+1去掉即可)
log2n是以2为底n的对数
[log2n]为不大于log2n的最大整数
可知,含有100个(根)结点的二叉树,(应该没"根"字吧)
可能的最小树深为[log2 100 ]+1
二叉树根结点的层次为0时,可能的最小树深为[log2 100 ]
即为6.
可以这样计算:确定最小树深当且仅当二叉树为完全二叉树时出现,设深度为k,(此时设二叉树根结点的层次为0)有:
2^0+2^1+2^2+...+2^(k-1)<100=<2^0+2^1+...+2^k
即2^k-1<100=<2^(k+1)-1
或2^k=<100<2^(k+1) (上下两式是相等的)
其中2^k为完全二叉树的第k层的最多结点个数
解得k=<log2 100<k+1
即k=[log2 100]=6
结点为1000的完全二叉树深度是多少
1.log2(1000)+1=10
2.
1000-(2^9-1)=489
489/2=244,
2^8-244=2,
489+2=491
3.
395/2=197
4.
2*395+1=791
完全二叉树的算法
如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。
可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0=n2+1，则n= n0+n1+n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=(n+1)/2或n0=n/2。
总结起来，就是 n0=[n/2]，其中[]表示上取整。可根据完全二叉树的结点总数计算出叶子结点数。
设有一棵完全二叉树具有1000个结点，问此完全二叉树有多少个叶子结点
完全二叉树度为1的点要么0，要么1。
二叉树有如下性质：N0 =N2 + 1，叶子结点个数为度为2的结点个数+1。
所以1000 = N0 + N1 + N2 ,当N1 = 0时，N0 不为整数，N1 应该等于1，所以N0 = 1000 / 2 = 500
叶子结点个数为500.