Mavzu: 14 “Dag‘al kuch” usuli bilan tartiblashtirish

Mavzu: 14 “Dag‘al kuch” usuli bilan tartiblashtirish.

Reja:
1. “Daraxt” ma’lumotlarning abstract turi.

2. Daraxtni qurish va ko‘rib chiqish algoritmlari.
3. Tikilgan(прошитого) ikkilik daraxtni aniqlash.
4. Belgilangan daraxtlarni olish.

Daraxt bu elementlarning ierarxik tuzilishini tashkil etuvchi elementlar va munosabatlar to‘plami bo‘lgan chiziqli bo‘lmagan ma'lumotlar tuzilmasi.

Asosiy tushunchalar
Daraxt tugunlari orasidagi bog‘lanishni tavsiflash uchun quyidagi terminologiya qo‘llaniladi:
M1 - A va B elementlari uchun “ota”. A va B - M1 tugunining “o‘g‘illari”.

Asosiy ta’riflar

• 
  Agar ikkita tugun yo‘naltirilgan yoy bilan bog‘langan bo‘lsa (x→y), u holda
  

x - o‘tmishdosh (ota-ona),

y - voris (o‘g‘il, qiz).

• 
  Ildiz - bu ota-onasi bo‘lmagan tugun.
  
• 
  Barg - vorislari bo‘lmagan tugun.
  
• 
  Ichki tugun - bu barg yoki ildiz bo‘lmagan tugun.
  
• 
  Tugunning tartibi - bu uning voris tugunlarining soni.
  
• 
  Daraxt darajasi - uning tugunlarining maksimal tartibi.
  
• 
  Tugunning chuqurligi uning ajdodlari sonini 1 ga orttirilganiga teng.
  
• 
  Daraxtning chuqurligi uning tugunlarining eng katta chuqurligidir.
  
• 
  Yuqorida keltirilgan daraxt 3 daraja (uchlik), 4 chuqurlik, a ildiz tuguni, d, e, g, k, m barglariga ega.
  

Ma’lumotlar ro‘yxatining daraxtlar tartibidagi ko‘rinishi {a b c d e f g k m}

Ildiz tugun(корень)
Ikkinchi daraja tuguni d, e, g, k,m - barglar

Ierarxik tuzilish

Direktor o‘rinbosarlari
O‘qituvchilar
Talabalar
Elementlari o‘rtasida bo‘ysunish munosabatlari o‘rnatiladigan ma’muriy boshqaruv tizimi.

Ierarxik tuzilishdagi graf - uning har qanday ikki tuguni orasida faqat bitta yo‘l bor.