左兒子右兄弟表示法-資料下載頁(yè)
2025-06-30 20:52本頁(yè)面
【正文】 ion Create(i:integer。var x:LabelType。var T1,T2,..,Ti,T:TreeType)。beginNew(T)。 {建T的根結(jié)點(diǎn)}T^.Label:=x。T^.Parent:=nil。T^.Right_Sibling:=nil。if i0 then begin T^.Leftmost_Child:=T1。 for k:=1 to i do begin Tk^.Parent:=T。 if ki then Tk^.Right_Sibling:=Tk+1 else Tk^.Right_Sibling:=nil。 end。end。end。說(shuō)明這個(gè)過(guò)程首先生成新樹(shù)的根結(jié)點(diǎn)，其中存儲(chǔ)的數(shù)據(jù)為x；然后對(duì)于每一個(gè)Tk，1≤k≤i，將Tk的根結(jié)點(diǎn)的父親指向T，將Tk的根結(jié)點(diǎn)的右兄弟指向Tk+1(對(duì)于k=i的Tk其右兄弟為nil)。這里我們假設(shè)輸入的參數(shù)Tknil，1≤k≤i。復(fù)雜性顯然為O(i)。Label,Root和MakeNull比較簡(jiǎn)單，這里就不一一實(shí)現(xiàn)了。我們看到，用這種左兒子右兄弟表示法實(shí)現(xiàn)樹(shù)，可以高效地實(shí)現(xiàn)樹(shù)的ADT操作，缺點(diǎn)是占用了用來(lái)存儲(chǔ)指針的空間。不過(guò)我們還是推薦用這種表示法來(lái)表示樹(shù)。
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1