不完整的二叉樹作爲數組

Question

在大學裏，我們被問及如何將不完整的二叉樹存入數組。 索引對於左邊的孩子是2i + 1，對於頂點的右邊的孩子是2i + 2。 （（i - 1）/ 2）爲父節點。 現在的第一個問題是我們如何表示「缺失」的頂點。

我認爲這可以通過將「null」保存到數組中來實現。有沒有解決方案？

第二個問題是，我清楚地不知道該怎麼回答。有人問，爲什麼沒有人會真正做到這一點，如果我們從這樣的第一個問題來解決問題，就會出現嚴重的問題。

感謝您的幫助。

Answer 1

如何表示缺少的頂點的答案取決於您的語言。在Java中，如果你的數組是對象之一，你肯定可以使用null。如果它是一個基元數組，而不需要某種可以表示空值的標記值。如前所述，使用數組來表示一個非完整的二叉樹可能會浪費，這取決於您的樹的結構。

第二個問題的答案可能是上述內存問題。如此說來，還有其他一些方法可以將不完整的樹存儲在數組中，這些數組對於內存的濫用程度較低，但比簡單的「2i + 1處的左邊的孩子和2i + 2處的右邊的孩子」要複雜得多。