Doorlopen
In-order, pre-order en post-order.
Doorlopen is een gratis C Academy-les op CoddyKit. Dit is les 3 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject C Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus C Academy bevat in totaal 4 lessen.
Wat is een doorloop?
Een doorloop is een systematische manier om elk knooppunt in een boom precies één keer te bezoeken.
De drie klassieke diepte-eerstvolgordes zijn in volgorde, voorafgaande volgorde en navolgende volgorde. Ze verschillen alleen in wanneer het huidige knooppunt wordt verwerkt ten opzichte van zijn deelbomen.
Doorloop in volgorde
Bij een doorloop in volgorde bezoek je eerst de linker deelboom, daarna het knooppunt en vervolgens de rechter deelboom.
Voor een BST worden de waarden hiermee in oplopende volgorde afgedrukt. Daarom is dit de nuttigste doorloop voor zoekbomen.
void in_order(Node *root) {
if (root == NULL) return;
in_order(root->left);
printf("%d ", root->value);
in_order(root->right);
}Doorloop in voorafgaande volgorde
Bij een doorloop in voorafgaande volgorde bezoek je eerst het knooppunt, daarna de linker deelboom en vervolgens de rechter deelboom.
Dit is handig voor het kopiëren van een boom of het maken van een prefixexpressie, omdat de wortel vóór zijn kinderen wordt uitgevoerd.
void pre_order(Node *root) {
if (root == NULL) return;
printf("%d ", root->value);
pre_order(root->left);
pre_order(root->right);
}Doorloop in navolgende volgorde
Bij een doorloop in navolgende volgorde bezoek je eerst beide deelbomen en als laatste het knooppunt.
Omdat de kinderen vóór hun ouder worden verwerkt, is deze volgorde precies wat je nodig hebt om een boom vrij te geven. Zo wordt een knooppunt nooit gebruikt nadat zijn kinderen zijn verwijderd.
void post_order(Node *root) {
if (root == NULL) return;
post_order(root->left);
post_order(root->right);
printf("%d ", root->value);
}Het algemene patroon
Alle drie de diepte-eerstdoorlopen delen dezelfde basisstructuur: een NULL-basissituatie, een recursieve aanroep voor het linker kind, een recursieve aanroep voor het rechter kind en een bezoekstap.
Alleen de positie van de bezoekstap bepaalt de naam van de volgorde.
/* visit position decides the order:
* pre : VISIT, left, right
* in : left, VISIT, right
* post : left, right, VISIT
*/In volgorde afdrukken geeft sortering
Dit programma bouwt een kleine BST en voert een doorloop in volgorde uit, waarmee de eigenschap van gesorteerde uitvoer wordt gedemonstreerd.
De waarden verschijnen van klein naar groot, ongeacht de invoegvolgorde.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
void in_order(Node *r){ if(!r) return; in_order(r->left); printf("%d ", r->value); in_order(r->right); }
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7,12};
for(int i=0;i<6;i++) root=insert(root,d[i]);
in_order(root);
printf("\n");
return 0;
}De drie volgordes vergelijken
Voor de boom met wortel 10, links 5 en rechts 15 verschillen de uitvoerreeksen:
De voorafgaande volgorde geeft 10 5 15. De volgorde geeft 5 10 15. De navolgende volgorde geeft 5 15 10. De knooppuntwaarden zijn hetzelfde; alleen het moment van bezoeken verandert.
/* 10
* / \
* 5 15
* pre : 10 5 15
* in : 5 10 15
* post: 5 15 10
*/Doorloop per niveau
Een breedte-eerstdoorloop, of doorloop per niveau, bezoekt knooppunten niveau voor niveau van boven naar beneden. Dit gebeurt niet van nature recursief; hiervoor wordt een wachtrij gebruikt.
We plaatsen de wortel in de wachtrij en halen daarna steeds een knooppunt uit de wachtrij, drukken het af en plaatsen zijn kinderen in de wachtrij.
void level_order(Node *root) {
if (!root) return;
Node *queue[100];
int head = 0, tail = 0;
queue[tail++] = root;
while (head < tail) {
Node *n = queue[head++];
printf("%d ", n->value);
if (n->left) queue[tail++] = n->left;
if (n->right) queue[tail++] = n->right;
}
}Doorlopen voor echt werk
Doorlopen zijn sjablonen voor elke bewerking waarbij elk knooppunt moet worden aangeraakt, niet alleen voor afdrukken.
Vervang de bezoekstap door het optellen van waarden, het zoeken naar een maximum of het kopiëren van knooppunten, en dezelfde structuur voert de taak uit.
int sum_tree(Node *root) {
if (root == NULL) return 0;
return root->value
+ sum_tree(root->left)
+ sum_tree(root->right);
}Kosten van een doorloop
Elke doorloop bezoekt elk knooppunt één keer en duurt daarom evenredig met n, het aantal knooppunten.
De recursie gebruikt stapelruimte die evenredig is met de hoogte van de boom: log(n) bij een gebalanceerde boom en n in het slechtste geval.
Alle drie tegelijk
Dit programma drukt de voorafgaande volgorde, de volgorde en de navolgende volgorde af voor dezelfde boom, zodat je ze naast elkaar kunt vergelijken.
Let erop dat alleen de positie van de afdrukaanroep de resulterende reeks verandert.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
void pre(Node *r){ if(!r) return; printf("%d ", r->value); pre(r->left); pre(r->right); }
void ino(Node *r){ if(!r) return; ino(r->left); printf("%d ", r->value); ino(r->right); }
void post(Node *r){ if(!r) return; post(r->left); post(r->right); printf("%d ", r->value); }
int main(void){
Node *root = cn(10);
root->left = cn(5); root->right = cn(15);
pre(root); printf("\n");
ino(root); printf("\n");
post(root); printf("\n");
return 0;
}Korte controle
Kies de juiste doorloop voor de taak.
Samenvatting
Diepte-eerstdoorlopen delen één recursieve basisstructuur; de positie van de bezoekstap maakt ze voorafgaand, in volgorde of navolgend. Een doorloop in volgorde van een BST levert gesorteerde uitvoer op en een doorloop in navolgende volgorde is de veilige volgorde voor het vrijgeven.
Een doorloop per niveau werkt breedte-eerst en gebruikt een wachtrij. Bij alle doorlopen wordt elk knooppunt één keer bezocht in O(n)-tijd.
Leer C met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 39
- Lessen
- 144
Veelgestelde vragen
Is de les “Doorlopen” gratis?
Ja — de volledige tekst van “Doorlopen” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus C Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus C Academy bevat in totaal 4 lessen.
Wat leer ik in “Doorlopen”?
In-order, pre-order en post-order. Je oefent met C Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met C Academy te beginnen?
Ervaring vooraf is niet nodig. C Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 3 van 4.
Hoe lang duurt de les “Doorlopen”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over C Academy?
Ja. Elke les over C Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.