二叉連結串列儲存結構是二叉樹的一種儲存方式。
二叉連結串列是樹的二叉連結串列實現方式。連結串列中結點的兩個鏈域分別指向該結點的第一個孩子結點和第二個孩子結點。二叉樹是邏輯結構,二叉連結串列是二叉樹的物理實現,兩者之間的關係屬於概念和實現,抽象和具體的關係。二叉樹的順序儲存結構由一組連續的儲存單元依次從上到下,從左到右儲存完全二叉樹的結點元素。對於一般二叉樹,應將其與完全二叉樹對應,然後給每個結點從1到i編上號,依次儲存在大小為i到1的陣列中。
二叉連結串列儲存結構是二叉樹的一種儲存方式。
二叉連結串列是樹的二叉連結串列實現方式。連結串列中結點的兩個鏈域分別指向該結點的第一個孩子結點和第二個孩子結點。二叉樹是邏輯結構,二叉連結串列是二叉樹的物理實現,兩者之間的關係屬於概念和實現,抽象和具體的關係。二叉樹的順序儲存結構由一組連續的儲存單元依次從上到下,從左到右儲存完全二叉樹的結點元素。對於一般二叉樹,應將其與完全二叉樹對應,然後給每個結點從1到i編上號,依次儲存在大小為i到1的陣列中。
鏈式儲存結構,又叫連結儲存結構。在計算機中用一組任意的儲存單元儲存線性表的資料元素。這組儲存單元可以是連續的,也可以是不連續的。它不要求邏輯上相鄰的元素在物理位置上也相鄰,因此它沒有順序儲存結構所具有的弱點,但也同時失去了順序表可隨機存取的優點。
1、基於儲存的考慮
順序表的儲存空間是靜態分配的,在程式執行之前必須明確規定它的儲存規模,事先對“MAXSIZE”要有合適的設定,。如果對線性表的長度或儲存規模難以估計時,不宜採用順序表;連結串列不用事先估計儲存規模,但連結串列的儲存密度較低。
2、基於操作的考慮
在順序表中按序號訪問元素的時間效能為O(1),而連結串列中按序號訪問的時間效能是O(n),所以如果經常做的運算是按序號訪問資料元素,顯然順序表優於連結串列;在連結串列中作插入、刪除,也要找插入位置,但是比較操作,顯然連結串列較優。
3、基於開發的語言考慮
順序表容易實現,任何高階語言中都有陣列型別,連結串列的操作是基於指標的,有些語言不支援指標型別,並且相對指標來講順序表較簡單。總之,兩種儲存結構各有長短,選擇那一種儲存方式應由實際問題決定。通常“較穩定”的線性表選擇順序儲存,而頻繁做插入刪除的即動態性較強的線性表宜選擇鏈式儲存。