11-Mavzu: Daraxt tushunchasi. Daraxtning kompyuter xotirasida tasvirlanishi. Reja

V >	Li		Key	Record
>ht
		^f 1				^f

Xotirada daraxtga mos keluvchi ma'lumotlar tuzilmasini yaratish uchun MakeTree(Key,Rec) nomli protsedura ishlatilib, u xotirada ikki ko‘rsatkichga va ikki (kalit va axborot) maydonga ega bo‘lgan element (daraxt tuguni)ni hosil qiladi.

MakeTree protsedurasining ko‘rinishi:

Psevdokodda:

p = getnode r(p) = rec k(p) = key v = p

Paskal tilida: New(p);

p^A.r := rec; p^A.k := key; v := p; p^A.left := nil;

left(p) = nil

right(p) = nil pA.right := nil;

m-ar daraxtni binar daraxtga keltirish algoritmini quyidagicha yozish mumkin:

1. 
   daraxtning tugunlarida chap katta —bola”ga mos keluvchi shoxdan boshqa barcha shoxlar kesib tashlanadi (4.7a-rasm);
   
2. 
   bir —ota”ning barcha —bola”lari gorizontal chiziqlar bilan birlashtiriladi (4.7b-rasm);
   

3. ushbu tuzilmadagi har bir element uchun uning ostida joylashgan element katta “bola” hisoblanadi (4.7v-rasm).



a) b)


v) g)

m-ar daraxtdan binar daraxtga o’tish

Nazariy savollar

1. 
   Daraxt tushunchasini tushuntirib bering?
   
2. 
   Daraxtning kompyuter xotirasida tasvirlanishini tushuntirib bering?
   
3. 
   Daraxtlarni tasvirlashni tushuntirib bering?
   
4. 
   Binar (ikkilik) daraxtlarni tushuntirib bering?