DSA Post-order o‘tish

Ikkilik daraxtlarni Post-order o‘tish

Post-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 Post-order o‘tishni quyidagicha tasavvur qilish mumkin:

Post-order o‘tish chap qism daraxt va o‘ng qism daraxtni rekursiv Post-order o‘tish, so‘ngra ildiz tugunga tashrif buyurish orqali ishlaydi. U daraxtni o‘chirish, ifoda daraxtining postfiks yozuvini olish va hokazolar uchun ishlatiladi.

Bu aylanib chiqishni "post" qiladigan narsa shundaki, tugunga tashrif buyurish chap va o‘ng bola tugunlar rekursiv chaqirilgandan "keyin" amalga oshiriladi.

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

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

postOrderTraversal() funksiyasi C’ning chap bola tuguni node argumenti sifatida chaqirilganda None qaytarilmaguncha chap qism daraxtni rekursiv aylanib chiqishda davom etadi (4-qator).

C’ning chap bola tuguni None qaytargandan so‘ng 5-qator bajariladi va C’ning o‘ng bola tuguni None qaytaradi, keyin esa 'C' harfi chop etiladi (6-qator).

Bu shuni anglatadiki, C’ga uning chap va o‘ng bola tugunlari aylanib chiqilgandan "keyin" tashrif buyuriladi, ya’ni u chop etiladi — shuning uchun bu "post" order o‘tish deb ataladi.

postOrderTraversal() funksiyasi oldingi rekursiv funksiya chaqiruvlariga qaytishda davom etadi, shuning uchun keyingi chop etiladigan tugun 'D', keyin esa 'A' bo‘ladi.

Funksiya barcha tugunlar chop etilmaguncha, ya’ni ularga tashrif buyurilmaguncha orqaga qaytishda va tugunlarni chop etishda davom etadi.