DSA massiv orqali amalga oshirish

Ikkilik daraxtlarni massiv orqali amalga oshirish

Massivlardan foydalanganda yuzaga keladigan xotiradagi barcha siljitishlar xarajatidan qochish uchun, ayniqsa ikkilik daraxt tez-tez o‘zgartirilsa, ikkilik daraxtlarni shu paytgacha amalga oshirganimiz kabi bir elementdan keyingisiga ko‘rsatkichlar yordamida amalga oshirish foydali.

Ammo agar ikkilik daraxtdan uni o‘zgartirishga qaraganda ancha ko‘p o‘qisak, ikkilik daraxtni massiv orqali amalga oshirish ma’qul bo‘lishi mumkin, chunki u kamroq xotira talab qiladi, uni amalga oshirish osonroq bo‘lishi mumkin va kesh lokalligi tufayli ayrim amallar uchun tezroq bo‘lishi mumkin.

Ushbu ikkilik daraxtni ko‘rib chiqing:

Bu ikkilik daraxtni massivda ildiz tugun R’ni 0-indeksga joylashtirishdan boshlab saqlash mumkin. Daraxtning qolgan qismini \(i\) indeksda saqlangan tugunni olib, uning chap bola tugunini \(2\cdot i+1\) indeksda, o‘ng bola tugunini esa \(2\cdot i+2\) indeksda saqlash orqali qurish mumkin.

Quyida ikkilik daraxtning massiv orqali amalga oshirilishi berilgan.

binary_tree_array = ['R', 'A', 'B', 'C', 'D', 'E', 'F', None, None, None, None, None, None, 'G']

def left_child_index(index):
    return 2 * index + 1

def right_child_index(index):
    return 2 * index + 2

def get_data(index):
    if 0 <= index < len(binary_tree_array):
        return binary_tree_array[index]
    return None

right_child = right_child_index(0)
left_child_of_right_child = left_child_index(right_child)
data = get_data(left_child_of_right_child)

print("root.right.left.data:", data)

Bu massiv orqali amalga oshirishda ikkilik daraxt tugunlari massivga joylashtirilgani sababli kodning katta qismi tugunlarga indekslar orqali murojaat qilish va to‘g‘ri indekslarni qanday topishga bag‘ishlangan.

Aytaylik, B tugunining chap va o‘ng bola tugunlarini topmoqchimiz. B 2-indeksda bo‘lgani uchun B’ning chap bolasi \(2\cdot 2+1=5\) indeksda, ya’ni bu E tuguni, to‘g‘rimi? B’ning o‘ng bolasi esa \(2\cdot 2+2=6\) indeksda, ya’ni F tuguni va bu ham yuqoridagi chizmaga mos keladi, to‘g‘rimi?

1-qatorda ko‘rib turganingizdek, bu amalga oshirish tugunlarning bola tugunlari bo‘lmagan joylarda bo‘sh massiv elementlarini talab qiladi. Shuning uchun bo‘sh massiv elementlariga joy isrof qilmaslik uchun massiv orqali saqlanadigan ikkilik daraxtlar "mukammal" (perfect) ikkilik daraxt yoki unga yaqin bo‘lishi kerak.

Mukammal ikkilik daraxt — har bir ichki tugun aynan ikkita bola tugunga ega bo‘lgan va barcha barg tugunlar bir xil darajada joylashgan daraxt.

Yuqoridagi ikkilik daraxtdan G tugunini olib tashlasak, u quyidagicha ko‘rinadi:

Shunda yuqoridagi koddagi birinchi qatorni bo‘sh massiv elementlariga joy isrof qilmasdan yozish mumkin:

binary_tree_array = ['R', 'A', 'B', 'C', 'D', 'E', 'F']

Ikkilik daraxtning massiv orqali amalga oshirilishida uchta turli DFS aylanib chiqishni quyidagicha bajarish mumkin.

binary_tree_array = ['R', 'A', 'B', 'C', 'D', 'E', 'F', None, None, None, None, None, None, 'G']

def left_child_index(index):
    return 2 * index + 1

def right_child_index(index):
    return 2 * index + 2

def pre_order(index):
    if index >= len(binary_tree_array) or binary_tree_array[index] is None:
        return []
    return [binary_tree_array[index]] + pre_order(left_child_index(index)) + pre_order(right_child_index(index))

def in_order(index):
    if index >= len(binary_tree_array) or binary_tree_array[index] is None:
        return []
    return in_order(left_child_index(index)) + [binary_tree_array[index]] + in_order(right_child_index(index))

def post_order(index):
    if index >= len(binary_tree_array) or binary_tree_array[index] is None:
        return []
    return post_order(left_child_index(index)) + post_order(right_child_index(index)) + [binary_tree_array[index]]

print("Pre-order Traversal:", pre_order(0))
print("In-order Traversal:", in_order(0))
print("Post-order Traversal:", post_order(0))

Bu aylanib chiqishlar massiv orqali amalga oshirishda qanday bajarilishini ko‘rsatkichlar orqali amalga oshirilgan daraxtni aylanib chiqish bilan solishtirsangiz, pre-order, in-order va post-order o‘tishlar bir xil rekursiv usulda ishlashini ko‘rishingiz mumkin.