16
tashrif oddiy operatsiyalarni bajarish,masalan: daraxt uchlari belgilarini chop etish yoki
murakkab operatsiyalarni bajarish,masalan: ba’zi funksiyalarni hisoblash bilan bog’liq
bo’lishi mumkin.
Agar uchlarga tashrif orqali
daraxt strukturasi buzulmasa, daraxt uchlaeini
aylanib o’tishning quyidagi ikki asosiy usuli bir qancha foydali hisoblanadi: tubini
aylanib o’tish va kengligini aylanib o’tish.
Daraxt tubini aylanib o’tishda (xuddi fo’g’ri tartibda o’tish kabi ma’lum)
quyidagi rekursiv protsedura bilanmoslikda daraxt uchlariga tashrif buyuriladi: oldin
daraxtning q - ildiziga tashrif , keyin agar ildiz qaralayotgan daraxtning bargi bo’lmasa,
u holda har bir q - ildizning p - o’g’li tubini aylanib o’tish
protsedurasiga murojaat
qilinadi,negaki, hamma shoxlar p - ildizlar bilan xuddi q - ildiz o’g’li p - uch tartibidek
aylanib o’tiladi.
Agar daraxt bo’lab joriy yo’lni saqlash uchun S - stekni qo’llasak, ya’ni daraxt
ildizidan boshlanib, uchida tugaydigan, berilganmomentda tashrif buyuruvchi yo’lni
saqlash uchun S - stekni qo’llasak, daraxt tubini aylanib o’tishning rekursiv bo’lmagan
algoritmini qurish mumkin:
Daraxt ildiziga tashrif va uni S - bo’sh stekka joylashtirish;
WHILE S - stek bo’sh bo’lmaguncha DO
BEGIN
S - stekning tepasida joylashgan uch p bo’lsin;
IF p - uch o’g’li hali kelmagan
THEN Katta o’g’ilni p - uchga keltirish va uni S - stekka joylashtirish;
ELSE BEGIN p - uchni S - stekdan o’chirish;
IF p - uka bo’lsa
THEN Ukani p - uchga keltirish va uni S - stekka joylashtirish;
END;
END[9].
Daraxt kengligini aylanib o’tish, ba’zan gorizontal tartibda o’tuvchi usul ham
deyiladi, daraxt uchlari bo’ylab chapdan-o’ngga, daraxt ildizlari bo’ylab darajama-
17
daraja murojaatni amalga oshiradi.Shunday qilib, uzunligi noaniq bo’lgan ( r - ma’lum
emas), qandaydir (
a
1
,a
2
,...
) vektor ko’rinishidagi biror yechimini topish mumkin.
Chuqurlikni aylanib o’tish algoritmini shunday ta’riflash kerakki, uni
tasvirlangan grafning hammauchlari bo’ylab aylanib o’tishga qo’llash mumkin bo’lsin:
WHILE Hech bo’lmaganda bitta uchga tashrifga ega bo’lguncha DO
BEGIN p - tashrif buyurilmagan uchlarning birinchisi ( minimali) bo’lsin;
p - uchga kelish va uni S - stek tepasiga joylashtirish;
WHILE S - stek bo’sh emas DO
BEGIN S - stek tepasida joylashganuch p bo’lsin;
IF p - uchda kelmagan qo’shiluvchi uchlar bo’lsin;
THEN BEGIN p - ning qo’shilgan uchlari lchida birinchi tashrif buyurmaganuch q -
bo’lsin;
(p,q) reber bo’ylab yurish q - uchga tashrif va uni s - stekka joylashtirish;
END;
ELSE p - uchni S - stekdan uchirish;
END;
END.
Algoritm ishi natijasida grafning bir-biriga o’tgan reberlari bir yoki bir nechta
daraxt uchlariga tashrif bilan tasvirlanadi[9].
Qaytishli izlashni takomillashtirish: dasturda qaytishli izlashning realizatsiyasi
hamma usullarda mumkin bo’lgan yechimlar to’plami sifatida qaraladi.Faqat shunday
konfiguratsiyalar, ya’ni imkoniyatlar sonini ko’paytiradigan komfiguratsiyalar tadqiq
qilinadi. Imkoniyatlar to’plamini qisqartirish uchun shu turdagi analizdan foydalanish
chegarali izlash yoki shoxlarni kesib tashlash deyiladi.
Ikki konfiguratsiyani ekvivalent
deb hisoblash mumkin, agar ulardan biri
aylantirish va akslantirish yordamida boshqasiga o’tsa. Aylantirish va akslantirish
yordamida ulardan hamma konfiguratsiyalar to’plami quriladi.
Yana bir takomillashtirish— shoxlarning qo’shilishidir. Uning g’oyasi shundan
iboratki, bir xil ishni ikki marta bajarishni oldini olish, agar ba’zi
daraxtning shoxlarini
izlash izomorf bo’lsa, hech bo’lmaganda ulardan birini tadqiq qilishning iloji bo’lsa.
18
Shuni nazarda tutish lozimki,nafaqat dasturlarni qayta ishlashda, balki shu bilan
birga qayta ishlangan dasturni o’chirishda ham har xil takomillashtirishlarni
qo’llashmaqsadga muvofiqdir.
