Strom binárních výrazů - Binary expression tree

A binární výrazový strom je specifický druh a binární strom slouží k reprezentaci výrazy. Dva běžné typy výrazů, které může strom binárních výrazů představovat, jsou algebraický^[1] a booleovský. Tyto stromy mohou představovat výrazy, které obsahují obojí unární a binární operátory.^[1]

Každý uzel binárního stromu, a tedy strom binárního výrazu, má nulu, jedno nebo dvě podřízené položky. Tato omezená struktura zjednodušuje zpracování stromů výrazů.

Přehled

Strom výrazů výrazu (a + b) * c + 7

Listy stromu binárních výrazů jsou operandy, například konstanty nebo názvy proměnných, a ostatní uzly obsahují operátory. Tyto konkrétní stromy jsou binární, protože všechny operace jsou binární, a přestože se jedná o nejjednodušší případ, je možné, aby uzly měly více než dvě děti. Je také možné, aby uzel měl pouze jedno dítě, jako je tomu v případě unárního mínusového operátoru. Strom výrazů, T, lze vyhodnotit použitím operátoru v kořenovém adresáři na hodnoty získané rekurzivním hodnocením levého a pravého podstromu.^[2]

Traverz

Algebraický výraz může být vytvořen ze stromu binárních výrazů rekurzivním vytvořením levého výrazu v závorkách, potom vytištěním operátoru v kořenovém adresáři a nakonec rekurzivním vytvořením výrazu v závorkách vpravo. Tato obecná strategie (vlevo, uzel, vpravo) je známá jako v pořadí procházení Alternativní traverzovou strategií je rekurzivní tisk levého podstromu, pravého podstromu a poté operátora. Tato traverzová strategie je obecně známá jako post-order traversal. Třetí strategií je nejprve vytisknout operátor a poté rekurzivně vytisknout levý a pravý podstrom známý jako předobjednávkový průchod.^[2]

Tyto tři standardní průchody hloubky jsou reprezentacemi tří různých formátů výrazů: infix, postfix a prefix. Výraz infixu je vytvořen v pořadí traversalu, výraz postfixu je vytvořen v post-order traversalu a prefixový výraz je vytvořen v pre-order traversalu.^[3]

Infix traversal

Když je vytištěn výraz infix, musí být na začátek a konec každého výrazu přidána úvodní a závěrečná závorka. Protože každý podstrom představuje podvýraz, vytiskne se úvodní závorka na začátku a závěrečná závorka se vytiskne po zpracování všech jejích podřízených.

Pseudo kód:

Algoritmus infix (strom)/ * Vytiskne výraz infix pro strom výrazů. Pre: tree je ukazatel na strom výrazů Příspěvek: výraz infix byl vytištěn * / -li (strom ne prázdný)    -li (strom žeton je operátor)       tisk (otevřeno závorky)    konec -li    infix (strom vlevo, odjet podstrom)    tisk (strom žeton)    infix (strom že jo podstrom)    -li (strom žeton je operátor)       tisk (zavřít závorky)    konec -li konec -likonec infix

Postfixový přechod

The postfix výraz je tvořen základním postorderovým procházením libovolného binárního stromu. Nevyžaduje závorky.

Pseudo kód:

Algoritmus postfix (strom)/ * Vytiskne výraz postfixu pro strom výrazů. Pre: tree je ukazatel na strom výrazů Příspěvek: výraz postfixu byl vytištěn * / -li (strom ne prázdný)    postfix (strom vlevo, odjet podstrom)    postfix (strom že jo podstrom)    tisk (strom žeton) konec -likonec postfix

Přechod předpony

Pseudo kód:

Algoritmus předpona (strom)/ * Vytiskne výraz předpony pro strom výrazů. Pre: tree je ukazatel na strom výrazů Příspěvek: výraz předpony byl vytištěn * / -li (strom ne prázdný)    tisk (strom žeton)    předpona (strom vlevo, odjet podstrom)    předpona (strom že jo podstrom) konec -likonec předpona

Konstrukce výrazového stromu

Konstrukce stromu probíhá čtením postfixového výrazu po jednom symbolu. Pokud je symbolem operand, vytvoří se strom s jedním uzlem a jeho ukazatel se vloží na zásobník. Pokud je symbolem operátor, ukazatele na dva stromy T1 a T2 jsou vyskočeny ze zásobníku a nový strom, jehož kořen je operátor a jehož levý a pravý potomek ukazují T2 a T1 respektive je vytvořen. Ukazatel na tento nový strom se poté posune do zásobníku.^[4]

