DSA In-order o‘tish

Ikkilik daraxtlarni In-order o‘tish

In-order o‘tish — chuqurlik bo‘yicha qidiruvning bir turi bo‘lib, unda har bir tugunga ma’lum tartibda tashrif buyuriladi. Ikkilik daraxtlarni aylanib chiqish haqida umumiy ma’lumotni bu yerda o‘qing.

Ikkilik daraxtni In-order o‘tish qanday bajarilishini ko‘rish uchun quyidagi animatsiyani ishga tushiring.

In-order o‘tish chap qism daraxtni rekursiv In-order o‘tadi, ildiz tugunga tashrif buyuradi va nihoyat o‘ng qism daraxtni rekursiv In-order o‘tadi. Bu aylanib chiqish asosan ikkilik qidiruv daraxtlari uchun ishlatiladi, bunda u qiymatlarni o‘sish tartibida qaytaradi.

Bu aylanib chiqishni "in" order qiladigan narsa shundaki, tugunga rekursiv funksiya chaqiruvlari orasida tashrif buyuriladi. Tugunga chap qism daraxtni In-order o‘tishdan keyin va o‘ng qism daraxtni In-order o‘tishdan oldin tashrif buyuriladi.

In-order o‘tish kodi quyidagicha ko‘rinadi:

def inOrderTraversal(node):
    if node is None:
        return
    inOrderTraversal(node.left)
    print(node.data, end=", ")
    inOrderTraversal(node.right)

inOrderTraversal() funksiyasi argument None bo‘lib, funksiya qaytmaguncha (2–3-qatorlar) o‘zini joriy chap bola tugunni argument sifatida berib chaqirishda davom etadi (4-qator).

node argumenti birinchi marta None bo‘ladigan holat — C tugunining chap bolasi argument sifatida berilgan payt (C’ning chap bolasi yo‘q).

Shundan so‘ng C tugunining data qismi chop etiladi (5-qator), ya’ni birinchi bo‘lib 'C' chop etiladi.

Keyin C tugunining o‘ng bolasi argument sifatida beriladi (6-qator), u None bo‘lgani uchun funksiya chaqiruvi boshqa hech narsa qilmasdan qaytadi.

'C' chop etilgandan so‘ng oldingi inOrderTraversal() funksiya chaqiruvlari bajarilishda davom etadi, natijada 'A', keyin 'D', keyin 'R' va hokazo chop etiladi.