Tree traversal. Bomen zijn overal. Ferd van Odenhoven. 15 november 2011

15 november 2011

Doorlopen van bomen

Doorlopen van bomen

Tree traversal Ferd van Odenhoven Fontys Hogeschool voor Techniek en Logistiek Venlo Software Engineering

15 november 2011

ODE/FHTBM

Tree traversal

15 november 2011

1/22

15 november 2011

2/22

Doorlopen van bomen

1

Doorlopen van bomen Bomen Recursieve binaire-boom-algoritmen Doorlopen van bomen Doorlopen van grafen

ODE/FHTBM

Tree traversal

Doorlopen van bomen

Bomen Recursieve binaire-boom-algoritmen Doorlopen van bomen Doorlopen van grafen

Bomen zijn overal We kennen meerdere voorbeelden hoe bomen gebruikt kunnen worden: ter beschrijving van eigenschappen van algoritmen om datastrukturen te gebruiken en te vervaardigen, die concrete realisaties van bomen zijn op andere plaatsen: stambomen, mappenstructuur van bestandsystemen op computers, enz. Bomen Gewortelde bomen Geordende bomen M-voudige bomen en binaire bomen ODE/FHTBM

Tree traversal

15 november 2011

3/22

1

15 november 2011

Doorlopen van bomen

Doorlopen van bomen


Definities voor bomen Definition 5.1 Een binaire boom is een exteren knoop of een interne knoop verbonden met twee binaire bomen, die de linker respectievelijk de rechter subboom genoemd worden van die knoop. Definition 5.2 Een M-voudige boom is een exteren knoop of een interne knoop verbonden met een geordende reeks van M bomen, die ook M-voudige bomen zijn. Definition 5.3 Een woud (forest) kan ook als boom worden gezien, meer precies een geordende boom. Dat is een knoop (wortel (root) genaamd) verbonden met een reeks van disjuncte bomen. Het is een algemenere M-ary boom, omdat de knopen een willekeurig aantal kind-knopen kunnen hebben. Zie Fig 5.22. ODE/FHTBM

Tree traversal

15 november 2011

Doorlopen van bomen

4/22


Boom-eigenschappen en meer definities Property 5.4 Tussen binaire bomen en geordende wouden bestaat een 1 op 1 correspondentie. Definition 5.4 Een gewortelde boom (of ongeordende boom) is een knoop (wortel (root) geheten) naar een verzameling van gewortelde bomen. (Zo’n verzameling is heet een ongeordend woud.) Definition 5.5 Een graaf is een verzameling van knopen met een verzameling van takken, die paren van knopen verbinden, zo dat elk knopenpaar met tenhoogste een tak is verbonden). Meerdere voorwaarden gelden voor de defintie van een boom; bijv. Een boom is een verbonden graaf met N-1 takken. Een andere voorwaarde luidt: een boom is een graaf, waarin elk paar van knopen door precies een pad met elkaar verbonden is. ODE/FHTBM

Tree traversal

15 november 2011

Doorlopen van bomen

5/22


Doorlopen van bomen Binaire bomen hebben twee takken, en hun knopen kunnen daarom in drie ordeningen voorkomen: Preorder node - left - right Inorder left - node - right Postorder left - right - node node left

ODE/FHTBM

Tree traversal

right

15 november 2011

6/22

2

15 november 2011

Doorlopen van bomen

Doorlopen van bomen


Programma 5.14 Pre-order doorlopen, verander de volgorde van methodeaanroepen voor een andere ordening private void traversePreR ( Node h ) { if ( h == null ) return ; h . item . visit (); traverseR ( h . l ); traverseR ( h . r ); } void traverse () { traversePreR ( root ); }

ODE/FHTBM

Tree traversal

Doorlopen van bomen

15 november 2011

7/22


Voorbeeld: pre-oder markeren van liniaal static void ruler ( int l , int r , int h ) { int m = ( l + r )/2; if ( h > 0) { mark (m , h ); ruler (l , m , h -1); ruler (m , r , h -1); } }

