Datastructuren: Binary tree

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4-6

Datastructuren

Binary tree

Leerdoel

Aan het eind van de les ken je de kenmerken van een binary tree en kan je een binary tree opbouwen aan de hand van een lijst met elementen.

Omschrijf kort de werking van een stack

Wat wordt er bedoeld met het LIFO principe?

Geef de C# code voor de declaratie van een stack met het label "mijnStack".

Bekijk onderstaande C# code. Geef de juiste C# code voor het toevoegen van een element aan deze stack met de waarde "product 1".

Stack mijnStack = new Stack();

Bekijk de C# code. Wat is de uitvoer van het programma?

Stack mijnStack = new Stack();

mijnStack.Push("Koe"); 

mijnStack.Push("Varken");

mijnStack.Push("Kip");

Console.WriteLine(mijnStack.Pop());

1. Koe
2. Varken
3. Kip
4. Niets

Binary tree

Tot nu toe hebben we datastructuren gezien die visueel erg lijken op lijsten. Er bestaan echter ook andere datastructuren. Een daarvan is een binary tree.

Binary tree

Een binary tree ziet er visueel ook uit als een soort boom.

werking

Het eerste, bovenste element wordt het root-element genoemd. De andere elementen worden nodes genoemd: de takken van de boom. Een node zonder sub-nodes wordt ook wel een blaadje (leaf) genoemd.

Binary tree

Opbouw binary tree

Een binary tree wordt op de volgende manier opgebouwd:

Het begint met een root-node. Deze staat bovenaan. Iedere node bestaat zelf weer uit 

0, 1 of 2 nodes.

Bij het vullen van de binary tree geldt de volgende voorwaarde: Controleer of het getal kleiner of groter is dan de node. Is deze kleiner dan komt deze links van de node te staan, is deze groter dan komt deze rechts van de node te staan.

Voorbeeld

Neem deze lijst met elementen: 

6 - 4 - 5 - 8 - 7 - 3 - 9

Oefenen (1)

Neem deze lijst met elementen: 

5 - 4 - 6 - 1 - 2 - 9 - 3 - 7 - 8

Maak de bijbehorende Binary Tree.

Oefenen (2)

Neem deze lijst met elementen: 

25 - 44 - 21 - 75 - 34 - 49 - 51 - 34

Maak de bijbehorende Binary Tree.

Boom in balans

Hoe meer een Binary Tree in balans is, hoe efficienter deze is.

Boom in balans

Vuistregel om te bepalen on een Binary Tree in balans is:

1. De nodes mogen maximaal 1 hoogte van elkaar verschillen
2. De linker subtree is in balans
3. De rechter subtree is in balans

Oefenen (3)

Neem deze lijst met elementen: 

34 - 21 - 36 - 41 - 53 - 44 - 32 - 38 - 39 - 27

Maak de bijbehorende Binary Tree. Is de Binary Tree in balans?

Zelfde getallen

Bevat een Binary Tree dezelfde getallen? Hanteer dan het volgende uitgangspunt:

Alle waarden aan de linkerkant van een node zijn kleiner dan of gelijk aan de node. Alle waarden aan de rechterkant van een node zijn groter dan of gelijk aan de node. 

Oefenen (4)

Neem deze lijst met elementen: 

5 - 6 - 6 - 3 - 3 - 2 - 7 - 8

Maak de bijbehorende Binary Tree.