Ordening afleiden van andere ordering bij binaire boom

Het forum voor overige vragen betreffende wiskunde uit het hoger onderwijs.
Plaats reactie
amx
Vast lid
Vast lid
Berichten: 38
Lid geworden op: 19 okt 2014, 08:30

Ordening afleiden van andere ordering bij binaire boom

Bericht door amx » 10 nov 2014, 17:20

Ik ben bezig met het bestuderen van de orderingen bij binaire bomen, de preorder, inorder en postorder notatie.

Ik snap wanneer ik een boom bekijk het verschil tussen de verschillende notaties.
Er wordt nu in het boek zonder veel uitleg erbij gevraagd om de notatie van andere notatie af te leiden zonder afbeelding.
Voorbeeld:

Geef de pre- en inorder-lijst van de in postorder gegeven notatie:

a b a + - c d a c - + x x

Zonder haakjes weet ik niet waar ik moet beginnen. Ik heb geprobeerd het uit te tekenen, maar ik kom dan nog niet uit.
Wie kan me een voorzet geven hoe ik dit kan oplossen?

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Ordening afleiden van andere ordering bij binaire boom

Bericht door arie » 10 nov 2014, 17:52

In postorder notatie werken de operaties (+, -, *, etc) op de operanden (= variabelen of expressies / uitdrukkingen) die er direct voor staan:

Voorbeeld:
a b a + - c d a c - + * *
start met 3 variabelen: a, b, a, daar doen we nog niets mee
dan volgt de eerste operatie: '+', die werkt zoals altijd op de laatste 2 variabelen / uitdrukkingen:
a (b + a) - c d a c - + * *
dan volgt '-': die werkt op a en (b + a):
(a - (b + a)) c d a c - + * *
vervolgens 4 variabelen: c, d, a, c, daar doen we nog niets mee
dan volgt -: de laatste 2 variabelen/uitdrukkingen zijn a en c, daarom krijgen we:
(a - (b + a)) c d (a - c) + * *
dan volgt +: de laatste 2 uitdrukkingen zijn d en (a - c), we krijgen daardoor:
(a - (b + a)) c (d + (a - c)) * *
dan *:
(a - (b + a)) (c * (d + (a - c))) *
tenslotte de laatste *:
((a - (b + a)) * (c * (d + (a - c))))

Kan je van deze uitdrukking met haakjes een boom tekenen?
Kan je daarmee de pre-order notatie construeren?

amx
Vast lid
Vast lid
Berichten: 38
Lid geworden op: 19 okt 2014, 08:30

Re: Ordening afleiden van andere ordering bij binaire boom

Bericht door amx » 11 nov 2014, 15:54

Ineens is het duidelijk. Waarvoor dank :)
Ik had na jouw uitleg alle verdere oefensommen goed, behalve een opgave met een negatie erin (dan is het geen binaire boom omdat er een unaire operator in zit). Geweldig!

Afbeelding

Plaats reactie