一棵二叉树如右图所示,若采用顺序存储结构,即用一维数组元素存储该二叉树中的结点,则该数组的最大下标至少为?

2021年9月19日 | 分类: 【编程】

【题目】

一棵二叉树如右图所示,若采用顺序存储结构,即用一维数组元素存储该二叉树中的结点(根结点的下标为1,若某结点的下标为 \(i\) ,则其左孩子位于下标 \(2i\) 处、右孩子位于下标 \(2i+l\) 处),则该数组的最大下标至少为()。

     o
    / \
   o   o
      / \
     o   o
        / \
       o   o

A. 6
B. 10
C. 15
D. 12

【考点】

二叉树(重点)

高度

结点数量

叶子节点数量

下一层数量是上一层的2倍

每层的数量:\(2(i−1)\)

总数量:\(2^i−1\)

完美二叉树(满二叉树)

完全二叉树:完美二叉树从右往左去掉一些叶子结点

【解析(2)】

堆式编号。

最大值是最深的那层最靠右侧的节点。

总共4层,从题目中给定的算式:

第1层:根节点,根结点的下标为1
第2层:右孩子位于下标 \(2i+l\) ,即 \((1*2+1)\)
第3层:右孩子位于下标 \(2i+l\) ,即 \([(1*2+1)*2+1]\)
第4层:右孩子位于下标 \(2i+l\) ,即 \(\{[(1*2+1)*2+1]*2+1\}\)

\(ans=\{[(1*2+1)*2+1]*2+1\}=15\)

【解析(2)】

\(ans=2^4−1=15\)