Mavzu: binar daraxtlar bilan ishlash reja maʼlumotlar tuzilmasida Binar daraxtlar

Ifodalar daraxtini qurish[tahrir | manbasini tahrirlash]

Daraxtning 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^[2].

Misol[tahrir | manbasini tahrirlash]

Postfiks yozuvidagi kirish: ab + cde + * * Birinchi ikkita belgi operandlar boʻlganligi sababli, bitta tugunli daraxtlar yaratiladi va ularga koʻrsatgichlar stekga suriladi. Qulaylik uchun stek chapdan oʻngga oʻsadi.

Stek chapdan oʻngga oʻsadi
Keyingi belgi „+“ belgisidir. U ikkita koʻrsatgichni daraxtlarga koʻchiradi, yangi daraxt hosil boʻladi va unga koʻrsatgich stekga suriladi.

Yangi daraxtning shakllanishi
Keyin c, d va e oʻqiladi. Har biri uchun bitta tugunli daraxt yaratiladi va mos keladigan daraxtga koʻrsatgich stekga suriladi.

Bir tugunli daraxt yaratish
Davom etishda „+“ belgisi oʻqiladi va u oxirgi ikkita daraxtni birlashtiradi.

Ikki daraxtni birlashtirish

Endi „*“ oʻqiladi. Oxirgi ikkita daraxt koʻrsatkichi ochiladi va ildiz sifatida „*“ belgisi bilan yangi daraxt hosil boʻladi.

Ildiz bilan yangi daraxtni shakllantirish
Nihoyat, oxirgi belgi oʻqiladi. Ikki daraxt birlashtiriladi va oxirgi daraxtda koʻrsatgich stekda qoladi.

Ab + cde + * * ifoda daraxtini yaratish bosqichlari

((5 + z) / −8) * (4 ^ 2) ga ekvivalent ikkilik algebraik ifoda daraxti

Algebraik ifodalar

Algebraik ifoda daraxtlari raqamlar, oʻzgaruvchilar va birlik va ikkilik operatorlarni oʻz ichiga olgan ifodalarni ifodalaydi. Baʼzi umumiy operatorlar × (koʻpaytirish), ÷ (boʻlish), + (qoʻshish), — (ayirish), ^ (koʻrsatkich) va — (inkor). Operatorlar daraxtning ichki tugunlarida, raqamlar va oʻzgaruvchilar barg tugunlarida joylashgan boʻladi^[3]. Ikkilik operatorlar tugunlarida ikkita tugun, birlik operatorlarda esa bitta tugun mavjud.

Ikkilik mantiqiy ifoda daraxtiga ekvivalent ((rost ∨  yolgʻon) ∧ ¬  yolgʻon) ∨  (rost ∨  yolgʻon))