C Academy · Les

Boomknopen en -structuur

Modelleer een knoop met pointers.

Les 1 van 413 stappen

Boomknopen en -structuur is een gratis C Academy-les op CoddyKit. Dit is les 1 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 binaire boom?

Een binaire boom is een hiërarchische structuur waarin elke knoop een waarde bevat en verwijzingen heeft naar maximaal twee kinderen: een linker- en een rechterkind.

De bovenste knoop is de wortel. Knopen zonder kinderen zijn bladeren. Door deze vorm zijn binaire bomen geschikt voor snel zoeken, sorteren en recursieve verwerking.

De knoopstructuur

In C modelleren we een knoop met een struct die naast de gegevens twee zelfverwijzende pointers bevat.

Elke pointer wijst naar een andere Node, of naar NULL als er aan die kant geen kind is.

struct Node {
    int value;
    struct Node *left;
    struct Node *right;
};

Waarom zelfverwijzende pointers?

Een knoop kan geen volledige andere knoop als waarde bevatten, omdat daarvoor oneindig veel opslag nodig zou zijn. In plaats daarvan bevat de knoop pointers naar zijn kinderen.

Pointers hebben een vaste grootte. Daardoor blijft de struct een bekende grootte houden, terwijl deze toch naar andere knopen op de heap kan verwijzen.

struct Node {
    int value;
    struct Node *left;   /* 8 bytes on 64-bit */
    struct Node *right;  /* 8 bytes on 64-bit */
};

Een typedef voor gemak

Overal struct Node typen is omslachtig. Met een typedef kunnen we gewoon Node schrijven.

De tag is binnen de struct nog steeds nodig, omdat het type op dat punt nog niet volledig is gedefinieerd.

typedef struct Node {
    int value;
    struct Node *left;
    struct Node *right;
} Node;

Een Node toewijzen

Knopen staan op de heap en worden gemaakt met malloc. We stellen de waarde in en initialiseren beide kindpointers op NULL.

Controleer altijd of malloc niet NULL heeft geretourneerd voordat je het geheugen gebruikt.

Node *create_node(int value) {
    Node *n = malloc(sizeof(Node));
    if (n == NULL) return NULL;
    n->value = value;
    n->left = NULL;
    n->right = NULL;
    return n;
}

Met de hand een kleine boom bouwen

Om de verwijzingen te begrijpen, verbinden we drie knopen handmatig: een wortel met twee kinderen.

Dit programma bouwt de boom en drukt de waarden af. Normaal zouden we hem daarna vrijgeven; dat behandelen we later.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *left;
    struct Node *right;
} Node;

Node *create_node(int v) {
    Node *n = malloc(sizeof(Node));
    n->value = v; n->left = NULL; n->right = NULL;
    return n;
}

int main(void) {
    Node *root = create_node(10);
    root->left = create_node(5);
    root->right = create_node(15);
    printf("%d %d %d\n", root->left->value, root->value, root->right->value);
    return 0;
}

Kleinkinderen bereiken

Je navigeert door de boom door de pijloperator aan elkaar te koppelen. root->left->right gaat eerst naar het linkerkind en vervolgens naar diens rechterkind.

Controleer voordat je een pointer volgt of deze niet NULL is, anders crasht je programma.

/* root
 *   \
 *    right (15)
 *        \
 *         right->right (20)
 */
if (root->right != NULL && root->right->right != NULL)
    printf("%d\n", root->right->right->value);

Knopen recursief tellen

Recursie past natuurlijk bij bomen. Om knopen te tellen heeft een lege deelboom nul knopen; anders tel je deze knoop plus beide deelbomen.

De controle op NULL is het basisgeval dat de recursie stopt.

int count_nodes(Node *root) {
    if (root == NULL) return 0;
    return 1 + count_nodes(root->left)
             + count_nodes(root->right);
}

De hoogte meten

De hoogte van een boom is het langste pad van de wortel naar een blad, gemeten in kanten.

We nemen de grootste van de hoogtes van de twee deelbomen en tellen daar één bij op. Een lege boom krijgt hoogte -1, zodat een enkele knoop hoogte 0 heeft.

int height(Node *root) {
    if (root == NULL) return -1;
    int l = height(root->left);
    int r = height(root->right);
    return 1 + (l > r ? l : r);
}

Bladeren herkennen

Een blad is een knoop zonder kinderen: zowel left als right is NULL.

Deze kleine hulpfunctie is nuttig in veel doorloop- en telroutines.

int is_leaf(Node *n) {
    return n != NULL && n->left == NULL && n->right == NULL;
}

De structuur gebruiken

Hier wordt een kleine boom gebouwd en rapporteren we het aantal knopen en de hoogte met behulp van de recursieve hulpfuncties.

Let erop dat de hulpfuncties nooit uitgaan van een vaste vorm. Ze werken voor elke boom, omdat de recursie de werkelijke pointers volgt.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *left, *right; } Node;

Node *nn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int height(Node *r){ if(!r) return -1; int l=height(r->left),x=height(r->right); return 1+(l>x?l:x); }

int main(void){
    Node *root = nn(10);
    root->left = nn(5); root->right = nn(15);
    root->left->left = nn(2);
    printf("nodes=%d height=%d\n", count(root), height(root));
    return 0;
}

Korte controle

Test je begrip van de knoopstructuur.

Beantwoord dit in de interactieve les

Samenvatting

Een knoop van een binaire boom bevat een waarde en twee zelfverwijzende pointers (left, right), die op NULL worden gezet als ze ontbreken.

We wijzen knopen toe met malloc, koppelen ze handmatig en verwerken ze recursief. De controle op NULL is altijd het basisgeval voor het tellen van knopen, het bepalen van de hoogte en bladtests.

Gratis beginnen

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

Gratis beginnen met leren Bekijk de volledige cursus

Veelgestelde vragen

Is de les “Boomknopen en -structuur” gratis?

Ja — de volledige tekst van “Boomknopen en -structuur” 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 “Boomknopen en -structuur”?

Modelleer een knoop met pointers. 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 1 van 4.

Hoe lang duurt de les “Boomknopen en -structuur”?

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.

Alle lessen in deze cursus

← Terug naar C Academy