Bomen, preorder, inorder, ambiguiteit

[RemcoAruba]

Beste allen,

Het principe van inorder, postorder en preorder snap ik. Als ik een boom zie kan ik de bijbehorende lijsten maken. Geen probleem.
Maar onlangs had ik examen (waarvoor ik dus gezakt ben....) en één van de vragen was dat ik een lijst in preorder kreeg, en daarbij de bijbehorende inorder en postorder lijsten moest maken. Ik weet niet meer precies wat de opgave was, maar het leek als volgt:

Gegeven de volgende preorderlijst:
a b c d e f g h i j
Vraag: Wat is hiervan de bijbehorende inorder en postorder lijst.

Mijn vraag is dan: Hoe moet ik dat bepalen. Ik weet toch niet hoeveel subbomen er zijn?
Ik kan wel beginnen met het tekenen van een boom gegeven de preorderlijst:
a is de wortel
Dan de linkerkant:
B is de wortel.
En dan?
Is C een wortel? Of is C een blad?
Op deze wijze kan je toch nooit een goede boom opbouwen?

Het enige verschil was dat de in de opgave geen abcdefghij vermeld stond maar iets van etc....

Wie kan mij op weg helpen?

[arie]

Het ging in die opgave waarschijnlijk om logische expressies, bv:



hier uitgedrukt in de normale (= inorder) vorm.

Kan je deze expressie weergeven in een boom?
(de variabelen zijn daarin de bladeren)

Kan je dan een preorderlijst maken van die boom?

Kan je vervolgens uit die preorderlijst de boom weer opbouwen?


Merk op: precies hetzelfde kan je doen voor normale rekenkundige expressies, bv
8 + ((5 - 3) * 2)

[RemcoAruba]

Hallo Arie,
Van de logische expressie die jij opgeeft kan ik geen boom maken.
Schijnbaar zie ik iets over het hoofd.
Je geeft aan dat het in de inorder vorm staat.
Inorder betekend naar mijn weten:
- Linkerboom in inorder doorlopen
- Wortel
- Rechterboom in inorder doorlopen

Als ik dat nu toepas op de logische expressie dan begin ik links helemaal onderin met het blad A.
Vervolgens V als wortel van blad A.
Maar dan?
Is B het rechterblad van de linkerboom met V als wortel en A als linkerblad?
Zo ja, en wat dan? Hoe ga ik dan verder?
Waar zet ik die --> neer ? Daar kom ik maar niet uit.
Kan je me verder helpen?

Alvast bedankt,

[arie]

Inorder betekend naar mijn weten:
- Linkerboom in inorder doorlopen
- Wortel
- Rechterboom in inorder doorlopen

Klopt.

Als ik dat nu toepas op de logische expressie dan begin ik links helemaal onderin met het blad A.
Vervolgens V als wortel van blad A.
Maar dan?

Je zit goed, maar je maakt het jezelf gemakkelijker als je van de wortel uitgaat:
we hebben:

dan is
- linker boom = a
- wortel =
- rechter boom =

Nu werken we hiervan de linker en rechter boom uit:

[1] linker boom = a = blad, hiermee zijn we klaar

[2] rechter boom:

hiervan is:
- linker boom =
- wortel =
- rechter boom = d


Nu werken we ook van [2] de linker en rechter boom uit:

[2.1] linker boom =
hiervan is
- linker boom = b
- wortel =
- rechter boom = c

[2.2] rechter boom = d = blad = klaar.


In feite heb je steeds:
[logische expressie] = [logische expressie 1] <functie> [logische expressie 2]
waarbij je <functie> als wortel neemt en daarna recursief de takken/deelbomen [logische expressie 1] (= linker tak van de huidige wortel) en [logische expressie 2] (= rechter tak van de huidige wortel) uitwerkt.

Kom je zo verder, kan je nu de volledige boom construeren?


PS:
Merk op dat zonder verdere afspraak over prioriteiten van de functies bij inorder haakjes nodig zijn, anders zou je niet weten of

dit betekent:

of dit:

terwijl deze laatste 2 verschillende betekenissen (en verschillende bomen) hebben.
Hoe zien de pre-order notaties van deze 2 laatste bomen er uit?
Zijn deze ook ambigu?

[RemcoAruba]

Arie, dank je wel.
Nu begrijp ik het.

Voor mijn gemak maak ik van

De vereenvoudigde formule:

Hierdoor kan ik een eenvoudige boom maken met X erin. X wordt dan het "rechterblad".
X staat dan in de rechterboom voor:
die ik weer vereenvoudig naar

Nu kan ik dus weer een stukje van de boom invullen.
Waar ik vervolgens in de linkersubboom van de rechterboom (volg je het nog?) dus weer X uitwerk naar:


De boom die dan ontstaat is:
Wortel is V
Rechterboom/blad = a

Vervolgens is de linkerboom als volgt:
Wortel is
Rechterboom = d
Linkerboom heeft weer als wortel
En linkerblad b, en rechterblad c

Dan vraag je nog de preorder notatie van:
Deze is dan volgens mij:

En van is de preorder:


