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

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

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

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