數(shù)據(jù)結(jié)構(gòu)

1、二叉樹兩種存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)順序存儲(chǔ)可能會(huì)浪費(fèi)空間(在非完全二叉樹的時(shí)候)，但是讀取某個(gè)指定的節(jié)點(diǎn)的時(shí)候效率比較高O(0)鏈?zhǔn)酱鎯?chǔ)相對(duì)二叉樹比較大的時(shí)候浪費(fèi)空間較少，但是讀取某個(gè)指定節(jié)點(diǎn)的時(shí)候效率偏低O(nlogn)編寫一個(gè)程序，要求能完成排序和查找，分別使用鏈表，數(shù)組和二叉樹等數(shù)據(jù)結(jié)構(gòu)，比較各種方法的優(yōu)缺點(diǎn)。思路很簡(jiǎn)單，根放在0位置，以后假定當(dāng)前位置是i，那么左子結(jié)點(diǎn)在2i1，右子結(jié)點(diǎn)在2i2。比如根的左子結(jié)點(diǎn)在1，右子結(jié)點(diǎn)在2。結(jié)點(diǎn)1

2、的左子結(jié)點(diǎn)在3，右子結(jié)點(diǎn)在4。定義一種空值表示沒有子結(jié)點(diǎn)，比如empty。假定一個(gè)結(jié)點(diǎn)由3個(gè)成員組成：valueleftright數(shù)組假定是全局的，如果不是可以作為參數(shù)傳送。遞歸實(shí)現(xiàn)比較簡(jiǎn)單：voidbtree2array(nodeindex)if(node==NULL)array[index]=emptyarray[index]=nodevaluebtree2array(nodeleftindex21)btree2array(node

3、rightindex22)互稱為兄弟。圖5.11中，結(jié)點(diǎn)B、C、D都是結(jié)點(diǎn)A的孩子，結(jié)點(diǎn)A是結(jié)點(diǎn)B的雙親，也是結(jié)點(diǎn)C、D的雙親，結(jié)點(diǎn)B、C、D互為兄弟。結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)稱為該結(jié)點(diǎn)的度。圖5.11中，結(jié)點(diǎn)A的度為3，結(jié)點(diǎn)B的度為2，結(jié)點(diǎn)E的度為0。葉結(jié)點(diǎn)、分支結(jié)點(diǎn)：度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，或者稱為終端結(jié)點(diǎn)；度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，或者稱為非終端結(jié)點(diǎn)。圖5.11中，結(jié)點(diǎn)A、B、C、D為分支結(jié)點(diǎn)，結(jié)點(diǎn)E、F、G、H、I