左兒子右兄弟表示法

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

2、;       Leftmost_Child,Right_Sibling:TPosition;          end; TreeType=TPosition; 若用游標實現(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; 此時樹類型TreeType

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

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

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

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

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

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

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

11、號為x，并令v有i個兒子，這些兒子從左到右分別為樹T1,T2,.,Ti的根。當i=0時，v既是樹根，又是樹葉。實現(xiàn)Function Create(i:integer;var x:LabelType;var T1,T2,.,Ti,T:TreeType);begin New(T); 建T的根結(jié)點 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;說明這個過程首先生成新樹的根結(jié)點，其中存儲的數(shù)據(jù)為x；然后對于每一個Tk，1ki，將T