设根结点的层次为0，则高度为k的二叉树的最大结点数为A．2k B．

问题单项选择题

设根结点的层次为0，则高度为k的二叉树的最大结点数为

A．2^k

B．2^k-1

C．2^k+1

D．2^k+1-1

答案

参考答案：D

解析：
二叉树是节点的有限集合，这个有限集合或者为空集，或者由一个根节点及两棵不相交的、分别称作这个根的左子树和右子树的二叉树组成。二叉树的根的左子树和右子树又都是二叉树，它们又都是节点的集合，或者为空集，或者由根节点和左子树、右子树构成，左子树和右子树又都是二叉树，如此递归下去。所以第k层的最大节点数是2^k，二又树的最大节点数为1+2+……+2^{k，即是 2^k+1-1。}