Traversal
Inorder, preorder och postorder.
Traversal är en gratis lektion i C Academy på CoddyKit. Detta är lektion 3 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för C Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i C Academy innehåller totalt 4 lektioner.
Vad är en traversering?
En traversering är ett systematiskt sätt att besöka varje nod i ett träd exakt en gång.
De tre klassiska djupförst-ordningarna är in-order, pre-order och post-order. De skiljer sig endast åt i när den aktuella noden behandlas i förhållande till sina delträd.
In-order-traversering
In-order besöker först det vänstra delträdet, sedan noden och därefter det högra delträdet.
För ett BST skriver detta ut värdena i stigande sorteringsordning, vilket gör traverseringen särskilt användbar för sökträd.
void in_order(Node *root) {
if (root == NULL) return;
in_order(root->left);
printf("%d ", root->value);
in_order(root->right);
}Pre-order-traversering
Pre-order besöker först noden, sedan det vänstra delträdet och därefter det högra delträdet.
Den är användbar när ett träd ska kopieras eller när ett prefixuttryck ska skapas, eftersom roten skrivs ut före sina barn.
void pre_order(Node *root) {
if (root == NULL) return;
printf("%d ", root->value);
pre_order(root->left);
pre_order(root->right);
}Post-order-traversering
Post-order besöker först båda delträden och noden sist.
Eftersom barnen behandlas före sin förälder är denna ordning precis vad som behövs när ett träd frigörs, så att en nod aldrig används efter att dess barn har tagits bort.
void post_order(Node *root) {
if (root == NULL) return;
post_order(root->left);
post_order(root->right);
printf("%d ", root->value);
}Det gemensamma mönstret
Alla tre djupförst-traverseringar har samma grundstruktur: ett NULL-basfall, ett rekursivt anrop för det vänstra barnet, ett rekursivt anrop för det högra barnet och ett besökssteg.
Det är endast besöksstegets placering som avgör ordningens namn.
/* visit position decides the order:
* pre : VISIT, left, right
* in : left, VISIT, right
* post : left, right, VISIT
*/In-order skriver ut sorterat
Det här programmet bygger ett litet BST och kör en in-order-traversering för att visa egenskapen att resultatet blir sorterat.
Värdena skrivs ut från minst till störst, oavsett i vilken ordning de infogades.
#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;
}Jämförelse av de tre ordningarna
För trädet med roten 10, vänster barn 5 och höger barn 15 blir resultaten olika:
Pre-order ger 10 5 15. In-order ger 5 10 15. Post-order ger 5 15 10. Nodvärdena är desamma; det är endast tidpunkten för besöket som ändras.
/* 10
* / \
* 5 15
* pre : 10 5 15
* in : 5 10 15
* post: 5 15 10
*/Nivåordnad traversering
Breddförst, eller nivåordnad traversering, besöker noder nivå för nivå uppifrån och ned. Den är inte naturligt rekursiv utan använder en kö.
Vi lägger roten i kön och tar sedan upp en nod i taget, skriver ut den och lägger dess barn i kön.
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;
}
}Traversering utför det faktiska arbetet
Traverseringar är mallar för alla operationer som måste beröra varje nod, inte bara för utskrift.
Byt ut besökssteget mot att summera värden, hitta ett största värde eller kopiera noder, så utför samma struktur arbetet.
int sum_tree(Node *root) {
if (root == NULL) return 0;
return root->value
+ sum_tree(root->left)
+ sum_tree(root->right);
}Kostnaden för en traversering
Varje traversering besöker varje nod en gång och tar därför tid proportionell mot n, antalet noder.
Rekursionen använder stackutrymme proportionellt mot trädets höjd, vilket är log(n) när trädet är balanserat och n i värsta fall.
Alla tre samtidigt
Det här programmet skriver ut pre-order, in-order och post-order för samma träd, så att du kan jämföra dem sida vid sida.
Observera hur det endast är placeringen av utskriftsanropet som ändrar den resulterande 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;
}Snabb kontroll
Välj rätt traversering för uppgiften.
Sammanfattning
Djupförst-traverseringar delar samma rekursiva grundstruktur; besöksstegets placering gör dem till pre-order, in-order eller post-order. In-order på ett BST ger sorterade värden, och post-order är den säkra ordningen när ett träd ska frigöras.
Nivåordning är breddförst och använder en kö. Alla besöker varje nod en gång på O(n)-tid.
Lär dig C med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 39
- Lektioner
- 144
Vanliga frågor
Är lektionen ”Traversal” gratis?
Ja – hela texten till ”Traversal” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i C Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i C Academy innehåller totalt 4 lektioner.
Vad lär jag mig i ”Traversal”?
Inorder, preorder och postorder. Ni övar på C Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig C Academy?
Du behöver inga förkunskaper. Utbildningen i C Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.
Hur lång tid tar lektionen ”Traversal”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här C Academy-lektionen?
Ja. Varje C Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.