Question

一棵含有n个节点二叉树的结点数据采用顺序存储结构,在最坏的情况下浪费？？个空间.

Answer 1

最坏的情况就是这个二叉树是单支数。 比如有 k 层，它的节点数字也是 k 。
那么它需要 2^K - 1 长度的数组来存放，而实际上它只有 k 个节点。
为什么会这样呢？因为二叉树的顺序存储是相对完全二叉树而言的。
对于一般的二叉树，如果相对于二叉树没有这个节点，也要在数组中的对应位置存放一个标识，表示没有该节点。