这棵树最少有2h-1个节点。
分析:考虑按规则构造一棵高度为h的二叉树,可使得其节点数最少。
1、构造一个根节点。
2、为根节点构造2个儿子节点。
3、如果树的高度已经达到H,则结束;否则以上一步的根节点的右儿子最为新的根节点。
除根节点层只有1个结点外,其h-1层都有两个节点。
因此节点总数为2×(h-1)+1=2×h-1。
故这棵树最少有2h-1个节点。
扩展资料
树型结构是一类重要的非线性数据结构,其中以树和二叉树最为常用。一个节点的子树数目称为该节点的度。
例:设一棵完全二叉树具有1000个结点,则此完全二叉树有____个叶子结点,有____个度为2的结点,有____个结点只有非空左子树,有____个结点只有非空右子树。
分析:叶子数=[n/2]=500 ,n2=n0-1=499。
另外,最后一结点为2i属于左叶子,右叶子是空的。
所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况,所以非空右子树数=0。
答:则此完全二叉树有500个叶子结点,有499个度为2的结点,有1个结点只有非空左子树,有0个结点只有非空右子树。