1 本日の学習内容

1.1 前回の復習

前回は，スタックとキューというデータ構造を学習した．

スタックの特徴は，最後に入れたデータが一番最初に取り出されることにある．取り出され るデータは，格納されている最新のデータで，最後に入れられたものが最初に取り出され ることから，LIFO(last in first out, 後入れ先出し)と呼ばれる．図1が スタックのイメージである．

スタックではデータの挿入と取り出しが列の一方からのみに対して，キューは列 の両端から行う．一方がデータの追加で一方がデータの取り出しとして使われる．キュー では，最初に入れたデータが一番最初に取り出されることにある．取り出され るデータは格納されている最古のデータで，最初に入れられたものが最初に取り出され ることから，FIFO(first in first out, 先入れ先出し)と呼ばれる．図2が キューのイメージである．

図 1: スタックのイメージ

図 2: キューのイメージ

1.2 本日の学習内容

本日の学習内容は，ツリーと呼ばれるデータ構造の学習である．教科書 [1]の pp.199-217が範囲である．ここでの学習のゴールは以下の通りである．

• ツリーのイメージができ，問題で与えられたデータの表現方法が分かる．
• 2分木(binary tree)によるデータの挿入追加が分かる．

ホームページ: Yamamoto's laboratory
著者: 山本昌志