Typbestämning av trädstrukturer
Modellera nästlade trädnoder med rekursiva typer.
Typbestämning av trädstrukturer är en gratis lektion i TypeScript Academy på CoddyKit. Detta är lektion 2 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 TypeScript Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i TypeScript Academy innehåller totalt 4 lektioner.
En trädnodstyp
Träd generaliserar listor: varje nod har ett värde och en array med barnnoder av samma typ. Det här är en rekursiv typ med en children-array.
type TreeNode<T> = {
value: T;
children: TreeNode<T>[];
};
const leaf: TreeNode<number> = { value: 1, children: [] };
console.log(leaf.value);Bygga ett litet träd
En nod med barn är bara nästlade objekt. Den tomma arrayen är det naturliga basfallet för ett löv.
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);Nästa djupnivå
Barn kan ha egna barn på godtyckligt djup, eftersom varje barn själv är en fullständig 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);Summera alla värden
En rekursiv funktion besöker varje nod och går rekursivt igenom dess barn samtidigt som ett resultat ackumuleras – en djupförstatraversering.
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));Räkna noder
Samma traverseringsstruktur räknar noder: en för den aktuella noden plus antalet noder i alla delträd.
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));Hitta det maximala djupet
Djupet är ett plus det maximala djupet bland undernoderna, eller ett för ett löv utan undernoder.
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));Samla in alla värden
Platta ut ett träd till en array genom att sammanfoga det aktuella värdet med de utplattade undernoderna.
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ök i trädet
En rekursiv sökning returnerar den första noden som matchar ett predikat och utforskar undernoderna när den aktuella noden inte matchar.
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);Mappa ett träd
Omvandla varje värde samtidigt som strukturen bevaras genom att rekursivt mappa värdet och undernoderna.
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äd representerar verkliga data
Filsystem, DOM-träd, organisationsscheman och AST:er är alla träd. En enda rekursiv typ kan beskriva alla dessa med fullständig typsäkerhet.
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);Löv och grenar
En nod är ett löv när children är tom, och en gren annars. Denna åtskillnad styr ofta traverseringslogiken.
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: [] }));Snabbtest: Trädstrukturer
Kontrollera din förståelse av typning av trädstrukturer.
Sammanfattning: Typning av trädstrukturer
Du modellerade träd med TreeNode<T>, där varje nod har ett värde och en array med undernoder, och skrev sedan rekursiva funktioner för att summera, räkna, söka och mappa över 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 dig TypeScript 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
- 101
- Lektioner
- 352
Vanliga frågor
Är lektionen ”Typbestämning av trädstrukturer” gratis?
Ja – hela texten till ”Typbestämning av trädstrukturer” 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 TypeScript Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i TypeScript Academy innehåller totalt 4 lektioner.
Vad lär jag mig i ”Typbestämning av trädstrukturer”?
Modellera nästlade trädnoder med rekursiva typer. Ni övar på TypeScript 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 TypeScript Academy?
Du behöver inga förkunskaper. Utbildningen i TypeScript 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 2 av 4.
Hur lång tid tar lektionen ”Typbestämning av trädstrukturer”?
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 TypeScript Academy-lektionen?
Ja. Varje TypeScript 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.
Alla lektioner i den här kursen
- Rekursiva typedefinitioner
- Typbestämning av trädstrukturer
- JSON-värdetyper
- Rekursionsdjup och begränsningar