二叉树的数组放置

Question

我正在学习二叉树。我正在练习一份试卷，遇到了这个问题，我不确定我的答案是否正确，所以我想问问你们对此的看法。（不是作业！）

假设有这个二叉树：-

在给定数组中的什么索引 [1][?][?][?][?][?][?][?][?]

'4'会被放置吗？

我认为我的答案是在第 3 个索引处（如果我们认为数组是基于 0 的）但是，我认为这可能不是答案。它比树的某些部分有很多 NULLS 更复杂。

数组应该像这样：- [1][2][3][NULL][NULL][4][NULL][NULL][5] “4”位于第 5 个索引处？

Answer 1

（注意：这在很大程度上取决于二叉树的实现方式。）

对于您绘制的树，并假设您将树隐式地包含在数组中，即您将节点的子节点放在数组中位置 i 的位置 2*i+1 和 2*i+2 分别是：是的，那么 4 将位于索引 5（从 0 开始计数）。

但是，假设以上所有情况并查看您的图片，您在数组中的错误位置有 5 个。 5 应该在索引 12 处。你应该有（使用你的符号）：

[1][2][3][NULL][NULL][4][NULL][NULL][NULL][NULL][NULL][NULL][5]

要查看此内容，请查看其中包含空条目的树

            1
        /       \
     2            3
   /   \       /     \
  N     N     4       N
 / \   / \   / \ 
N  N  N   N N   5

Array placement of Binary Tree