Tugunlar qo’yish va o’chirish. Daraxtlarni binar ko’rinishga keltirish

Tugunlar qo’yish va o’chirish. Daraxtlarni binar ko’rinishga keltirish.

Reja:
Kirish

• 
  Binar darxtlar haqida tushuncha
  
• 
  Ko`p o`lchamli daraxtni binar ko`rinishga keltirish
  
• 
  Daraxtlar ustida amallar.
  
• 
  Foydalanilgan manbalar
  

Kirish
Binar daraxti ikkilik ifodalarni ifodalash uchun ishlatiladigan dastur tili hisoblanadi. Binar daraxti ifodalashi mumkin boʻlgan ikkita keng tarqalgan ikkilik ifoda turi algebraik va mantiqiy ifoda turlari hisoblanadi. Binar daraxti birlik va ikkilik operatorlarni oʻz ichiga olgan ifodalarni ifodalashi mumkin.

Binar ifoda daraxtining har bir tugunida nol, bitta yoki ikkita son mavjud. Ushbu cheklangan struktura ifoda daraxtlarini qayta ishlashni soddalashtiradi. Ikkilik ifoda daraxtining barglari operandlar, masalan, doimiylar yoki oʻzgaruvchilar nomlari va boshqa tugunlarda operatorlar mavjud. Bu alohida daraxtlar ikkilik boʻladi, chunki barcha operatsiyalar ikkilikdir va bu eng oddiy holat boʻlsa-da, tugunlarda ikkitadan ortiq son boʻlishi mumkin. Bundan tashqari, birlik minus operatorida boʻlgani kabi, tugunning har biri faqat bitta songa ega boʻlishi mumkin. Ifodalar daraxti T ni chap va oʻng pastki daraxtlarni rekursiv baholash natijasida olingan qiymatlarga ildizdagi operatorni qoʻllash orqali baholash mumkin. Algebraik ifoda ikkilik ifoda daraxtidan qavs ichiga olingan chap ifodani rekursiv ishlab chiqarish, soʻngra operatorni ildizga chiqarish va nihoyat, qavs ichiga olingan oʻng ifodani rekursiv ishlab chiqarish orqali ishlab chiqarilishi mumkin. Ushbu umumiy strategiya (chap, tugun, oʻng) tartibli o'tish sifatida tanilgan. Muqobil oʻtish strategiyasi chap pastki daraxtni, oʻng pastki daraxtni va keyin operatorni rekursiv ravishda chop etishdir. Ushbu oʻtish strategiyasi odatda buyruqdan keyingi o'tish sifatida tanilgan. Uchinchi strategiya — avval operatorni chop etish, soʻngra oldindan tartibli oʻtkazish deb nomlanuvchi chap va oʻng pastki daraxtni rekursiv ravishda chop etish.
Ushbu uchta standartdan birinchi oʻtish uch xil ifoda formatlarining ifodasidir: infiks, postfiks va prefiks. Infiks ifodasi tartibni kesib oʻtish orqali, postfiks ifodasi buyruqdan keyingi oʻtish orqali va prefiks ifodasi oldindan tartibli oʻtish orqali hosil boʻladi.
nfiks ifodasi chop etilganda, har bir ifodaning boshiga va oxiriga ochilish va yopish qavslari qoʻshilishi kerak. Har bir pastki daraxt pastki ifodani ifodalaganligi sababli, uning boshida ochilish qavslari va barcha sonlarni qayta ishlagandan soʻng, yopish qavslari chop etiladi. D araxtning qurilishi postfiks ifodasini bir vaqtning oʻzida bitta belgini oʻqish orqali amalga oshiriladi. Agar belgi operand boʻlsa, bitta tugunli daraxt yaratiladi va uning koʻrsatkichi stekga suriladi. Agar belgi operator boʻlsa, ikkita T1 va T2 daraxtiga koʻrsatgichlar stekdan chiqariladi va ildizi operator boʻlgan va chap va oʻng sonlari mos ravishda T2 va T1 ni koʻrsatadigan yangi daraxt hosil boʻladi. Keyin ushbu yangi daraxtga koʻrsatgich stekka suriladi.Agar daraxtni tashkil etuvchi element(tugun)lardan ko`pi bilan 2ta shox chiqsa, yani har bir tugun tuzilmaning ko`pi bilan 2ta tugun bilan bog`langan bo`lsa, u holda bunday daraxt binar daraxt deyiladi.
eslatma
Umumiy holda binary daraxt har bir element 4ta maydonga ega yozuv hisoblanadi.
masaan, quyidagi kalit elementardan binar daraxt quramiz:50, 46, 61, 48, 29, 55, 79. u quyidagi ko`riishga ega bo`ladi:

Izoh
Binar daraxtda key(left_son)оtа
Chаp o`g`il
O`ng o`g`il