ツリー構造の型付け
再帰型でネストしたツリーノードをモデル化します。
「ツリー構造の型付け」はCoddyKit上の無料TypeScript Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはTypeScript Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 TypeScript Academyコースには全4レッスンが含まれています。
ツリーノードの型
ツリーはリストを一般化したものです。各ノードは値と、同じ型の子ノードの配列を持ちます。これは children 配列を持つ再帰型です。
type TreeNode<T> = {
value: T;
children: TreeNode<T>[];
};
const leaf: TreeNode<number> = { value: 1, children: [] };
console.log(leaf.value);小さなツリーの構築
子を持つノードは、単にオブジェクトをネストしたものです。空の配列は葉の自然な基底ケースになります。
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);さらに深くネストする
各子ノード自体が完全な 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);すべての値の合計
再帰関数は各ノードを訪れ、子ノードに対して再帰しながら結果を蓄積します。これは深さ優先走査です。
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));ノード数のカウント
同じ走査の形でノード数も数えられます。現在のノードを1つとして数え、すべての部分木の数を加算します。
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));最大深さを求める
深さは、子の中で最も深い深さに1を加えた値です。子がない葉の場合は1です。
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));すべての値を集める
現在の値と、平坦化した子の配列を連結して、ツリーを配列に平坦化します。
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));ツリーを検索する
再帰的な検索では、述語に一致する最初のノードを返します。現在のノードが一致しない場合は、子を調べます。
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);ツリーをマッピングする
値と子を再帰的にマッピングすることで、構造を維持したまま、すべての値を変換します。
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);ツリーは実データをモデル化する
ファイルシステム、DOMツリー、組織図、ASTはすべてツリーです。1つの再帰型で、完全な型安全性を保ちながらこれらすべてを表現できます。
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);葉と枝
childrenが空の場合、そのノードは葉であり、それ以外の場合は枝です。この区別がトラバーサルのロジックを決めることは少なくありません。
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: [] }));クイックチェック：ツリー構造
ツリー構造の型付けについて理解度を確認します。
まとめ：ツリー構造の型付け
TreeNode<T>を使って、各ノードが値と子ノードの配列を持つツリーをモデル化し、それらを合計、カウント、検索、マッピングする再帰関数を作成しました。
type TreeNode<T> = { value: T; children: TreeNode<T>[] };
const t: TreeNode<number> = { value: 1, children: [{ value: 2, children: [] }] };
console.log(t.children[0].value);よくある質問
「ツリー構造の型付け」レッスンは無料ですか？
はい。「ツリー構造の型付け」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、TypeScript Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 TypeScript Academyコースには全4レッスンが含まれています。
「ツリー構造の型付け」で何を学びますか？
再帰型でネストしたツリーノードをモデル化します。 ブラウザで直接実行するハンズオンコードでTypeScript Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
TypeScript Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのTypeScript Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「ツリー構造の型付け」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このTypeScript Academyレッスンでコードを書いて実行できますか？
はい。すべてのTypeScript Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。