Příklad

Vstup v postfixové notaci je: a b + c d e + * * Jelikož první dva symboly jsou operandy, vytvoří se stromy s jedním uzlem a ukazatele na ně se vloží do zásobníku. Pro pohodlí bude zásobník narůstat zleva doprava.

Zásobník roste zleva doprava

Dalším symbolem je „+“. Vyskočí dva ukazatele na stromy, vytvoří se nový strom a ukazatel na něj se vloží do zásobníku.

Vznik nového stromu

Dále jsou čtena písmena c, d ae. Pro každý je vytvořen strom s jedním uzlem a do zásobníku je vložen ukazatel na odpovídající strom.

Vytvoření stromu s jedním uzlem

Pokračuje se načtení znaku „+“, který sloučí poslední dva stromy.

Sloučení dvou stromů

Nyní je přečteno '*'. Poslední dva ukazatele stromu se vyskočí a vytvoří se nový strom s kořenem '*'.

Vytvoření nového stromu s kořenem

Nakonec se přečte poslední symbol. Dva stromy jsou sloučeny a ukazatel na poslední strom zůstane v zásobníku.^[5]

Kroky k vytvoření stromu výrazů a b + c d e + * *

Algebraické výrazy

Binární algebraický výrazový strom ekvivalentní k ((5 + z) / -8) * (4 ^ 2)

Stromy algebraických výrazů představují výrazy, které obsahují čísla, proměnné a unární a binární operátory. Některé běžné operátory jsou × (násobení ), ÷ (divize ), + (přidání ), − (odčítání ), ^ (umocňování ), a - (negace ). Provozovatelé jsou obsaženi v vnitřní uzly stromu, s čísly a proměnnými v listové uzly.^[1] Uzly binárních operátorů mají dva podřízené uzly a unární operátoři mají jeden podřízený uzel.

Booleovské výrazy

Binární logický výrazový strom ekvivalentní k ((true

{ displaystyle lor}

Nepravdivé)

{ displaystyle land}

{ displaystyle neg}

Nepravdivé)

{ displaystyle lor}

(skutečný

{ displaystyle lor}

Nepravdivé))

Booleovské výrazy jsou zastoupeny velmi podobně jako algebraické výrazy, jediným rozdílem jsou použité konkrétní hodnoty a operátory. Booleovské výrazy používají skutečný a Nepravdivé jako konstantní hodnoty a operátory zahrnují ${ displaystyle land}$ (A ), ${ displaystyle lor}$ (NEBO ), ${ displaystyle neg}$ (NE ).

Viz také

Reference

^ ^A ^b ^C Bruno R. Preiss (1998). „Expression Trees“. Archivovány od originál 19. ledna 2017. Citováno 20. prosince 2010.
^ ^A ^b Gopal, Arpita. Zvětšování datových struktur. PHI Learning, 2010, str. 352.
^ Richard F. Gilberg a Behrouz A. Forouzan. Datové struktury: Pseudokódový přístup s C.. Thomson Course Technology, 2005, str. 280.
^ Mark Allen Weiss,Datové struktury a analýza algoritmů v C, 2. vydání, Publikace Addison Wesley
^ Gopal, Arpita. Zvětšování datových struktur. PHI Learning, 2010, str. 353.

[brpreiss-1] A ^b ^C Bruno R. Preiss (1998). „Expression Trees“. Archivovány od originál 19. ledna 2017. Citováno 20. prosince 2010.

[Gopal2010-2] A ^b Gopal, Arpita. Zvětšování datových struktur. PHI Learning, 2010, str. 352.

[Gilberg-3] Richard F. Gilberg a Behrouz A. Forouzan. Datové struktury: Pseudokódový přístup s C.. Thomson Course Technology, 2005, str. 280.

[4] Mark Allen Weiss,Datové struktury a analýza algoritmů v C, 2. vydání, Publikace Addison Wesley

[Gopal2010.353-5] Gopal, Arpita. Zvětšování datových struktur. PHI Learning, 2010, str. 353.

[1]

[2]

[3]

[4]

[5]