Typning af træstrukturer
Modellér indlejrede træknuder med rekursive typer
Typning af træstrukturer er en gratis TypeScript Academy-lektion på CoddyKit. Dette er lektion 2 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i TypeScript Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. TypeScript Academy-kurset indeholder 4 lektioner i alt.
En træknudetype
Træer generaliserer lister: Hver knude har en værdi og et array med underknuder af samme type. Dette er en rekursiv type med et children-array.
type TreeNode<T> = {
value: T;
children: TreeNode<T>[];
};
const leaf: TreeNode<number> = { value: 1, children: [] };
console.log(leaf.value);Opbygning af et lille træ
En knude med underknuder er blot indlejrede objekter. Det tomme array er det naturlige basistilfælde for et blad.
type TreeNode<T> = { value: T; children: TreeNode<T>[] };
const tree: TreeNode<string> = {
value: "root",
children: [
{ value: "a", children: [] },
{ value: "b", children: [] }
]
};
console.log(tree.children.length);Dybere indlejring
Underknuder kan selv have underknuder i enhver dybde, fordi hver underknude selv er en komplet TreeNode.
type TreeNode<T> = { value: T; children: TreeNode<T>[] };
const tree: TreeNode<number> = {
value: 1,
children: [
{ value: 2, children: [{ value: 4, children: [] }] },
{ value: 3, children: [] }
]
};
console.log(tree.children[0].children[0].value);Summering af alle værdier
En rekursiv funktion besøger hver knude og kalder sig selv på dens underknuder, mens den akkumulerer et resultat – et dybde-først-gennemløb.
type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function sum(node: TreeNode<number>): number {
let total = node.value;
for (const child of node.children) total += sum(child);
return total;
}
const t: TreeNode<number> = { value: 1, children: [{ value: 2, children: [] }, { value: 3, children: [] }] };
console.log(sum(t));Optælling af knuder
Den samme gennemløbsstruktur tæller knuder: én for den aktuelle knude plus antallet af knuder i alle undertræer.
type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function count<T>(node: TreeNode<T>): number {
return 1 + node.children.reduce((acc, c) => acc + count(c), 0);
}
const t: TreeNode<string> = { value: "r", children: [{ value: "a", children: [] }] };
console.log(count(t));Sådan finder du den maksimale dybde
Dybden er én større end den maksimale dybde blandt underknuderne eller én for et blad uden underknuder.
type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function depth<T>(node: TreeNode<T>): number {
if (node.children.length === 0) return 1;
return 1 + Math.max(...node.children.map(depth));
}
const t: TreeNode<number> = { value: 1, children: [{ value: 2, children: [{ value: 3, children: [] }] }] };
console.log(depth(t));Sådan samler du alle værdier
Fladgør et træ til et array ved at sammenkæde den aktuelle værdi med de fladgjorte underknuder.
type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function flatten<T>(node: TreeNode<T>): T[] {
return [node.value, ...node.children.flatMap(flatten)];
}
const t: TreeNode<number> = { value: 1, children: [{ value: 2, children: [] }, { value: 3, children: [] }] };
console.log(flatten(t));Sådan søger du i træet
En rekursiv søgning returnerer den første knude, der matcher et prædikat, og gennemgår underknuderne, når den aktuelle knude ikke matcher.
type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function find<T>(node: TreeNode<T>, pred: (v: T) => boolean): TreeNode<T> | null {
if (pred(node.value)) return node;
for (const c of node.children) {
const hit = find(c, pred);
if (hit) return hit;
}
return null;
}
const t: TreeNode<number> = { value: 1, children: [{ value: 5, children: [] }] };
console.log(find(t, v => v === 5)?.value);Sådan mapper du et træ
Transformér hver værdi, mens strukturen bevares, ved rekursivt at mappe værdien og underknuderne.
type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function mapTree<T, U>(node: TreeNode<T>, fn: (v: T) => U): TreeNode<U> {
return { value: fn(node.value), children: node.children.map(c => mapTree(c, fn)) };
}
const t: TreeNode<number> = { value: 1, children: [{ value: 2, children: [] }] };
console.log(mapTree(t, x => x * 100).value);Træer modellerer virkelige data
Filsystemer, DOM-træer, organisationsdiagrammer og AST'er er alle træer. Én rekursiv type kan beskrive dem alle med fuld typesikkerhed.
type TreeNode<T> = { value: T; children: TreeNode<T>[] };
type FileTree = TreeNode<string>;
const fs: FileTree = { value: "/", children: [{ value: "home", children: [] }] };
console.log(fs.value, fs.children[0].value);Blade og grene
En knude er et blad, når children er tom, og ellers en gren. Denne sondring styrer ofte gennemløbslogikken.
type TreeNode<T> = { value: T; children: TreeNode<T>[] };
function isLeaf<T>(node: TreeNode<T>): boolean {
return node.children.length === 0;
}
console.log(isLeaf({ value: 1, children: [] }));Hurtigt tjek: Træstrukturer
Test din forståelse af typning af træstrukturer.
Opsummering: Typning af træstrukturer
Du modellerede træer med TreeNode<T>, hvor hver knude har en værdi og et array med underknuder, og skrev derefter rekursive funktioner til at summere, tælle, søge i og mappe dem.
type TreeNode<T> = { value: T; children: TreeNode<T>[] };
const t: TreeNode<number> = { value: 1, children: [{ value: 2, children: [] }] };
console.log(t.children[0].value);
Lær TypeScript med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 101
- Lektioner
- 352
Ofte stillede spørgsmål
Er lektionen “Typning af træstrukturer” gratis?
Ja — hele teksten til “Typning af træstrukturer” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af TypeScript Academy-kurset, skal du opgradere til CoddyKit PRO. TypeScript Academy-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Typning af træstrukturer”?
Modellér indlejrede træknuder med rekursive typer Du øver dig i TypeScript Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på TypeScript Academy?
Der kræves ingen tidligere erfaring. TypeScript Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 2 af 4.
Hvor lang tid tager lektionen “Typning af træstrukturer”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne TypeScript Academy-lektion?
Ja. Alle TypeScript Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Rekursive typedefinitioner
- Typning af træstrukturer
- JSON-værdityper
- Rekursionsdybde og begrænsninger