二分木のデータ構造と3種類の走査法（先行順・中間
順・後行順）の理解と実装
【学習内容の構成】
1. 二分木の構造：要素、左部分木ポインタ、右部分木
ポインタの3セルで構成されるレコード
2. 走査法：先行順（根→左→右）、中間順（左→根→
右）、後行順（左→右→根）の3種類
3. 実装演習：C言語による二分木の作成と各走査法の
プログラム実装
• 前提：C言語の基礎、ポインタの理解
• 意義：再帰的データ構造の理解、木構造を用いたアル
ゴリズム設計能力の習得
2
4-1. 二分探索木
3
二分木とは
レコードを次の３つで構成
• 要素を格納するセル
• 左部分木を指すポインタを格納するセル
• 右部分木を指すポインタを格納するセル
4
左部分木
根(root)
右部分木
二分探索木とは
• 二分探索木では，小さい要素を左部分木に，大き
い要素を右部分木に格納する
• 二分探索木を，中間順 (in-order) で走査すると，
要素は整列（ソート）された順になる
5
左部分木
根(root)
右部分木
要素の削除
• 要素の削除は，場合分けで行う
• 削除する要素に子がない場合
• 削除する要素に子が１つある場合
• 削除する要素に子が２つある場合
6
削除する要素に子がない場合
単純に要素を削除する
４を削除
７
５
９
３
１
４
７
５
９
３
１
7
１，９の削除のときも，
単純に要素を削除する
削除する要素に子が１つある場合
要素を削除する．直下の子要素が置き換わる
５を削除
７
５
９
３
１
４
７
９
３
１
8
削除する要素に子が２つある場合
要素を削除する．左部分木の中にある「最大の要
素」を削除の上で，それが置き換わる
７を削除
７
５
９
３
１
４
9
５
９
３
１
４
4-2. 「二分探索木」を実習で
きる
オンラインサイトの紹介
10
11
「二分探索木」を実習できる
オンラインサイトの紹介
パソコン演習
④ 説明が出る．ESC キーを押して，説明を消す
⑤ 左下のメニューで「検索」を選び，
「行く」を選ぶ．表示を確認する．
13
パソコン演習
⑥ 今度は，左下のメニューで「入れる」を選び，
「行く」をクリックする．表示を確認する．
⑦ データが増えるので，確認する
14
