順序儲存結構
該方法是把二叉樹的所有結點按照一定的線性次序儲存到一片連續的儲存單元中。結點在這個序列中的相互位置還能反映出結點之間的邏輯關係。
1．完全二叉樹結點編號
（1） 編號辦法
在一棵n個結點的完全二叉樹中，從樹根起，自上層到下層，每層從左至右，給所有結點編號，能得到乙個反映整個二叉樹結構的線性序列。
【例】如下圖所示。
（2） 編號特點
完全二叉樹中除最下面一層外，各層都充滿了結點。每一層的結點個數恰好是上一層結點個數的2倍。從乙個結點的編號就可推得其雙親，左、右孩子，兄弟等結點的編號。
假設編號為i的結點是ki(1≤i≤n)，則有：
①若i>1，則ki的雙親編號為 ；若i=1，則ki是根結點，無雙親。
②若2i≤n，則ki的左孩子的編號是2i；否則，ki無左孩子，即ki必定是葉子。因此完全二叉樹中編號的結點必定是葉結點。
③若2i+1≤n，則ki的右孩子的編號是2i+1；否則，ki無右孩子。
④若i為奇數且不為1，則ki的左兄弟的編號是i-1；否則，ki無左兄弟。
⑤若i為偶數且小於n，則ki的右兄弟的編號是i+1；否則，ki無右兄弟。
2．完全二叉樹的順序儲存
將完全二叉樹中所有結點按編號順序依次儲存在乙個向量bt[0..n]中。
其中：bt[1．．n]用來儲存結點
bt[0]不用或用來儲存結點數目。
【例】表6.1是圖6.8所示的完全二叉樹的順序儲存結構，bt[0]為結點數目，b[7]的雙親、左右孩子分別是bt[3]、bt[l4]和bt[15]。
3．一般二叉樹的順序儲存
（1） 具體方法
① 將一般二叉樹添上一些 "虛結點"，成為"完全二叉樹"
② 為了用結點在向量中的相對位置來表示結點之間的邏輯關係，按完全二叉樹形式給結點編號
③ 將結點按編號存入向量對應分量，其中"虛結點"用"∮"表示
【例】圖6-9中單支樹的順序儲存結構如下圖
（2） 優點和缺點
① 對完全二叉樹而言，順序儲存結構既簡單又節省儲存空間。
② 一般的二叉樹採用順序儲存結構時，雖然簡單，但易造成儲存空間的浪費。
【例】最壞的情況下，乙個深度為k且只有k個結點的右單支樹需要2k-1個結點的儲存空間。
③在對順序儲存的二叉樹做插入和刪除結點操作時，要大量移動結點。
資料結構二叉樹基本演算法
資料結構實驗報告 實驗四二叉樹儲存結構的應用 實驗內容 二叉樹各種演算法的實現 專業班級 網路工程專業 1002班 組長 賈鑫 2010100234 組員 賈鵬飛 2010100237 鄧桐桐 2010100229 2012年 4月 27日 實驗報告 實驗型別 綜合實驗室 軟體實驗室二一 實驗名稱 ...
資料結構練習二叉樹
學號 31301374 姓名張一博班級軟體工程1301 一 選擇題 1 按照二叉樹定義，具有3個結點的二叉樹共有 c 種形態。a 3 b 4 c 5d 6 2 具有五層結點的完全二叉樹至少有 d 個結點。a 9 b 15 c 31 d 16 3 以下有關二叉樹的說法正確的是 b a 二叉樹的度為2b...
資料結構試驗 二叉樹
實驗報告名稱 姓名學號專業班級 日期實驗6 二叉樹的建立及遍歷 一 實驗目的 1 學會實現二叉樹結點結構和對二叉樹的基本操作。2 掌握對二叉樹每種操作的具體實現，學會利用遞迴方法編寫對二叉樹這種遞迴資料結構進行處理的演算法。二 實驗要求 1 認真閱讀和掌握和本實驗相關的教材內容。2 編寫完整程式完成...