DSA Pre-order o‘tish

Ikkilik daraxtlarni Pre-order o‘tish

Pre-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 Pre-order o‘tish quyidagicha ko‘rinadi:

Pre-order o‘tish avval ildiz tugunga tashrif buyurish, so‘ngra chap qism daraxtni rekursiv ravishda pre-order o‘tish, undan keyin esa o‘ng qism daraxtni rekursiv ravishda pre-order o‘tish orqali bajariladi. U daraxt nusxasini yaratish, ifoda daraxtining prefiks yozuvini olish va hokazolar uchun ishlatiladi.

Bu aylanib chiqish "pre" order deb ataladi, chunki tugunga chap va o‘ng qism daraxtlarni rekursiv pre-order o‘tishdan "oldin" tashrif buyuriladi.

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

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

Birinchi bo‘lib R tuguni chop etiladi, chunki Pre-order o‘tish chap va o‘ng bola tugunlarni rekursiv chaqirishdan (5 va 6-qatorlar) oldin joriy tugunga tashrif buyurish, ya’ni uni chop etish (4-qator) orqali ishlaydi.

preOrderTraversal() funksiyasi o‘ng qism daraxtni aylanib chiqishga o‘tishdan (6-qator) oldin chap qism daraxtni rekursiv aylanib chiqishda davom etadi (5-qator). Shuning uchun keyingi chop etiladigan tugunlar 'A' va keyin 'C'.

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

C’ning chap bolasi chaqirilganda birinchi marta None qaytarilgandan so‘ng, C’ning o‘ng bolasi ham None qaytaradi, keyin esa rekursiv chaqiruvlar orqaga qaytishda davom etadi, natijada keyingi chop etiladigan tugun A’ning o‘ng bolasi D bo‘ladi.

Kod orqaga qaytishda davom etadi va R’ning o‘ng qism daraxtidagi qolgan tugunlar chop etiladi.