Tarkibga o'tish

Daraxtni aylanish (DFS, BFS)

Xaritadagi barcha shaharlarni aylanishni tasavvur qiling. Ikki xil strategiya bor: bir yo'nalishda imkon qadar chuqur borib, keyin orqaga qaytish — yoki avval yaqin atrofdagilarni ko'rib, keyin uzoqroqqa chiqish. Daraxtda ham aynan shu ikki yondashuv ishlaydi: DFS (chuqurlik bo'yicha) va BFS (kenglik bo'yicha).

Traversal — daraxtdagi har tugunni aynan bir marta ko'rib chiqish. Maqsad: qidirish, qiymatlarni to'plash, daraxtni qayta ishlash yoki tekshirish.

DFS — Chuqurlik bo'yicha qidiruv

DFS (Depth-First Search) — bir shoxga to imkon qadar chuqur tushib, keyin orqaga qaytib, boshqa shoxni ko'rib chiqish. Rekursiya yoki stek yordamida amalga oshiriladi.

Binar daraxtda DFS uchun uchta klassik tartib mavjud: preorder, inorder, postorder.

        [1]
       /   \
     [2]   [3]
    / \
  [4] [5]

Preorder: ildiz → chap → o'ng

Avval ildiz, keyin chap kenja daraxt, keyin o'ng kenja daraxt. Daraxtni "yuqoridan pastga" o'qiladi.

FUNCTION PREORDER(node)
    IF node = NULL
        RETURN

    VISIT(node)               // ildiz avval
    PREORDER(node.left)       // chap kenja daraxt
    PREORDER(node.right)      // o'ng kenja daraxt

Yuqoridagi daraxt uchun: 1 → 2 → 4 → 5 → 3

Nima uchun foydali: daraxtni nusxalash, fayl tizimini ro'yxatga olish (ota-papka avval yozilishi kerak), serialization.

Inorder: chap → ildiz → o'ng

Avval chap kenja daraxt, keyin ildiz, keyin o'ng kenja daraxt.

FUNCTION INORDER(node)
    IF node = NULL
        RETURN

    INORDER(node.left)        // chap kenja daraxt
    VISIT(node)               // ildiz
    INORDER(node.right)       // o'ng kenja daraxt

Yuqoridagi daraxt uchun: 4 → 2 → 5 → 1 → 3

BST'da inorder traversal barcha qiymatlarni o'sish tartibida beradi. Bu BST'ning asosiy foydali xususiyati.

BST:     [5]
        /   \
      [3]   [7]
     / \   / \
   [2][4] [6][8]

Inorder: 2, 3, 4, 5, 6, 7, 8  ← o'sish tartibi

Postorder: chap → o'ng → ildiz

Avval chap kenja daraxt, keyin o'ng kenja daraxt, oxirida ildiz.

FUNCTION POSTORDER(node)
    IF node = NULL
        RETURN

    POSTORDER(node.left)      // chap kenja daraxt
    POSTORDER(node.right)     // o'ng kenja daraxt
    VISIT(node)               // ildiz oxirida

Yuqoridagi daraxt uchun: 4 → 5 → 2 → 3 → 1

Nima uchun foydali: daraxtni o'chirish (bolalar avval o'chirilishi kerak), matematik ifodalarda quyi ifodalar avval hisoblanadi, fayl hajmlarini hisoblash (papka hajmi barcha bolalar hajmlaridan keyin).

Bosqichma-bosqich dry run

        [A]
       /   \
     [B]   [C]
    / \
  [D] [E]

Uchala DFS tartibini kuzatamiz. Rekursion chaqiruvlarni stack orqali kuzatish:

Preorder (ildiz avval):
  PREORDER(A):
    VISIT A                    → "A"
    PREORDER(B):
      VISIT B                  → "A, B"
      PREORDER(D):
        VISIT D                → "A, B, D"
        PREORDER(NULL) → qayt
        PREORDER(NULL) → qayt
      PREORDER(E):
        VISIT E                → "A, B, D, E"
        PREORDER(NULL) → qayt
        PREORDER(NULL) → qayt
    PREORDER(C):
      VISIT C                  → "A, B, D, E, C"
      PREORDER(NULL) → qayt
      PREORDER(NULL) → qayt

Preorder natija: A, B, D, E, C

Inorder natija:  D, B, E, A, C

Postorder natija: D, E, B, C, A

