Rеje: Ápiwayı kórip shıģıw hám binаr izlew аlgоritmleri 2

Gilt	Informaciya saatı		Shep bólek terek kórsetkishi
Oń bólek terek kórsetkishi
Payda bolmawı múmkin.		LLINK	RLINK
KEY

4-mısal. Dáslebki toplam gilti ósiw tártibinde tártiplengen bolıwı kerek. Sızıqlı royxatdan toplamnıń oraylıq elementi terektiń tamırı bolgan binar terek boyınsha izlewge ótemiz.

n_markaz= [N/2] + 1
bul jerde N- toplam elementler sanı.
Shep táreptegi shaxdıń ushı shep bólek toplamnıń oraylıq elementi esaplanadi; oń táreptegi oń bólek toplamdiki boladı.
{2,4,5,6,7, 9,12,14,18. Щ, 24,25,27,30,32,33,34,37,39}

toplam berilgen bolsın.

Izlenip atırgan gilt K=24\

Bárshe elementler N = 19; N_markaz = [19/2} + 1 = 10.

Binar teregi boyınsha K -24 izlew gilti tamırdan japıraqlarga shekem

4-suwrette kórsetilgen.

Binar terekte shegaralar bar: hár bir túyinge tek bir onıń ata-anası bolgan basqa túyin kórsetiliwi múmkin, hár bir túyinde ese eki teń silkalar bar bolıp, shep hám oń silkalar dep ataladı. Olar ese mas rawishde shep hám oń túyinlerdi kórsetedi. Usı túrde binar terekti nolinshi silka yaki hár biri bólek binar terek bolgan terekti kórsetiwshi shep hám oń silkali túyin sıpatında qarawımız múmkin.
Táriyp.

Binar terek boyınsha izlew - bul binar terek hár bir Comparable tipli giltten ibarat túyin (hám ol menen mánisler baylangan) hám qólegen túyindegi gilt shep bólek terektegi bárshe giltlerden úlken hám oń bólek terektegi barcha kalitlardan ichik shartni qanoatlantiradi. Quyidagi rasmda biz kalitlami tugunga joylashtiramiz. Har bir tugunning kalta kesmalar orqali ifodalangan nolinchi silkadan tashqari barcha i silkalari uni tugunlar bilan bogMaydi. Odatdagidek, bizning misolimizda bir simvolli kalitlardan foydalanamiz.

Procedure Obrab(ss:pt);

Begin Write(ss^.kl:5) End; {imitiruyuщаya оbrаbоtku uzlоv}

Procedure Poisk(cor:pt; ar1,ar2:tipkl; l:integer; var pp:pt); Label 1,2; {sl - BDU tuguniga ko’rsatkich sohasi, ssl – stеkdagi bog’lanish}

Type pnt=^z;

z=Record

sl:pt; ssl:pnt End;

Var rr,ss,tt: pt; q,t: pnt; Procedure StekIn; { BDU tuguniga t ko’rsatkichni stekka qo’shish} Begin New(q); q^.sl:= ss; q^.ssl:=t; t:=q End; Begin pp:= Nil; rr:= Nil; t:= Nil; tt:= cor; If l = 3 Then ar2:=ar1; While tt <> Nil do {Izlash jarayoni sikli} Begin ss:= tt; If ss^.kl = ar1 Then {kalitning mos tushish holati} Begin pp:= ss; StekIn; Goto 1 End; If ss^.kl > ar1 Then Begin tt:= tt^.lson; StekIn End Else Begin tt:= tt^.rson; rr:= ss End; End; If (l <> 2) And (t <> Nil) Then pp:= t^.sl; If l=-1 Then pp:= rr; 1:If pp <> Nil Then If l < 3 Then Obrab(pp) Else If t^.sl^.kl > ar2 Then pp:= Nil Else { l=3,4: uchun ishning 2-ETАPI} While t <> Nil do {BDUni chapdan qismiy ko’rib chiqish sikli} Begin q:= t; ss:qt^.sl; t:= t^.ssl; Dispose(q); If ss^.kl > ar2 Then Goto 2;{ Ko’rib chiqishni tugallash ehtimoli } Obrab(ss); ss:= ss^.rson; While ss <> Nil do Begin While ss^.lson <> Nil do {“O’yinchi”gacha chapga o’tish} Begin StekIn; ss:= ss^.lson End; If ss^.kl > ar2 Then Goto 2;

{Kórip shıgıwdı tawısıw itimalı}

Obrab(ss); ss:= ss^.rson End End; {BDU ni chapdan qismiy ko’rib chiqish blokining oxiri} 2:While t <> Nil do Begin q:=t; t:=t^.ssl; Dispose(q) End; End{Binar daraxtda izlash blоki oxiri( BDU)};
Binаr terek B-terektiń хususiy hоli bolıp esablаnаdı. m-dárejeli V- terek tómendegi shаrtlerdi qаnaаtlаndırıwshı ulıwmalıq terek sıpatında аnıqlаnаdı:
Usı suwrette 5-dárejeli V-terek kórsetilgen.Bul jеrde hár bir túyin qаndаyda bir tártiplengen(p1, k1, p2, k2, ..., kn-1, rn) topar arqаlı kórsetiliwi múmkin .Bul jеrde pi kórsetkish (bos kórsetkish. Gаr bеrilgen túyin áwlad bolsа) ese qаndаyda bir gilt. Pi kórsetip atırgan túyindegi 78 giltler ki-1 hám ki arаsındа jaylаsаdı. Hár bir túyin ishinde ese k1

Ádette, at tablicasında giltti izlewde eki variant bolıwı múmkin. Eger izlenip atıregan gilt túyini tablicada bar bolsa, ol jagdayda nishonga tegadi hám gilt penen baylangan mánis qaytadı. Eger kerisinshe bolsa, ol jagdayda nishonga tiymeydi hám nolge qaytadı.

Binar terek boyınsha izlewde gilt izlew rekursiv algoritmi rekursiv struktura boyınsha jóneledi: eger terek bos bolsa, ol jagdayda nishonga tegmaydi; eger izlenip atırgan gilt túbir giltke teń bolsa. Ol jagdayda nishonga tiyiwin bildiredi. Keri jagdayda izlew (rekursiv) mas rawishde izlenip atırgan gilt bolsa shep bólek terekte, úlken bolsa oń bólek terekte dawam ettiriledi. Process izlenip atırgan gilt bar bolgan túyin tabılganga yaki joriy bólek terek bos bolganda tawsıladı. Izlew joqarıdan baslanadı hám bólek túyinlerge rekursiv ótedi, sonıń ushın hám izlew terek jónelisin anıqlap beredi. Nishonga tiyetugın bolganda izlenip atırgan gilt bar bolgan túyin jónelisi tawsıladı , nishonga tegmaydigan jónelis nolinshi silka menen tawsıladı.

Binar terek boyınsha izlewde (shepta) nishonga tiyiw hám (ońda) nishonga tegmaslik.