二叉树结点计算问1、 深度为m的满二叉树有几个结点?2、设二叉树根结点的层次为0...
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。 可以这样计...全部
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)。收起
