左兒子右兄弟表示法

1、左兒子右兄弟表示法樹的左兒子右兄弟表示法又稱為二叉樹表示法或二叉鏈表表示法。每個(gè)結(jié)點(diǎn)除了data域外，還含有兩個(gè)域，分別指向該結(jié)點(diǎn)的最左兒子和右鄰兄弟。這種表示法常用二叉鏈表實(shí)現(xiàn)，因此又稱為二叉鏈表表示法。但是實(shí)際應(yīng)用中常用游標(biāo)(靜態(tài)鏈表)來代替鏈表，請參見表的游標(biāo)實(shí)現(xiàn)。若用指針實(shí)現(xiàn)，其類型定義為：Type TPosition=NodeType; NodeType=record           Label:LabelType;    

2、;       Leftmost_Child,Right_Sibling:TPosition;          end; TreeType=TPosition; 若用游標(biāo)實(shí)現(xiàn)，其類型定義為:Type TPosition=integer; NodeType=record           Label:LabelTyp

3、e;           Leftmost_Child,Right_Sibling:TPosition;         end; CellspaceType=array 1.MaxNodeCount of NodeType; TreeType=TPosition;var Cellspace:CellspaceType; Tree:TreeType; 此時(shí)樹類型TreeType

4、是整數(shù)類型，它指示樹根在cellspace中的游標(biāo)。例如圖5(a)中樹的左兒子右兄弟表示法的指針和游標(biāo)實(shí)現(xiàn)分別如圖5(b)和(c)所示。(a)(b)(c)圖5 樹的左兒子右兄弟表示法    用樹的左兒子右兄弟表示法可以 直接實(shí)現(xiàn)樹的大部分操作，只有在對樹結(jié)點(diǎn)作Parent操作時(shí)需遍歷樹。如果要反復(fù)執(zhí)行Parent操作，可在結(jié)點(diǎn)記錄中再開辟一個(gè)指向父結(jié)點(diǎn)的指針域， 也可以利用最右兒子單元中的Right_Sibling作為指向父結(jié)點(diǎn)的指針(否則這里總是空指針)。當(dāng)執(zhí)行Parent(v)時(shí)，可以先通過 Right_Sibling逐步找出結(jié)點(diǎn)v的最右兄弟，再通過最右兄弟的

5、Right_Sibling(父親指針)找到父結(jié)點(diǎn)。這個(gè)結(jié)點(diǎn)就是結(jié)點(diǎn)v的父親。 在這樣的表示法下，求一個(gè)結(jié)點(diǎn)的父親所需要的時(shí)間正比于該結(jié)點(diǎn)右邊的兄弟個(gè)數(shù)。不過，這時(shí)每個(gè)記錄中需要多用一位(bit)空間，用以標(biāo)明該記錄中的 right_sibling是指向右鄰兄弟還是指向父親?？紤]到對于現(xiàn)在的計(jì)算機(jī)，內(nèi)存已經(jīng)不是很重要的限制因素了。我們下面就采取增加一個(gè)parent域的方案，以改進(jìn)左兒子右兄弟表示法中Parent操作的效率。因此重新定義樹的類型如下：若用指針實(shí)現(xiàn)，其類型定義為：Type TPosition=NodeType; NodeType=record  

6、;         Label:LabelType;           Parent,Leftmost_Child,Right_Sibling:TPosition; 增加一個(gè)Parent域          end; TreeType=TPosition;var Tree:TreeType; 若用游標(biāo)實(shí)現(xiàn)，

7、其類型定義為:Type TPosition=integer; NodeType=record           Label:LabelType;           Parent,Leftmost_Child,Right_Sibling:TPosition; 增加一個(gè)Parent域        

8、 end; CellspaceType=array 1.MaxNodeCount of NodeType; TreeType=TPosition;var Cellspace:CellspaceType; Tree:TreeType; 下面我們只針對上面的指針實(shí)現(xiàn)方案實(shí)現(xiàn)樹的ADT操作。對于指針實(shí)現(xiàn)的樹，空結(jié)點(diǎn)表示空指針nil。對于浮標(biāo)實(shí)現(xiàn)的樹，可以類似地實(shí)現(xiàn)下面的操作。指針實(shí)現(xiàn)的左兒子右兄弟表示法實(shí)現(xiàn)的ADT樹操作函數(shù) Leftmost_Child(v,T)功能這是一個(gè)求最左兒子結(jié)點(diǎn)的函數(shù)。函數(shù)值為樹T中結(jié)點(diǎn)v的最左兒子的位置。當(dāng)v是葉結(jié)點(diǎn)時(shí)，函數(shù)值為n

9、il，表示結(jié)點(diǎn)v沒有兒子。實(shí)現(xiàn)Function Leftmost_Child(v:TPosition;var T:TreeType):TPosition;begin return(v.Leftmost_Child);end;說明返回v的最左兒子的位置指針。復(fù)雜性顯然為O(1)。函數(shù) Right_Sibling(v,T)功能這是一個(gè)求右鄰兄弟的函數(shù)，函數(shù)值為樹T中結(jié)點(diǎn)v的右鄰兄弟。當(dāng)v沒有右鄰兄弟時(shí)，函數(shù)值為nil。實(shí)現(xiàn)Function Right_Sibling(v:TPosition;var T:TreeType):TPosition;begin return(v.Rig

10、ht_Sibling);end;說明返回v的右鄰兄弟的位置指針。復(fù)雜性顯然為O(1)。函數(shù) Parent(v,T)功能這是一個(gè)求父結(jié)點(diǎn)的函數(shù)，函數(shù)值為樹T中結(jié)點(diǎn)v的父親在結(jié)點(diǎn)表中的位置。當(dāng)v是根結(jié)點(diǎn)時(shí)，函數(shù)值為nil，表示結(jié)點(diǎn)v沒有父結(jié)點(diǎn)。實(shí)現(xiàn)Function Parent(v:TPosition;var T:TreeType):TPosition;begin return(v.Parent);end;說明返回v的父結(jié)點(diǎn)的位置指針。復(fù)雜性顯然為O(1)。函數(shù) Create(i,x,T1,T2,.,Ti)功能這是一族建樹過程。對于每一個(gè)非負(fù)整數(shù)i，該函數(shù)生成一個(gè)新樹T，T的根結(jié)點(diǎn)v的標(biāo)

11、號為x，并令v有i個(gè)兒子，這些兒子從左到右分別為樹T1,T2,.,Ti的根。當(dāng)i=0時(shí)，v既是樹根，又是樹葉。實(shí)現(xiàn)Function Create(i:integer;var x:LabelType;var T1,T2,.,Ti,T:TreeType);begin New(T); 建T的根結(jié)點(diǎn) T.Label:=x; T.Parent:=nil; T.Right_Sibling:=nil; if i>0 then  begin    T.Leftmost_Child:=T1;  &

12、#160; for k:=1 to i do     begin      Tk.Parent:=T;      if k<i then Tk.Right_Sibling:=Tk+1             else Tk.Right_Sibling:=nil;     end;    end;end;說明這個(gè)過程首先生成新樹的根結(jié)點(diǎn)，其中存儲的數(shù)據(jù)為x；然后對于每一個(gè)Tk，1ki，將T