二叉樹(shù)的存儲結構
發表時間：2020-10-18
發布人：葵宇科技
浏覽次數：26
1）二叉樹(shù)的存儲存儲結構
用一組地址連續的存儲單元（一維數組）存儲二叉樹(shù)中(zhōng)的結點，必須把結點排成一個(gè)适當的線性序列，并且結點在這個(gè)序列中(zhōng)的相互位置能反映出結點之間的邏輯頭系。
對于深度為k完全二叉樹(shù)，除第k層外，其餘各層中(zhōng)含有最大的結點數，即每一層的結點數恰為其上一層結點數的兩倍。因此，從一個(gè)結點的編号可(kě)推知其雙親、左孩子(zǐ)和(hé)右孩子(zǐ)的編号。
假設有編号為i的結點，則有：
1.若i=1時，該結點為根結點，無雙親。
2.若i>1時，該結點的雙親結點為[（i+1)/2]。
3.若2i≤n,則該結點的左孩子(zǐ)編号為2i，否則無左孩子(zǐ)。
4.若2i+1≤n,則該結點的右孩子(zǐ)編号為2i+1,否則無右孩子(zǐ)。
完全二叉樹(shù)的順序存儲結構。
完全二叉樹(shù)采用順序存儲既簡單又節省空間，而一般的二叉樹(shù)則不宜用順序存儲結構，因為需要添加一些實際并不存在的虛結點将造成空間的浪費，在最壞情況下(xià)，一個(gè)深度為k且隻有k個(gè)結點的二叉樹(shù)（單支樹(shù)）需要2k-1個(gè)存儲單元。
（2）二叉樹(shù)的結點包含數據元素、左子(zǐ)樹(shù)的根、右子(zǐ)樹(shù)的根及雙親等信息，因此可(kě)以用三叉鍊表或二叉鍊表（即一個(gè)結點含有三個(gè)指針或兩個(gè)指針）來顧念二叉樹(shù)，鍊表的頭指針指向二叉樹(shù)的根結點。
設結點中(zhōng)的數據元素為整型，則二叉鍊表的結點類型定義如(rú)下(xià)：
typedef struct BiTnode
int data；
在不同的顧念結構中(zhōng)，實現二叉樹(shù)的遠(yuǎn)算方法是不同的。具體應采用什麼存儲結構，除了考慮二叉樹(shù)的形态外，還應考慮需要進行的運算特點。
