把二叉樹存放在數(shù)組里

這是一個二叉樹，想一下如何把這個二叉樹存在數(shù)組里？

當(dāng)然，父節(jié)點和子節(jié)點的關(guān)系也需要保存下來。換句話說，存儲在數(shù)組中的數(shù)據(jù)可以再還原出原來的二叉樹。

很簡單，從最上面一層開始，按順序放到數(shù)組里：

這個二叉樹從最頂端的第0層開始，一共有4層。我們來看一下每一層有多少個節(jié)點，然后找到每一層第一個節(jié)點在數(shù)組里的下標(biāo)值。

第0層的節(jié)點數(shù)： 2^0 = 1

第1層的節(jié)點數(shù)： 2^1 = 2

第2層的節(jié)點數(shù)： 2^2 = 4

第3層的節(jié)點數(shù)： 2^3 = 8

嗯，都是2的次方數(shù)

那么每一層的第一個節(jié)點在數(shù)組里的位置是前面所有節(jié)點數(shù)+1， 因為數(shù)組的索引是從0開始的，那么在數(shù)組中的索引位置需要減1:

第0層的第一個節(jié)點索引位置： 0

第1層的第一個節(jié)點索引位置： 2^0 + 1 - 1 = 2^0 = 2^1-1

第2層的第一個節(jié)點索引位置： 2^0+2^1 +1-1= 2^0+2^1= 2^2-1

第3層的第一個節(jié)點索引位置：  2^0+2^1 + 2^2 + 1-1= 2^0+2^1 + 2^2 = 2^3-1

規(guī)律是： 第n層的第一個節(jié)點是索引位置 = 2^n -1     (n = 0,1,2...)

問題：

答案：

因為第n層的第一個節(jié)點是2^n -1, 所以x在第n層。

下面來推導(dǎo)計算第幾層的簡單公式：

堆中父節(jié)點和子節(jié)點的索引變換

如果 i 是節(jié)點的索引， 下面我們來找到它的父節(jié)點和子節(jié)點在數(shù)組中的位置

left(i)  表示二叉樹中i的左子節(jié)點索引位置

right(i)  表示二叉樹中i的右子節(jié)點索引位置

parent(i) 表示二叉樹中i的父節(jié)點索引位置

我們來看一下節(jié)點i的同一層第一個節(jié)點的子節(jié)點。這里i是5，同層第一個節(jié)點是3.

節(jié)點3的左子節(jié)點是7, 也是下一層的第一個節(jié)點。 現(xiàn)在來使用每層第一個節(jié)點的計算公式： 2^n - 1   

也就是左子節(jié)點 = 【該節(jié)點索引值】 乘以【2】 加  【1】

現(xiàn)在從本層的第一個節(jié)點3移動到節(jié)點j (5). 我們注意到：當(dāng)我們在同一層中向右移動節(jié)點時（3到5），因為每個節(jié)點有左右2個子節(jié)點，相應(yīng)的子節(jié)點索引值以2倍的距離移動（7到11）。 

上圖顯示子節(jié)點層的移動距離是父節(jié)點層的2倍

也就是對于一個節(jié)點（5），對于它的左子節(jié)點的索引值依然是 2倍的值加1.

：總結(jié)一下：