En volgens mij zijn deze ambigu omdat er niet met haakjes gewerkt wordt. Je weet immers niet wanneer je moet overstappen naar links of rechts.
Mijn denkwijze:

Om hier een boom van te maken als je weet dat het in preorder staat:
is de wortel. Dat is eenvoudig.
Dan a. Deze plaats je als linkerblad.
Dan , en daar is het probleem volgens mij. Je weet immers niet of a een vader is, of dat de als wortel voor de rechterboom fungeert.
Of sla ik nu de plank volledig mis?

[arie]

Je boom van

is OK.
Grafisch gezien:

Code: Selecteer alles

     <of>
    /    \
   a     <en>
        /    \
     <imp>    d
     /   \
    b     c

Dan vraag je nog de preorder notatie van:
Deze is dan volgens mij:

En van is de preorder:


En volgens mij zijn deze ambigu omdat er niet met haakjes gewerkt wordt. Je weet immers niet wanneer je moet overstappen naar links of rechts.

Je preorder formules kloppen, maar deze zijn niet ambigu.

In preorder is een expressie:
[expressie] = <functie> [expressie 1] [expressie 2]
of
[expressie] = <variabele>
de variabelen zijn de bladeren, de functies de wortel/knopen.

Voor elke <functie> mag je een openingshaakje '(' zetten, het bijbehorende sluithaakje ')' volgt nadat de expressie compleet is.
Je mag dus ook schrijven
[expressie] = ( <functie> ( [expressie 1] ) ( [expressie 2] ) )
of
[expressie] = ( <variabele> )

In deze preorder formule

komt het eerste openingshaakje hier:

het volgende symbool is de implicatie (dus weer een functie en geen variabele), hiervoor komt ook een openingshaakje:

Dan variabele a: die kunnen we direct tussen haakjes plaatsen:

dan hetzelfde voor variabele b:

en nu is de expressie <implicatie> [a] compleet (functie gevolgd door 2 nieuwe bomen): dus een sluithaakje volgt:

dan is c weer een complete expressie:

en nu wordt de <of> functie gevolgd door 2 bomen en is ook deze compleet:


De wortel van deze boom is dus de <en>,
met linker boom (<implicatie>(a)(b))
en rechter boom (c).
Er is nu dus maar 1 manier om de haakjes te plaatsen, 1 manier om de boom te maken, dus GEEN ambiguiteit.

Lukt je dit ook met de tweede boom ?

En met de oorspronkelijke expressie:

Wat is daarvan de preorder formule?
Kan je die preorderformule ook eenduidig terug omzetten naar de boom?

[RemcoAruba]

Hallo Arie,

Als eerste wil ik je alvast danken voor de tijd en moeite die je erin steekt om mij verder te helpen. Ik waardeer dat zeer.
Alvorens je vragen te beantwoorden heb ik zelf nog een vraag;

Bij het plaatsen van de haakjes in de preorder formule kom je op een gegeven moment bij:

En plaats je dus het sluitingshaakje van de implicatie achter de b. Is dat omdat geldt:

In preorder is een expressie:
[expressie] = <functie> [expressie 1] [expressie 2]

Zo ja, dan begrijp ik het. Zo nee, waarom plaats je het sluitingshaakje van de implicatie niet al achter de a?

En als voor preorder geld:
[expressie] = <functie> [expressie 1] [expressie 2]
Wat geld dan voor inorder en postorder?

Alvast bedankt!

[arie]

En plaats je dus het sluitingshaakje van de implicatie achter de b. Is dat omdat geldt:
In preorder is een expressie:
[expressie] = <functie> [expressie 1] [expressie 2]
Zo ja, dan begrijp ik het.

Ja, dat klopt.
We kijken hier naar tweewaardige logische functies: logische functies die op 2 expressies werken: conjunctie (= 'EN'), disjunctie (= "OF") en implicatie.
Het sluithaakje van een <functie> komt bij preorder dus na 2 complete expressies na die functie.

En als voor preorder geld:
[expressie] = <functie> [expressie 1] [expressie 2]
Wat geld dan voor inorder en postorder?
Alvast bedankt!

inorder:
[expressie] = [expressie 1] <functie> [expressie 2]

postorder:
[expressie] = [expressie 1] [expressie 2] <functie>


We hebben al gezien dat voor inorder de haakjesvolgorde niet vastligt:

Als je de implicatie als wortel neemt, dan heb je het schema [expressie]<functie>[expressie]:

maar als je de 'EN' als wortel neemt, heb je ook het geldige schema [expressie]<functie>[expressie]:


De inorder formule

kan dus meer dan 1 betekenis hebben = ambiguiteit.


Postorder verwerk je al inorder, maar dan in spiegelbeeld.
Je begint dan dus achteraan met het sluithaakje van de functie, en werkt dan terug.
Heb je dan (zonder haakjes) wel altijd een unieke interpretatie van je formule?

[RemcoAruba]

Hallo Arie,

Beetje late reactie, maar hartstikke bedankt. Ik heb nu alle opgaven van mijn boek zonder problemen kunnen maken !