DFS'ni iterativ amalga oshirish

Rekursiv DFS chaqiruv stacki ishlatadi. Katta daraxlarda stack overflow bo'lishi mumkin. Iterativ variant o'z stekimizni boshqaradi.

Iterativ preorder:

FUNCTION ITERATIVE_PREORDER(root)
    IF root = NULL
        RETURN

    stack = [root]
    result = []

    WHILE stack bo'sh emas
        node = stack dan POP

        result ga node.value qo'sh

        IF node.right ≠ NULL
            stack ga node.right PUSH   // o'ng avval → chapni avval ko'rish uchun
        IF node.left ≠ NULL
            stack ga node.left PUSH    // chap keyin → avval chiqadi

    RETURN result

Nima uchun o'ng avval push qilinadi? Stek LIFO — keyingi POP eng yuqoridagini oladi. Chapni avval ko'rishimiz uchun chap oxirida push qilinadi.

BFS — Kenglik bo'yicha qidiruv

BFS (Breadth-First Search) — daraxtni qavatma-qavat o'qiydi: birinchi ildiz, keyin birinchi qavat, keyin ikkinchi qavat va hokazo. Navbat (queue) ishlatiladi.

        [1]            ← 0-qavat
       /   \
     [2]   [3]         ← 1-qavat
    / \   /
  [4] [5][6]           ← 2-qavat

BFS tartibi: 1, 2, 3, 4, 5, 6

FUNCTION BFS(root)
    IF root = NULL
        RETURN

    queue = [root]
    result = []

    WHILE queue bo'sh emas
        node = queue dan DEQUEUE (old)

        result ga node.value qo'sh

        IF node.left ≠ NULL
            queue ga node.left ENQUEUE
        IF node.right ≠ NULL
            queue ga node.right ENQUEUE

    RETURN result

BFS davomida navbat qanday o'zgarishini kuzatish:

queue: [1]          result: []
DEQUEUE 1 → result: [1]
  ENQUEUE 2, 3
queue: [2, 3]

DEQUEUE 2 → result: [1, 2]
  ENQUEUE 4, 5
queue: [3, 4, 5]

DEQUEUE 3 → result: [1, 2, 3]
  ENQUEUE 6
queue: [4, 5, 6]

DEQUEUE 4 → result: [1, 2, 3, 4]    bolasi yo'q
queue: [5, 6]

DEQUEUE 5 → result: [1, 2, 3, 4, 5] bolasi yo'q
queue: [6]

DEQUEUE 6 → result: [1, 2, 3, 4, 5, 6] bolasi yo'q
queue: []

Natija: [1, 2, 3, 4, 5, 6]

Qavat bo'yicha BFS

Ko'pincha har qavatni alohida ro'yxat sifatida olish kerak bo'ladi. Bu uchun har iteratsiyada navbatdagi barcha elementlar — joriy qavat — birgalikda qayta ishlanadi.

FUNCTION BFS_BY_LEVEL(root)
    IF root = NULL
        RETURN []

    queue = [root]
    result = []

    WHILE queue bo'sh emas
        level_size = navbat hajmi      // joriy qavatdagi elementlar soni
        current_level = []

        FOR i = 0 DAN level_size-1 GACHA
            node = queue dan DEQUEUE

            current_level ga node.value qo'sh

            IF node.left ≠ NULL
                queue ga node.left ENQUEUE
            IF node.right ≠ NULL
                queue ga node.right ENQUEUE

        result ga current_level qo'sh

    RETURN result

Natija: [[1], [2, 3], [4, 5, 6]]

Bu "Level Order Traversal" — keyingi masalada batafsil ko'riladi.

Vaqt va xotira murakkabligi

Algoritm Vaqt Xotira Xotira nima uchun?
DFS (rekursiv) O(n) O(h) Call stack chuqurligi
DFS (iterativ) O(n) O(h) Stek hajmi
BFS O(n) O(w) Navbat hajmi

n — tugunlar soni, h — balandlik, w — eng keng qavat.

DFS xotirasi: rekursion call stack daraxt balandligiga teng — O(h). Muvozanatlangan daraxtda O(log n), zanjir ko'rinishida O(n).

BFS xotirasi: navbatda eng ko'p tugun eng keng qavatda bo'ladi. Mukammal binar daraxtda oxirgi qavat n/2 tugunni saqlaydi — O(n/2) = O(n). Chuqur va tor daraxtda BFS xotirasi DFS'dan kamroq; keng va yassi daraxtda ko'proq.

