二叉树的数组放置

Question

我正在学习二叉树。我正在练习一个问题论文，并且遇到了这个问题，我不确定我的答案是否正确，所以我想问问你们对此的意见。 （！不是赋值）

比方说，有这个二叉树： - [？] [？] [？] [？] [？]

 1 
    /\ 
    2 3 
    /
    4 
     \ 
     5 

在给定数组中什么指数[1] [？] [？] [？]

将'4'放置？

我的答案我以为是在第三指数（如果我们认为该数组为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