リストと木構造の試験問題への適用
リスト・木の問題では、参照先変更や木の走査順を図に書いて追う。ポインタ更新では「変更前の次ノード」を失わないことが重要。
この単元で学ぶこと
- 挿入の意味と役割を説明できる
- 削除の意味と役割を説明できる
- 前順走査の意味と役割を説明できる
- リストの参照更新と二分木の走査順を具体例で求められる
本文解説
連結リストの挿入・削除では参照のつなぎ替えを扱う。木では前順・中順・後順など、ノードを訪問するタイミングによって出力順が変わる。
挿入 新ノードを既存ノード間へつなぐ操作。 旧nextを保存してから参照を更新する。
削除 対象ノードを参照列から外す操作。 直前ノードのnextを対象の次へ向ける。
前順走査 根→左部分木→右部分木の順に訪問する。 ノードを再帰呼出し前に処理する形。
中順走査 左部分木→根→右部分木の順。 二分探索木では昇順になることがある。
後順走査 左部分木→右部分木→根の順。 子を処理後に親を処理する。
参照更新は矢印を書き、木走査は「根をいつ処理するか」を決めてから左右へ進む。
根A、左B、右Cなら前順A,B,C、中順B,A,C、後順B,C,A。
図解
重要ポイント
- 挿入: 新ノードを既存ノード間へつなぐ操作。
- 削除: 対象ノードを参照列から外す操作。
- 前順走査: 根→左部分木→右部分木の順に訪問する。
- 中順走査: 左部分木→根→右部分木の順。
- 木走査は左/右の順だけでなく、根を処理する位置が違う。
間違えやすい点
- 削除ノードの前後をつながず参照を切らない。
- 前順/中順/後順で根の位置を混同しない。
- 二分探索木の性質と単なる二分木を混同しない。
用語解説
- 挿入
- 新ノードを既存ノード間へつなぐ操作。
- 削除
- 対象ノードを参照列から外す操作。
- 前順走査
- 根→左部分木→右部分木の順に訪問する。
- 中順走査
- 左部分木→根→右部分木の順。
- 後順走査
- 左部分木→右部分木→根の順。
関連教材
参考資料
教材データに登録された参考リンクです。リンク先の内容や更新日は提供元でご確認ください。
確認問題の出題・採点や学習履歴の保存にはログインが必要です。