Datastructuren. Practicum 9.


Binary Trees.


A. Binary Trees.

Net als 'linked lists', zijn 'binary trees' dynamische, recursieve structuren. Bomen zijn dynamisch, omdat boomstructuren opgebouwd, ingesnoeid, en geheel gekapt kunnen worden tijdens de programma-uitvoer. Dit is mogelijk, omdat hierbij gebruik wordt gemaakt van pointers. Zoals we weten, maken pointers het mogelijk om dynamische variabelen in het programma te introduceren.
Bomen zijn recursieve structuren, omdat vanuit elk knooppunt in de boom, een boom met dezelfde structuur groeit. Bestudeer bijvoorbeeld maar eens een stamboom, en je ziet al snel de steeds terukerende herhaling die zich hierin voordoet. Dankzij deze recursieve structuur kunnen manipulaties op boomstructuren vaak heel goed recursief geformuleerd en geïmplementeerd worden.

Typedefinities voor 'trees', oftewel bomen, hangen af van het soort boom dat men wil opzetten. Een boom kan nl. vanuit één knooppunt twee of meerdere takken laten uitgaan. 'Binary trees' zijn een speciaal soort bomen. Zij hebben knooppunten waarvanuit maar twee takken komen. Dit betekent dat de knopen geïmplementeerd dienen te worden als records met een aantal velden, waaronder het zgn. 'keyfield', maar waarvan 2 velden als pointervelden moeten worden gedefiniëerd. Het ene pointerveld vertegenwoordigt de boom die aan de linkertak van het betreffende knooppunt hangt, het andere de boom die aan de rechtertak hangt.

Hieronder zijn typedefinities voor knoopunten van een binaire boom gegeven:


type Ref = ^TreeNode;
type TreeNode = record -------------------D1: T1;
-------------------D2: T2;
------------------- .....;
-------------------Dn: Tn;
-------------------LinkLeft: Ref;
-------------------LinkRight: Ref;
----------------end;


TreeNode is een recordtype dat de structuur van een record aangeeft met n aantal gegevensvelden en 2 pointervelden, één die de linkertak vanuit het recordknooppunt voorstelt, een andere die de rechtertak voorstelt. Ref is het pointertype van een pointer die naar zo'n record kan verwijzen. In de record zelf zijn dat de twee pointers aangeduid met LinkLeft (corresponderend met de linkertak) en LinkRight (corresponderend met de rechtertak).

B. Manipulaties met binaire boomstructuren.

Net zoals het geval is bij lijsten, kan het bewerken van bomen recursief en niet recursief plaatsvinden. Een recursieve bewerking ligt vaak voor de hand, omdat de dynamische boomstructuren zelf recursief zijn. Het belangrijkste werk bij lijst- en boommanipulaties bestaat uit herschikkingen van pointers ('resetting of pointers'), waarbij pointervariabelen nieuwe, andere pointerwaarden (verwijzingen) krijgen toegekend. Vaak zijn er extra pointers (hulppointers) nodig om de bewerking goed uit te voeren. Want bedenk: een boomknoop ergens in een boom is alleen te bereiken als er een pointer naar verwijst!

Het bouwen van een binaire boom.

Wil je binaire bomen manipuleren, wil je er bijvoorbeeld knopen uit verwijderen, of wil je er in zoeken, dan moet er al ergens een binaire boom bestaan. Het opbouwen van een binaire boom kan het best recursief gebeuren. Van te voren is het goed om je te realiseren wat voor binaire boom je wilt hebben. Een binaire boom waarin je vervolgens binair wilt zoeken, wordt anders opgebouwd, dan een binaire boom, waarin de 'volgorde' van de inhoud minder van belang is (zie voor het bouwen van een zgn. 'Binary Search Tree' Savitch, Chapter 16, section 4). Ook is het belangrijk om te bepalen of je een mooie gebalanceerde boom wilt bouwen, of dat de boom volledig uit balans mag raken. Hieronder wordt een recursieve functie gegeven die een gebalanceerde binaire boom met n aantal knooppunten bouwt. Voor het gemak laten we de knooppunten bestaan uit records met maar 3 velden: een keyveld dat een integer bevat, en twee pointervelden die respectievelijk naar de rechter- en linkertakken verwijzen.

