单选题 一个深度为k且只有k个结点的二叉树按照完全二叉树顺序存储的方式存放于一个一维数组R[n]中,则n应至少是______。
  • A.2k
  • B.2k+1
  • C.2k-1
  • D.2k
【正确答案】 C
【答案解析】[解析] 深度为k且只有k个结点的二叉树是一棵单支树。本题需要计算可以保证存储这样一棵二叉树的最小空间,因此要找到所有这种单支二叉树中占用存储空间最大的那一棵,正好对应一棵所有结点的左子树均为空的单枝树,此时的二叉树所需要的存储空间恰恰和与其高度相同的满二叉树相同,需要2k-1个结点单元。