n个结点的无根树，n-1条边，k个叶子结点，有多少种不同的树？

n{(n-1)*k}

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)

鹏仔微信 15129739599 鹏仔QQ344225443 鹏仔前端 pjxi.com 共享博客 sharedbk.com