Qaysi traversal qachon?

Vazifa Eng mos traversal Sabab
BST'ni tartibli o'qish Inorder BST inorder → o'sish tartibi
Daraxt nusxasini olish Preorder Ota avval, bolalar keyin
Daraxtni o'chirish Postorder Bolalar avval, ota keyin
Qavat bo'yicha o'qish BFS Qavatma-qavat tabiiy
Eng qisqa yo'l BFS BFS birinchi topilgan yo'l qisqa
Barcha yo'llar DFS Rekursiv shox bo'yicha yurish
Daraxt mavjudmi (chuqur)? DFS Katta w da BFS xotira ko'p

Rekursiya va DFS aloqasi

DFS rekursion yozilishi eng tabiiy. Rekursion funksiya har safar:

  1. Base case tekshiradi (NULL → qaytadi).
  2. Joriy tugunga ish qiladi (VISIT).
  3. Chap kenja daraxtga rekursiv chaqiradi.
  4. O'ng kenja daraxtga rekursiv chaqiradi.

Bu "bo'l va zabt et" tamoyili: har tugun o'z kenja daraxtini mustaqil qayta ishlaydi. Natija quyi tugunlar natijalarini birlashtiradi.

FUNCTION TREE_HEIGHT(node)
    IF node = NULL
        RETURN -1

    left_h  = TREE_HEIGHT(node.left)
    right_h = TREE_HEIGHT(node.right)
    RETURN 1 + MAX(left_h, right_h)

Bu postorder mantiqida: avval chap va o'ng balandligi hisoblanadi, so'ng birlashtirilib ildizga qaytariladi.

Real qo'llanishlar

Fayl tizimini ko'rsatish

ls -R yoki find buyrug'i DFS preorder ishlatadi: papka nomi avval, keyin uning bolalari.

Brauzer DOM traversali

JavaScript document.querySelectorAll DOM daraxtini DFS bilan aylanib, mos elementlarni to'playdi. CSS animatsiyasi daraxtda pastdan yuqoriga (postorder) qo'llanishi mumkin.

Grafik render tartibi

Scene graph'da (3D sahnada) ota-transformatsiya bolaga tatbiq qilish uchun preorder ishlatiladi.

Sosial tarmoq eng qisqa yo'l

"Ikki foydalanuvchi orasidagi eng qisqa bog'lanish zanjiri" — BFS. BFS daraxt yoki grafda manba dan boshlanib, eng yaqin tugunlarni avval ko'rib chiqadi.

Keng tarqalgan xatolar

NULL holat tekshirilmasa. Har rekursiv funksiya birinchi qadamida node = NULL holatini tekshirishi kerak. Tushirib qoldirilsa, null-dereference xatosi.

BFS uchun navbat o'rniga stek ishlatish. Navbat (FIFO) BFS uchun; stek (LIFO) DFS uchun. Ularni aralashtirish noto'g'ri traversal tartibini beradi.

Inorder va preorderni aralashtirish. VISIT ning joyi muhim: preorderdda rekursiv chaqiruvlardan oldin, inorderdda chap rekursiyadan keyin o'ng rekursiyadan oldin, postorderdda ikkalasidan keyin.

Qavat hajmini navbatdan dinamik o'lchash. level_size = navbat hajmi navbat to'ldirilishidan oldin olinishi kerak. Aks holda joriy qavat tugunlari qo'shilgan bolalar ham hisob-ga kirib ketishi mumkin.

Xulosa

Daraxt traversali uchun ikkita asosiy strategiya mavjud.

DFS rekursiya yordamida chuqurlikka kiradi. Uchta tartibi bor: preorder (ildiz avval), inorder (ildiz o'rtada — BST uchun muhim), postorder (ildiz oxirida — o'chirish va hisoblash uchun). Xotira O(h).

BFS navbat yordamida qavatma-qavat ishlaydi. Eng qisqa yo'l va qavat bo'yicha ishlov uchun mos. Xotira O(w) — eng keng qavat.

Ko'plab daraxt masalalari — chuqurlik, simmetriya, umumiy qiymat, yo'l — DFS bilan rekursiv yechiladi: har tugun o'z kenja daraxtlaridan natija olib, birlashtiradi. Qavat bo'yicha masalalar BFS bilan aniqroq yechiladi.