二叉樹的存儲結構 - 新聞資訊 - 云南小程序開發(fā)|云南軟件開發(fā)|云南網(wǎng)站建設-昆明葵宇信息科技有限公司

159-8711-8523

云南網(wǎng)建設/小程序開發(fā)/軟件開發(fā)

知識

不管是網(wǎng)站，軟件還是小程序，都要直接或間接能為您產生價值，我們在追求其視覺表現(xiàn)的同時，更側重于功能的便捷，營銷的便利，運營的高效，讓網(wǎng)站成為營銷工具，讓軟件能切實提升企業(yè)內部管理水平和效率。優(yōu)秀的程序為后期升級提供便捷的支持！

二叉樹的存儲結構

發(fā)表時間：2020-10-18

發(fā)布人：葵宇科技

瀏覽次數(shù)：54

1）二叉樹的存儲存儲結構

用一組地址連續(xù)的存儲單元（一維數(shù)組）存儲二叉樹中的結點，必須把結點排成一個適當?shù)木€性序列，并且結點在這個序列中的相互位置能反映出結點之間的邏輯頭系。

對于深度為k完全二叉樹，除第k層外，其余各層中含有最大的結點數(shù)，即每一層的結點數(shù)恰為其上一層結點數(shù)的兩倍。因此，從一個結點的編號可推知其雙親、左孩子和右孩子的編號。

假設有編號為i的結點，則有：

1.若i=1時，該結點為根結點，無雙親。

2.若i>1時，該結點的雙親結點為[（i+1)/2]。

3.若2i≤n,則該結點的左孩子編號為2i，否則無左孩子。

4.若2i+1≤n,則該結點的右孩子編號為2i+1,否則無右孩子。

完全二叉樹的順序存儲結構。

完全二叉樹采用順序存儲既簡單又節(jié)省空間，而一般的二叉樹則不宜用順序存儲結構，因為需要添加一些實際并不存在的虛結點將造成空間的浪費，在最壞情況下，一個深度為k且只有k個結點的二叉樹（單支樹）需要2k-1個存儲單元。

（2）二叉樹的結點包含數(shù)據(jù)元素、左子樹的根、右子樹的根及雙親等信息，因此可以用三叉鏈表或二叉鏈表（即一個結點含有三個指針或兩個指針）來顧念二叉樹，鏈表的頭指針指向二叉樹的根結點。

設結點中的數(shù)據(jù)元素為整型，則二叉鏈表的結點類型定義如下：

typedef struct BiTnode

int data；

在不同的顧念結構中，實現(xiàn)二叉樹的遠算方法是不同的。具體應采用什么存儲結構，除了考慮二叉樹的形態(tài)外，還應考慮需要進行的運算特點。