資料結構中的二叉樹表示

我們將瞭解如何在計算機記憶體中表示二叉樹。有兩種不同的表示方法：使用陣列和使用連結串列。

假設我們有一棵這樣的樹：

陣列表示法透過使用層序遍歷掃描元素來儲存樹資料。因此它逐層儲存節點。如果某些元素缺失，則為其保留空白空間。上述樹的表示如下：

索引1儲存根節點，它有兩個子節點5和16，它們分別位於位置2和3。一些子節點缺失，因此它們的位置留空。

在此表示中，我們可以使用以下公式輕鬆獲得一個節點的兩個子節點的位置：

$$child_{1}=2*parent$$ 

$$child_{2}=\lgroup2*parent\rgroup+1$$

要從子節點獲取父節點索引，我們必須遵循以下公式：

$$parent=\begin{bmatrix}\frac{child}{2} \end{bmatrix}$$

這種方法很好，我們可以很容易地找到父節點和子節點的索引，但它不是記憶體高效的。它將佔用許多無用的空間。這種表示對於完全二叉樹或滿二叉樹是合適的。

另一種方法是使用連結串列。我們為每個元素建立一個節點。這將如下所示：

Arnab Chakraborty

更新於：2019年8月27日

15K+ 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習