ODE/FHTBM

Tree traversal

Doorlopen van bomen

15 november 2011

8/22


Nietrecursieve loop door bomen Nietrecursieve pre-order-loop door bomen Bij de nietrecursieve variant is er een axpliciete stack. Zie programma 5.15 op een van de volgende sheets. Het programma gebruikt de stack om de volgorde bij te houden waarin de knopen bezocht worden. Bij de declaratie van de stack wordt geen maximum aangegeven; we gaan ervan uit dat we geen geheugenproblemen krijgen.

Level-order doorlopen Een andere manier om een boom te doorlopen is level-order: van boven naar beneden bezoek je alle knopen per niveau (level) van links naar rechts voordat je naar het volgende niveau daaronder gaat. Merk op, dat het programma een queue in plaats van een stack gebruikt, ook nu weer zonder een maximum grootte. ODE/FHTBM

Tree traversal

15 november 2011

9/22

3

15 november 2011

Doorlopen van bomen

Doorlopen van bomen


Programma 5.15: Nietrecursieve pre-order doorloop private void traversePreNR ( Node h ) { NodeStack s = new NodeStack (); s . push ( h ); while (! s . empty ()) { h = s . pop (); h . item . visit (); if ( h . r != null ) s . push ( h . r ); if ( h . l != null ) s . push ( h . l ); } }

ODE/FHTBM

Tree traversal

Doorlopen van bomen

15 november 2011

10/22


Programma 5.16: Level-order doorloop private void traverseLevNR ( Node h ) { NodeQueue q = new NodeQueue (); q . put ( h ); while (! q . empty ()) { h = q . get (); h . item . visit (); if ( h . l != null ) q . put ( h . l ); if ( h . r != null ) q . put ( h . r ); } }

ODE/FHTBM

Tree traversal

Doorlopen van bomen

15 november 2011

11/22


Recursieve binaire boom algoritme Enkele nuttige basisberekeningen en operaties. Knopen tellen Hoogte berekenen Boom afdrukken Bomen maken

ODE/FHTBM

Tree traversal

15 november 2011

12/22

4

15 november 2011

Doorlopen van bomen

Doorlopen van bomen


Programma 5.17

private static int count ( Node h ) { if ( h == null ) return 0; return count ( h . l ) + count ( h . r ) +1; } int count () { return count ( root ); } int height () { return height ( root ); }

ODE/FHTBM

Tree traversal

Doorlopen van bomen

15 november 2011

13/22


Programma 5.17a

private static int height ( Node h ) { if ( h == null ) return -1; int u = height ( h . l ) , v = height ( h . r ); if (u > v ) return u +1; else return v +1; }

ODE/FHTBM

Tree traversal

Doorlopen van bomen

15 november 2011

14/22


Programma 5.18 static void printnode ( Item x , int h ) { for ( int i =0; i < h ; i ++) Out . print ( " " ); Out . println ( " [ " + x + " ] " ); } void show () { showR ( root , 0); }

ODE/FHTBM

Tree traversal

15 november 2011

15/22

5

15 november 2011

Doorlopen van bomen

Doorlopen van bomen


Programma 5.18a private static void showR ( Node t , int h ) { if ( t == null ) { printnodeR ( null , h ); return ; } showR ( t .r , h +1); printnode ( t . item , h ); showR ( t .l , h +1); }

ODE/FHTBM

Tree traversal

Doorlopen van bomen

15 november 2011

16/22


Doorlopen van grafen: ’Diepzoeken’ (depth first) Een boom is een graaf en een graaf KAN een boom zijn. Een belangrijke manier om knopen in een graaf te bezoeke is ”depth first” Daarbij moet men bijhouden welke knopen bezocht zijn! Depth-first: van een wortel een kind-knoop bezoeken, daarvan weer de kindknopen bezoeken enz., voordat men andere kindnopen van de wortelknoop gaat bezoeken. Als we alle knopen die we bezoech hebben met elkaar verbinden, volgens het ’bezoekschema’, dan vormen die verbindingen met de knopen een opspannende boom.

