O’zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti qarshi filiali mustaqil ish Mavzu: Muvozanatlashgan Binar daraxtni

Siklik bo’lmagan (Asiklik) – ixtiyoriy tugunlar juftligida faqat bitta yo’l mavjud.

Binar daraxt – har bir tugunga ikkitadan ko’p bo’lmagan tugunlar bog’langan tartiblangan daraxt.

::= ( ) |

::=

::=

Umumiy holda binar daraxtning har bir elementi (tuguni) to’rtta maydonga ega yozuvdan tashkil topgan bo’ladi.

Shuni esda tutish lozimki, binar daraxt hosil qilinayotganda, otaga nisbatan chap tomondagi o’g’il qiymati kichik, o’ng tomondagi o’g’il qiymati katta bo’lishi lozim.

Masalan, quyidagi kalitli elementlardan binar daraxt quramiz:

{50, 46, 61, 48, 29, 55, 79}. U quyidagi ko’rinishga ega bo’ladi:

Ko’p o’lchamli daraxtni binar ko’rinishga keltirishning noformal algoritmi:

• 
  Daraxtning xar bir tugunida katta o’g’ilga mos chetki chap shoxidan tashqari barcha shoxlari kesib tashlanadi.
  
• 
  Bitta otaga barcha o’g’illari gorizontal chiziq bilan ulanadi.
  
• 
  Hosil qilingan tuzilmaning har bir tugunida katta o’g’il mazkur tugun pastida turgan tugun xisoblanadi (agar u mavjud bo’lsa).
  

Bu algoritm amallar ketma-ketligi quyida keltirilgan: