Ikkilik ifoda daraxti - Binary expression tree

A ikkilik ifoda daraxti a ning o'ziga xos turi ikkilik daraxt vakili qilish uchun ishlatilgan iboralar. Ikkilik iboralar daraxti ko'rsatishi mumkin bo'lgan ikkita keng tarqalgan iboralar turi algebraik^[1] va mantiqiy. Ushbu daraxtlar ikkalasini ham o'z ichiga olgan iboralarni aks ettirishi mumkin unary va ikkilik operatorlar.^[1]

Ikkilik daraxtning har bir tugunida va shuning uchun ikkitomonlama ifoda daraxtida nol, bitta yoki ikkita bola bo'ladi. Ushbu cheklangan tuzilish ifoda daraxtlarini qayta ishlashni osonlashtiradi.

Umumiy nuqtai

(A + b) * c + 7 ifodaning ifoda daraxti

Ikkilik ifoda daraxtining barglari doimiylar yoki o'zgaruvchan nomlar kabi operandlar bo'lib, boshqa tugunlarda operatorlar mavjud. Ushbu maxsus daraxtlar ikkitomonlama bo'ladi, chunki barcha operatsiyalar ikkilikdir va bu eng oddiy holat bo'lsa-da, tugunlarda ikkitadan ortiq bola tug'ilishi mumkin. Tugunda bitta bolali bo'lishi ham mumkin, xuddi unary minus operatorida bo'lgani kabi. Ifoda daraxti, T, operatorni ildizda chap va o'ng pastki daraxtlarni rekursiv ravishda baholash natijasida olingan qiymatlarga qo'llash orqali baholash mumkin.^[2]

Traversal

Ikkilik ifodalar daraxtidan algebraik ifodani rekursiv ravishda chap qavatli ifodani hosil qilish, so'ngra operatorni ildizga bosib chiqarish va nihoyat, qavslar ichiga kiritilgan o'ng ifodani hosil qilish orqali hosil qilish mumkin. Ushbu umumiy strategiya (chap, tugun, o'ng) an deb nomlanadi tartibda o'tish Muqobil o'tish strategiyasi - chap subtree, o'ng pastki daraxt va keyin operatorni rekursiv ravishda bosib chiqarish. Ushbu o'tish strategiyasi odatda quyidagicha tanilgan buyurtmadan keyingi o'tish. Uchinchi strategiya - avval operatorni bosib chiqarish, so'ngra oldindan buyurtma o'tish deb nomlanuvchi chap va o'ng subtree rekursiv ravishda bosib chiqarish.^[2]

Ushbu uchta standart chuqurlikdan o'tish - bu uch xil ifoda formatining vakili: infiks, postfiks va prefiks. Infiks ifodasi inorder traversal tomonidan, postfiks ifoda post-order traversal tomonidan va prefiks iborasi pre-order traversal tomonidan ishlab chiqariladi.^[3]

Infiks o'tish

Infiks ifodasi bosilganda har bir iboraning boshida va oxirida ochiladigan va yopiladigan qavs qo'shilishi kerak. Har bir kichik daraxt subekspressiyani ifodalaganligi sababli, ochilish qavs boshida va barcha bolalar ishlangandan so'ng yopiladigan qavs bosiladi.

Psevdokod:

Algoritm infiks (daraxt)/ * Ifoda daraxti uchun infiks ifodasini chop eting. Oldindan: daraxt - bu ifoda daraxtiga ko'rsatgich Post: infiks ifodasi bosildi * / agar (daraxt emas bo'sh)    agar (daraxt nishon bu operator)       chop etish (ochiq qavs)    oxiri agar    infiks (daraxt chap kichik daraxt)    chop etish (daraxt nishon)    infiks (daraxt to'g'ri kichik daraxt)    agar (daraxt nishon bu operator)       chop etish (yaqin qavs)    oxiri agar oxiri agaroxiri infiks

Postfiks o'tish

The postfiks ifoda har qanday ikkilik daraxtning post postorder traversalidan hosil bo'ladi. Buning uchun qavs kerak emas.

Psevdokod:

Algoritm postfiks (daraxt)/ * Ifoda daraxti uchun postfix ifodasini chop eting. Oldindan: daraxt - bu ifoda daraxtiga ko'rsatgich Post: postfix ifodasi bosilgan * / agar (daraxt emas bo'sh)    postfiks (daraxt chap kichik daraxt)    postfiks (daraxt to'g'ri kichik daraxt)    chop etish (daraxt nishon) oxiri agaroxiri postfiks

Prefiks o'tish

Psevdokod:

Algoritm prefiks (daraxt)/ * Ekspresiya daraxti uchun prefiks ifodasini chop eting. Oldindan: daraxt - bu ifoda daraxtiga ko'rsatgich Post: prefiks iborasi bosilgan * / agar (daraxt emas bo'sh)    chop etish (daraxt nishon)    prefiks (daraxt chap kichik daraxt)    prefiks (daraxt to'g'ri kichik daraxt) oxiri agaroxiri prefiks

Ekspres daraxtini qurish

Daraxtning qurilishi postfiks ifodasini birma-bir bitta belgini o'qish orqali amalga oshiriladi. Agar belgi operand bo'lsa, bitta tugunli daraxt hosil bo'ladi va uning ko'rsatkichi a ga suriladi suyakka. Agar belgi operator bo'lsa, ikkita daraxtga ishora qiladi T1 va T2 stack va yangi daraxt paydo bo'ldi, uning ildizi operator bo'lib, chap va o'ng bolalari ishora qilmoqda T2 va T1 navbati bilan shakllanadi. Keyin ushbu yangi daraxtga ishora Stekka suriladi.^[4]

Misol

Postfiks yozuvidagi yozuv: a b + c d e + * * Dastlabki ikkita belgi operand bo'lganligi sababli, bitta tugunli daraxtlar hosil bo'ladi va ularga ko'rsatgichlar stakka suriladi. Qulaylik uchun stek chapdan o'ngga o'sadi.

Stak chapdan o'ngga o'sib boradi

Keyingi belgi '+'. U ikkita ko'rsatgichni daraxtlarga ochadi, yangi daraxt paydo bo'ladi va unga ishora stakka suriladi.

Yangi daraxtning shakllanishi

Keyingi, c, d va e o'qiladi. Har biri uchun bitta tugunli daraxt yaratiladi va mos daraxtga ko'rsatgich stakka suriladi.

Bitta tugunli daraxt yaratish

Davom etganda, "+" o'qiladi va u so'nggi ikkita daraxtni birlashtiradi.

Ikki daraxtni birlashtirish

Endi "*" o'qiladi. So'nggi ikkita daraxt ko'rsatgichi qo'yildi va ildiz sifatida '*' bilan yangi daraxt hosil bo'ldi.

Ildiz bilan yangi daraxtni shakllantirish

Nihoyat, oxirgi belgi o'qiladi. Ikki daraxt birlashtirilib, oxirgi daraxtga ko'rsatgich stakada qoladi.^[5]

A b + c d e + * * iboralar daraxtini qurish bosqichlari

Algebraik ifodalar

Ikkilik algebraik ifoda daraxti ((5 + z) / -8) * (4 ^ 2) ga teng

Algebraik ifoda daraxtlari tarkibidagi iboralarni ifodalaydi raqamlar, o'zgaruvchilar, va bitta va ikkilik operatorlar. Umumiy operatorlarning ba'zilari × (ko'paytirish ), ÷ (bo'linish ), + (qo'shimcha ), − (ayirish ), ^ (eksponentatsiya ) va - (inkor ). Operatorlar ichki tugunlar daraxtidagi raqamlar va o'zgaruvchilar bilan barg tugunlari.^[1] Ikkilik operatorlarning tugunlari ikkitadan bolalar tugunlari va bitta operatorlar bitta tugunga ega.

Mantiqiy ifodalar

Ikkilik mantiqiy ifoda daraxti ((true) ga teng

{ displaystyle lor}

yolg'on)

{ displaystyle land}

{ displaystyle neg}

yolg'on)

{ displaystyle lor}

(to'g'ri

{ displaystyle lor}

yolg'on))

Mantiqiy ifodalar algebraik ifodalarga juda o'xshash tarzda ifodalanadi, ularning farqi faqat ishlatiladigan maxsus qiymatlar va operatorlardir. Mantiqiy iboralardan foydalaning to'g'ri va yolg'on doimiy qiymatlar sifatida va operatorlar kiradi ${ displaystyle land}$ (VA ), ${ displaystyle lor}$ (Yoki ), ${ displaystyle neg}$ (YO'Q ).

Shuningdek qarang

Adabiyotlar

^ ^a ^b ^v Bruno R. Preiss (1998). "Ifoda daraxtlari". Arxivlandi asl nusxasi 2017 yil 19 yanvarda. Olingan 20 dekabr, 2010.
^ ^a ^b Gopal, Arpita. Ma'lumotlar strukturasini kattalashtirish. PHI Learning, 2010, p. 352.
^ Richard F. Gilberg va Behruz A. Foruzan. Ma'lumotlar tuzilmalari: C bilan psevdokod yondashuvi. Tomson kursi texnologiyasi, 2005, p. 280.
^ Mark Allen Vayss,Ma'lumotlar strukturasi va algoritm tahlili C da, 2-nashr, Addison Uesli nashrlari
^ Gopal, Arpita. Ma'lumotlar strukturasini kattalashtirish. PHI Learning, 2010, p. 353.

[brpreiss-1] v Bruno R. Preiss (1998). "Ifoda daraxtlari". Arxivlandi asl nusxasi 2017 yil 19 yanvarda. Olingan 20 dekabr, 2010.

[Gopal2010-2] Gopal, Arpita. Ma'lumotlar strukturasini kattalashtirish. PHI Learning, 2010, p. 352.

[Gilberg-3] Richard F. Gilberg va Behruz A. Foruzan. Ma'lumotlar tuzilmalari: C bilan psevdokod yondashuvi. Tomson kursi texnologiyasi, 2005, p. 280.

[4] Mark Allen Vayss,Ma'lumotlar strukturasi va algoritm tahlili C da, 2-nashr, Addison Uesli nashrlari

[Gopal2010.353-5] Gopal, Arpita. Ma'lumotlar strukturasini kattalashtirish. PHI Learning, 2010, p. 353.

[1]

[2]

[3]

[4]

[5]