Typedefinities:


type Ref = ^TreeNode;
type TreeNode = record -------------------key: integer;
-------------------LinkLeft: Ref;
-------------------LinkRight: Ref;
----------------end;


De functie Tree, die een gebalanceerde binaire boom aflevert, bij input van een bepaald aantal knooppunten, ziet er als volgt uit:


Function Tree (n: integer): Ref;
var newnode: Ref;
---x, nl, nr: integer;
{x is keywaarde die de gebruiker invoert}
{nl en nr zijn de aantallen knooppunten die resp. de linker- en de rechterboom vanuit een bepaald knooppunt moeten bevatten, op grond van n en de eis op gebalanceerdheid}
begin {Tree}
---if n = 0 then
{stopconditie voor recursieve aanroepen van de functie Tree}
------Tree:= nil
---else
------begin
---------nl:= n DIV 2;
---------nr:= n - nl - 1;
{het aantal knoopunten wordt netjes verdeeld over de linker- en de rechtertak}
---------read(x);
{de integerwaarde x wordt ingelezen}
---------new(newnode);
{een nieuwe dynamische recordvariabele wordt klaargezet, waarnaar de pointer newnode verwijst}
---------with newnode^ do
{met de recordvariabele waarnaar newnode verwijst moet het volgende gebeuren:}
------------begin
---------------Key:= x;
---------------LinkLeft:= Tree(nl);
---------------LinkRight:= Tree(nr);
{om de linker- en rechterboom vanuit het huidige record te genereren, wordt de functie Tree recursief aangeroepen met het aantal knooppunten voor resp. de linker- en de rechterboom}
------------end;
---------Tree:= newnode;
{de functie moet steeds een pointer afleveren die naar een knooppunt in de boom verwijst. Hier gaat deze pointer verwijzen naar het record waarnaar de hulppointer newnode verwijst. Zo levert de functie uiteindelijk een pointer op die naar het bovenste knooppunt ('root') van de boom verwijst}
------end;
end; {Tree}
.


Het uitschrijven van de inhoud van een binaire boom.

Als je wil weten welke gegevens de knooppunten van een binaire boom bevatten, dan wil je de inhoud van bepaalde velden ergens uitgeprint hebben. Deze inhoud wil je bijvoorbeeld onder elkaar op het scherm uitgeprint zien. Nu moet je eerst een keuze maken in welke volgorde de knooppunten uitgeschreven moeten worden. Hier zijn 3 opties: preorder, inorder, postorder. Stel je kiest voor inorder, dan houdt dit in dat eerst de inhoud van de knooppunten van de linkerboom L wordt uitgeprint, daarna het knooppunt K waarvanuit de linkerboom groeit, en daarna de inhoud van de knooppunten van de rechterboom R, die hangt aan K. De volgende recursieve procedure doet dit werk voor je:


procedure PrintInOrder(P: Ref);
begin
---if P <> NIL then
------begin
---------PrintInOrder(P^.LinkLeft);
---------writeln(P^.D1, .... , P^.Dn);
---------PrintInOrder(P^.LinkRight);
------end;
end;


Oefenopdracht 1 week 9.

  1. Schrijf een OO-programma waarmee de gebruiker eerst een gebalanceerde binaire boom op kan bouwen van knooppunten waarin het keyveld namen bevat, en vervolgens de namen op 3 verschillende manieren kan printen op het scherm: in 'preorder', 'inorder', of 'postorder'.
  2. Gebruik bovenstaande functie Tree om de boom te bouwen.
  3. Gebruik bovenstaande procedure PrintInOrder om de inhoud 'inorder' uit te printen, en als uitgangspunt voor het programmeren van de procedures PrintPreOrder en PrintPostOrder.
  4. Zie je ook kans om de namen in boomstructuur op het scherm te krijgen?

Oefenopdracht 2 week 9.

Maak exercise 15 (p. 649) van de Programming Exercises (16.6) van Chapter 16 (Pointers and Dynamic Data Structures) uit Savitch.