樹的左孩子右兄弟表示法

左孩子右兄弟表示法是一種不同的 n 元樹表示方法，它不像維護指向每個子節點的指標那樣，一個節點只儲存兩個指標：第一個指標指向它的第一個孩子，另一個指標指向它緊鄰的下一個兄弟。這種新的轉換不僅消除了對節點子節點數量的預先了解的需求，而且還將指標數量限制在最多兩個，從而使程式碼編寫變得簡單得多。

在每個節點上，將具有相同父節點的子節點從左到右連線。

父節點應只與第一個子節點連線。

示例

左孩子右兄弟樹表示法

10
|
2 -> 3 -> 4 -> 5
| |
6 7 -> 8 -> 9

優點

  • 這種表示法透過將每個節點所需的指標最大數量限制為兩個來節省記憶體。
  • 程式碼編寫更簡單。

缺點

  • 諸如搜尋/插入/刪除之類的基本操作會消耗更長的時間，因為為了選擇確切的位置，我們必須遍歷要搜尋/插入/刪除的節點的所有兄弟節點（根據最壞情況）。

更新於：2020年1月2日

676 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告