計算二叉樹的高度

-1

我想計算二叉樹的高度，而不使用採用每個葉子深度最大值的算法。這是我在eache節點上的結構 [content, left_son, right_son, father_node] 大小爲4的數組的列表，代表每個節點。 left_son，right_son和father分別是列表中左子節點，右子節點和父節點的索引計算二叉樹的高度

來源

2017-03-26 Akram Bendoukha

好像你的運氣了......你必須採取的最大的根據高度的定義考慮每個孩子的身高。 – BeyelerStudios

這確實是可能的，但是您必須重新修改您的數據結構：你可以存儲一個二進制樹在一個這樣的數組：

商店根節點的索引爲0
商店的節點的左子的值在索引2 * i + 1的，其中i是當前節點的索引; 右孩子在指數2 * i + 2去。

如果你不喜歡這樣

節點的父對象被保存在索引（i-1）/ 2。
您的數組需要長度2 ^（h + 1）-1，其中h是樹的高度。

所以你只需要跟蹤數組中最後一個「used」索引並使用上面的公式來計算高度。

2^(h+1)-1 = l => h = ceil(ld(l+1))-1

蒙山L是你的數組的長度您effictively使用和ld與底對數2

來源

2017-03-26 13:32:37

如何管理節點可能沒有右/左子節點，並且在這種情況下需要None值的事實？ –

@Akram Bendoukha：通常一個不存在的節點必須用一個特殊的值來標記，即'null'或-1。如果您期望在數組末尾有「空節點」，我建議通過將索引存儲在一個額外的變量中來追蹤最後填充的條目。這樣你可以直接使用公式。 –

計算二叉樹的高度

回答

相關問題