C Academy · leksjon

Traverseringer

In-order, pre-order og post-order.

Leksjon 3 av 413 trinn

Traverseringer er en gratis leksjon i C Academy på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i C Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i C Academy inneholder totalt 4 leksjoner.

Hva er en gjennomgang?

En gjennomgang er en systematisk måte å besøke hver node i et tre nøyaktig én gang på.

De tre klassiske dybde-først-rekkefølgene er in-order, pre-order og post-order. De skiller seg bare i når den gjeldende noden behandles i forhold til deltrærne.

In-order-gjennomgang

In-order besøker det venstre deltreet, deretter noden og til slutt det høyre deltreet.

For et BST skriver dette ut verdiene i stigende sortert rekkefølge, noe som gjør denne gjennomgangen spesielt nyttig for søketrær.

void in_order(Node *root) {
    if (root == NULL) return;
    in_order(root->left);
    printf("%d ", root->value);
    in_order(root->right);
}

Pre-order-gjennomgang

Pre-order besøker noden først, deretter det venstre deltreet og til slutt det høyre deltreet.

Dette er nyttig når De skal kopiere et tre eller lage et prefiksuttrykk, fordi roten skrives ut før barna.

void pre_order(Node *root) {
    if (root == NULL) return;
    printf("%d ", root->value);
    pre_order(root->left);
    pre_order(root->right);
}

Post-order-gjennomgang

Post-order besøker først begge deltrærne og deretter noden til slutt.

Fordi barna behandles før forelderen, er denne rekkefølgen akkurat det De trenger når et tre frigjøres, slik at en node aldri brukes etter at barna er borte.

void post_order(Node *root) {
    if (root == NULL) return;
    post_order(root->left);
    post_order(root->right);
    printf("%d ", root->value);
}

Det felles mønsteret

Alle tre dybde-først-gjennomgangene har samme grunnstruktur: et NULL-basistilfelle, en rekursjon til venstre barn, en rekursjon til høyre barn og et besøkstrinn.

Det er bare plasseringen av besøkstrinnet som bestemmer navnet på rekkefølgen.

/* visit position decides the order:
 * pre  : VISIT, left, right
 * in   : left, VISIT, right
 * post : left, right, VISIT
 */

In-order skriver ut sortert

Dette programmet bygger et lite BST og kjører en in-order-gjennomgang for å demonstrere egenskapen med sortert utskrift.

Verdiene kommer ut fra minst til størst, uavhengig av innsettingsrekkefølgen.

#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;
}

Sammenligning av de tre rekkefølgene

For treet med roten 10, venstre barn 5 og høyre barn 15 blir resultatene forskjellige:

Pre-order gir 10 5 15. In-order gir 5 10 15. Post-order gir 5 15 10. Nodeverdiene er de samme; det er bare tidspunktet for besøket som endres.

/*        10
 *       /  \
 *      5    15
 * pre : 10 5 15
 * in  : 5 10 15
 * post: 5 15 10
 */

Level-order-gjennomgang

Bredde-først, eller level-order, besøker nodene nivå for nivå ovenfra og ned. Dette skjer ikke naturlig rekursivt, men ved hjelp av en kø.

Vi legger roten i køen, tar deretter gjentatte ganger ut en node, skriver den ut og legger barna i køen.

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;
    }
}

Gjennomgangen utfører det faktiske arbeidet

Gjennomganger fungerer som maler for alle operasjoner som må berøre hver node, ikke bare for utskrift.

Bytt ut besøkstrinnet med å summere verdier, finne maksimum eller kopiere noder, så utfører den samme strukturen oppgaven.

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

Kostnaden ved en gjennomgang

Hver gjennomgang besøker hver node én gang, og kjøretiden er derfor proporsjonal med n, antallet noder.

Rekursjonen bruker stakkplass proporsjonal med høyden på treet. Høyden er log(n) når treet er balansert, og n i verste fall.

Alle tre samtidig

Dette programmet skriver ut pre-order, in-order og post-order for det samme treet, slik at De kan sammenligne dem side om side.

Legg merke til at det bare er plasseringen av utskriftskallet som endrer den resulterende sekvensen.

#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;
}

Rask sjekk

Velg riktig gjennomgang for oppgaven.

Besvar den i den interaktive leksjonen

Oppsummering

Dybde-først-gjennomganger deler én rekursiv grunnstruktur; plasseringen av besøkstrinnet gjør dem til pre-order, in-order eller post-order. In-order på et BST gir sortert utskrift, og post-order er den sikre rekkefølgen når treet skal frigjøres.

Level-order er bredde-først og bruker en kø. Alle besøker hver node én gang med kjøretid O(n).

Gratis å komme i gang

Lær deg C med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 39
Leksjoner: 144

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Traverseringer» gratis?

Ja – hele teksten i «Traverseringer» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av C Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i C Academy inneholder totalt 4 leksjoner.

Hva lærer jeg i «Traverseringer»?

In-order, pre-order og post-order. Du øver på C Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med C Academy?

Ingen tidligere erfaring er nødvendig. C Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.

Hvor lang tid tar leksjonen «Traverseringer»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne C Academy-leksjonen?

Ja. Alle C Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til C Academy