順序存儲結構
該方法是把二叉樹的所有結點按照一定的線性次序存儲到一片連續的存儲單元中結點在這個序列中的相互位置還能反映出結點
之間的邏輯關系
完全二叉樹結點編號
() 編號辦法
在一棵n個結點的完全二叉樹中從樹根起自上層到下層每層從左至右給所有結點編號能得到一個反映整個二叉樹結構的
線性序列
【例】如下圖所示
() 編號特點
完全二叉樹中除最下面一層外各層都充滿了結點每一層的結點個數恰好是上一層結點個數的倍從一個結點的編號就可推得
其雙親左右孩子兄弟等結點的編號假設編號為i的結點是k i (≤i≤n)則有
①若i>則k i 的雙親編號為
;若i=
則K i 是根結點
無雙親
②若i≤n則K i 的左孩子的編號是i;否則K i 無左孩子即K i 必定是葉子因此完全二叉樹中編號
的結
點必定是葉結點
③若i+≤n則K i 的右孩子的編號是i+;否則K i 無右孩子
④若i為奇數且不為則K i 的左兄弟的編號是i;否則K i 無左兄弟
⑤若i為偶數且小於n則K i 的右兄弟的編號是i+;否則K i 無右兄弟
完全二叉樹的順序存儲
將完全二叉樹中所有結點按編號順序依次存儲在一個向量bt[n]中
其中
bt[n]用來存儲結點
bt[]不用或用來存儲結點數目
【例】表是圖所示的完全二叉樹的順序存儲結構bt[]為結點數目b[]的雙親左右孩子分別是bt[]bt[l]和
bt[]
一般二叉樹的順序存儲
() 具體方法
① 將一般二叉樹添上一些 虛結點成為完全二叉樹
② 為了用結點在向量中的相對位置來表示結點之間的邏輯關系按完全二叉樹形式給結點編號
③ 將結點按編號存入向量對應分量其中虛結點用∮表示
() 優點和缺點
① 對完全二叉樹而言順序存儲結構既簡單又節省存儲空間
② 一般的二叉樹采用順序存儲結構時雖然簡單但易造成存儲空間的浪費
【例】最壞的情況下一個深度為k且只有k個結點的右單支樹需要k個結點的存儲空間
③在對順序存儲的二叉樹做插入和刪除結點操作時要大量移動結點
二叉樹的順序存儲結構類型定義
【參見參考書】
From:http://tw.wingwit.com/Article/program/sjjg/201311/23886.html