ODE/FHTBM

Tree traversal

Doorlopen van bomen

15 november 2011

17/22


Graaf implementatie class Graph { private int Vcnt , Ecnt ; private class Node { int v ; Node next ; Node ( int x , Node t ) { v = x; next = t ; } } private Node adj []; Graph ( int V ) { Vcnt = V ; Ecnt = 0; adj = new Node [ V ]; } void insert ( Edge e ) { int v = e .v , w = e . w ; adj [ v ] = new Node (w , adj [ v ]); if (! digraph ) adj [ w ] = new Node (v , adj [ w ]); Ecnt ++; } } ODE/FHTBM

Tree traversal

15 november 2011

18/22

6

15 november 2011

Doorlopen van bomen Bomen Recursieve binaire-boom-algoritmen Doorlopen van bomen Doorlopen van grafen

Doorlopen van bomen

Graaf: adjacentie matrix representatie

0 1 2 3 4 5 6 7

0 1 1 1 0 0 1 1 1

1 1 1 0 0 0 0 0 1

2 1 0 1 1 0 0 0 1

3 0 0 0 1 1 1 0 0

4 0 0 0 1 1 1 1 1

5 1 0 0 0 1 1 0 0

6 1 0 0 0 1 0 1 0

7 1 1 1 0 0 0 0 1

Figuur: 3.16 (Sedgewick: pagina 121)

In plaats van een matrix kunnen we ook een array van het type Node nemen. Node[] adj = new Node[V]. Deze knopen moeten weten of ze al bezocht zijn. boolean[] visited = new boolean[V]. ODE/FHTBM

Tree traversal

Doorlopen van bomen

15 november 2011

19/22


Programma 5.21 (Sedgewick: pagina 522) private void dfs ( int k ) { visit ( k ); visited [ k ] = true ; for ( Node t = adj [ k ]; t != null ; t = t . next ) { if (! visited [ t . v ]) dfs ( t . v ); } } Als de graaf een boom is, is een recursieve ’depth first search’ beginnend bij de root gelijk aan het preorder doorlopen van de boom. Zie Sedgewick figuren 5.33 und 5.34 voor de details van het voorbeeld met de adjacentie matrix zoal hiervoor werd gegeven. ODE/FHTBM

Tree traversal

Doorlopen van bomen

15 november 2011

20/22


Doorlopen van grafen: ’Breedzoeken’ (breadth first) Een boom is een graaf en een graaf KAN een boom zijn. Een volgende belangrijke wijze waarop men knopen kan bezoeken is ”Breedtezoeken”(breadth first) Breedtezoeken: vanuit de wortel eerst alle kindknopen bezoeken en daarna pas de kinderen van een kin. Ook daarbij moet mem bijhouden welke knopen al bezocht werden! Als we alle knopen die we bezocht hebben met elkaar verbinden, volgens het ’bezoekschema’, dan vormen die verbindingen met de knopen een opspannende boom.

ODE/FHTBM

Tree traversal

15 november 2011

21/22

7

15 november 2011

Doorlopen van bomen

Doorlopen van bomen


Programma 5.22 void bfs ( int k ) { intQUEUE q = new intQUEUE ( V * V ); q . put ( k ); while (! q . empty ()) { if (! visited [ k = q . get ()]) { Node t ; visit ( k ); visited [ k ] = true ; for ( t = adj [ k ]; t != null ; t = t . next ) if (! visited [ t . v ]) q . put ( t . v ); } } }

Vergelijk dit programma met het programma voor de level-order tree-traversal. ODE/FHTBM

Tree traversal

15 november 2011

22/22

8

Tree traversal. Bomen zijn overal. Ferd van Odenhoven. 15 november 2011

Recommend Documents