リストと木構造を理解する
リストは要素をリンクでつなぐ線形構造、木は親子関係を持つ階層構造である。配列とは異なるアクセス・挿入削除の特徴を理解する。
この単元で学ぶこと
- 連結リストの意味と役割を説明できる
- 先頭ポインタの意味と役割を説明できる
- 木の意味と役割を説明できる
- 連結リストと木の構造・基本用語・参照関係を図から読み取れる
本文解説
連結リストは各要素が次要素への参照を持ち、位置をたどってアクセスする。木では根・親・子・葉・深さなどの用語を使い、二分木では各ノードの子が高々二つとなる。
連結リスト 要素と次要素への参照をノードとしてつなぐ線形構造。 途中挿入では参照のつなぎ替えが中心になる。
先頭ポインタ リストの最初のノードを指す参照。 空リスト判定や走査開始に使う。
木 ノードを親子関係で接続する階層構造。 根から枝分かれし循環を持たない基本形を扱う。
葉 子を持たないノード。 終端ノードとして扱う。
二分木 各ノードが高々二つの子を持つ木。 左部分木・右部分木を区別する。
リストはnext参照、木は親子・左右・根/葉を明示して図を追う。
A→B→CでB後ろにDを入れるなら、D.nextをC、B.nextをDへ更新する。
図解
重要ポイント
- 連結リスト: 要素と次要素への参照をノードとしてつなぐ線形構造。
- 先頭ポインタ: リストの最初のノードを指す参照。
- 木: ノードを親子関係で接続する階層構造。
- 葉: 子を持たないノード。
- リストは「位置」より参照、木は「順番」より階層関係で読む。
間違えやすい点
- 連結リストを添字で直接アクセスできる配列と同一視しない。
- 木の葉を根と混同しない。
- 参照つなぎ替えの順序で既存ノードへの参照を失わない。
用語解説
- 連結リスト
- 要素と次要素への参照をノードとしてつなぐ線形構造。
- 先頭ポインタ
- リストの最初のノードを指す参照。
- 木
- ノードを親子関係で接続する階層構造。
- 葉
- 子を持たないノード。
- 二分木
- 各ノードが高々二つの子を持つ木。
関連教材
参考資料
教材データに登録された参考リンクです。リンク先の内容や更新日は提供元でご確認ください。
確認問題の出題・採点や学習履歴の保存にはログインが必要です。