Informatika va at

17.9. T1 va T2 daraxtlarning tengligini tekshiruvchi rekursiv va rekursiv bo'lmagan mantiqiy Equal(T1,T2) funktsiyasi aniqlansin.

17.10. T daraxt nusxasi − T1 daraxtni quruvchi copy(T,T1) protsyedurasi tuzilsin.

17.11. Berilgan n- butun soni bo'yicha 19-rasmda ko'rsatilgan T daraxtni quruvchi CREATE(T,n) protsyedurasi tuzilsin.

19-rasm

17.12. T daraxtda kamida ikkita bir xil element bor yoki yo'qligini aniqlovchi mantiqiy Same(T) funktsiyasi aniqlansin.

17.13. Formula tuzilishi berilgan:

::=  ( )

::= +*

::= 0123456789
Formulani DET=char bo'lgan daraxt ko'rinishida tasvirlash mumkin (“daraxt-formula”). Bunda quyidagi qoidadan foydalaniladi: bitta terminaldan (raqamdan) iborat formula daraxtning bitta tuguni bilan, (f₁ s f₂) formula ko'rinishidagi daraxtda ildiz-bu s belgisi, va uning chap va o'ng daraxt ostilarida mos ravishda f₁ va f₂ formulalar. 20-rasmda (5*(3+8)) formulaning daraxt formulasi ko'rsatilgan.

Quyidagi masalalarni yechadigan rekursiv protsyedura yoki funktsiya tuzilsin:

a) T daraxt-formula qiymatni (butun son sifatida) hisoblovchi;

b) f matn faylida yozilgan formuladan mos T daraxt-formula yaratuvchi;

v) T daraxt-formulaga mos keluvchi formula chop qiladigan;

g) T ikkilik daraxt daraxt-formula ekanligini tekshiruvchi.

17.14. Daraxt-formulada (17.13 ga qarang) terminal sifatida faqat raqamlar emas, balki o'zgaruvchi rolini o'ynovchi harflar ham ishlatiladi deb hisoblansin. Protsyedura ko'rinishida yechilsin:

a) T daraxt-formuladagi (f+0), (0+f), (f0), (f*1) va (1*f) formulalarga mos keluvchi daraxt ostilarini − f formulaga mos keluvchi daraxt ostilariga, (f*0), (0*f) formulalarni 0 tugun bilan almashtirish orqali soddalashtiruvchi;

b) T daraxt-formulada ((f₁f₂)*f₃) va ((f₁*(f₂f₃)) formulalariga mos daraxt ostilarini ((f₁f₂)*f₃) va ((f₁*f₂)(f₂*f₃)) formulalarga mos keluvchi daraxt ostilar bilan almashtiruvchi;

v) T daraxt-formula ustida b) punktdagi amalga nisbatan teskari almashtirishlar qiluvchi;

g) T daraxt-formulani ixtiyoriy parametr orqali berilgan bir harfli o'zgaruvchi bo'yicha hosilasi T1 daraxt-formulani quradigan.

20-rasm 21-rasm

17.15. Daraxt-formulaning 17.13 dagi ko'rinishida terminal o'rnida ixtiyoriy musbat butun son bo'lishi munkin deb hisoblagan holda, uning ustida 17.13 masaladagi barcha amallar bajarilsin.

17.16. Izlash daraxti yoki daraxt ko'rinishidagi jadval deb, uning ixtiyoriy tugunining chap tomonida shu tugun elementidan kichik elementlar, o'ngda undan katta elementlar joylashgan ikkilik daraxti tushuniladi (daraxt elementlari o'zaro farqli va uning turi (DET) taqqoslash amalini qo'llash imkonini beradi). 21-rasmda shunday daraxtlardan biri ko'rsatilgan:

Daraxt turi (DET) aniqlangan deb hisoblab, fayl turi berilgan:

type fayl = file of DET;

Quyidagi masalalarni yechadigan protsyedura yoki funktsiya aniq- lansin:

a) YE element T izlash daraxtiga kirish-kirmasligini tekshiradigan;

b) T izlash daraxtidagi elementlarni f faylga o'sish tartibida yozadigan;

v) T izlash daraxtiga YE yangi elementni qo'shadigan, agarda YE element T da bo'lmasa;

g) Elementlari turli xil bo'lgan f fayl bo'yicha unga mos T izlash daraxtini quradigan.

17.17. PROG matn faylida Paskal tilidagi programma matni (xatosiz) berilgan. Ma'lumki, bu programmada har bir identifikator (xizmatchi so'z yoki nom) 9 belgidan oshmagan harf va (yoki) raqamdan iborat. Programmadagi barcha identifikatorlar alfavit tartibida ularni programmaga kirishlari soni bilan birgalikda chop qilinsin. (Harfning katta va kichik ko'rinishi bir xil deb hisoblansin, satr-konstanta va izohlar identifikator hisoblanmaydi, haqiqiy son yozuvida YE yoki ye uchrashi mumkin). Identifikatorlarni saqlash uchun elementlar juftligidan, ya'ni identifikator va uning programma matniga kirishlar sonidan iborat bo'lgan izlash daraxtidan foydalanilsin.

17.18. Yuqoridagi masala quyidagicha yechilsin: har bir identifikator bilan, u uchraydigan satrlar nomerlarining o'sish tartibdagi ket-ketligini chop qilinsin.