Kompyuter injiniringi” fakulteti “axborot texnologiyalari” kafedrasi

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: