“Ma’lumotlar tuzilmasi va algoritmlar” fanidan 1-hafta laboratoriya ishi bajarishga namuna

“Ma’lumotlar tuzilmasi va algoritmlar” fanidan 8-AMALIY ISH (2-kurslar uchun)

8.3. Binar daraxtlar. Daraxt balandligi va ko‘ruvi
8.4. Muvozanatlangan binar daraxtlar. Binary Heap
Fan o‘qituvchisi: ass. M.A. Fayzullayev

8.3. Binar daraxtlar. Daraxt balandligi va ko‘ruvi

Rejalashtirildi:

• Ikkilik daraxtning balandligini qanday topish mumkin?
• Rekursiya yordamida binar daraxt balandligini topish.
• Binar daraxt ko‘ruvi algoritmlari.

Ikkilik daraxtning balandligini qanday topish mumkin?

Binar daraxtning balandligi – bu ildiz tugunidan boshlab ikkilik daraxtning har qanday barg tuguniga qadar eng uzun yo'l hisoblanadi. Agar biz balandlikni hisoblashimiz kerak bo'lsa, ildiz tugundan boshqa tugunlarga ulanmagan bo'lsa, u holda bu tugunning balandligi 0 ga teng bo'ladi.

Shunday qilib, biz ikkilik daraxtning balandligi deb aytishimiz mumkin, agar ikkilik daraxtning balandligi ikkilik daraxtning ildizidan boshlab eng olisdagi barg tuguniga qadar bo'lgan qirralarning eng katta miqdoriga teng.

Rekursiya yordamida binar daraxt balandligini topish

• Barg tugunining "h" uchun qirralari bo'ylab tugunlar soni 4 taga teng. 
• Barg tugunining "e" uchun qirralari bo'ylab tugunlar soni 3 ga teng. 
• Barg tugunining "f" uchun qirralari bo'ylab tugunlar soni 3 ga teng. 
• Barg tugunining "g" uchun qirralari bo'ylab tugunlar soni 3 ga teng.

Ildizdan eng uzoq barggacha maksimal tugun soni: max(4,3,3,3)=4. 
Demak, binar daraxtning balandligi 4 ga teng. 

Rekursiya yordamida binar daraxt balandligini topish

maksimal (0, 0) = 0 
Shuning uchun, har bir iteratsiyada tugun uzunligini qaytaradi: 1 + max (leftHeight, rightHeight)

Rekursiya yordamida binar daraxt balandligini topish

Rekursiya yordamida binar daraxt balandligini topish

 Python kodi (rekursiya bilan): 

class TreeNode:

def __init__(self, val):

self.val = val

self.left = None

self.right = None

def height(root):

# Ikkilik daraxt bo'sh yoki yo'qligini tekshiring

if root is None:

return 0

# Har bir tugunning balandligini rekursiv chaqirish
leftAns = height(root.left)
rightAns = height(root.right)
# Har bir iteratsiyada maksimal (leftHeight, rightHeight) qaytaring
return max(leftAns, rightAns) + 1
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print("Ikkilik daraxtning balandligi: " + str(height(root)) + " ga teng!") 

1. Tartib bo'yicha (chapdan o’nga) o'tish

Ushbu o'tish usulida birinchi navbatda chap pastki daraxtga, keyin ildizga va keyinroq o'ng pastki daraxtga tashrif buyuriladi. Biz har doim yodda tutishimiz kerakki, har bir tugun pastki daraxtning o'zini ko'rsatishi mumkin.

2. Daraxtni yuqoridan quyiga qarab o‘tish

Ushbu o'tish usulida birinchi navbatda ildiz tuguniga, keyin chap pastki daraxtga va nihoyat o'ng pastki daraxtga tashrif buyuriladi.

3. Daraxtni quyidan yuqoriga qarab o‘tish

Ushbu o'tish usulida ildiz tuguniga oxirida tashrif buyuriladi, Birinchidan, biz chap pastki daraxtni, keyin o'ng pastki daraxtni va nihoyat ildiz tugunini kesib o'tamiz (murojaat qilamiz).

Topshiriqlar:

Quyidagi ma’lumotlardan foydalanib binary daraxt hosil qiling va daraxtda barcha daraxt ko‘ruvi bo‘yicha elementlar qiymatini ekranga chiqaring?

TATU SF
KIF
TTKT
AT
DI
TT
AX
KT