二分木のデータ構造と3種類の走査法（先行順・中間
順・後行順）の理解と実装
【学習内容の構成】
1. 二分木の構造：要素、左部分木ポインタ、右部分木
ポインタの3セルで構成されるレコード
2. 走査法：先行順（根→左→右）、中間順（左→根→
右）、後行順（左→右→根）の3種類
3. 実装演習：C言語による二分木の作成と各走査法の
プログラム実装
• 前提：C言語の基礎、ポインタの理解
• 意義：再帰的データ構造の理解、木構造を用いたアル
ゴリズム設計能力の習得
2
3-1. 二分木と走査
3
二分木とは
レコードを次の３つで構成
• 要素を格納するセル
• 左部分木を指すポインタを格納するセル
• 右部分木を指すポインタを格納するセル
4
左部分木
根(root)
右部分木
二分木の走査法
二分木の走査には次の種類がある
• 先行順 (pre-order)
• 中間順 (in-order)
• 後行順 (post-order)
先行順 (pre-order)
• 根ノード，左部分木，右部分木の順
A
B
C
D
E
F G
D, B, E, A, F, C, G
の順に処理を行う
中間順 (in-order)
• 左部分木，根ノード，右部分木の順
A
B
C
D
E
F G
D, B, E, A, F, C, G
の順に処理を行う
①左部分木を辿る
②根を辿る
③右部分木を辿る
後行順 (post-order)
• 左部分木，右部分木，根ノードの順
A
B
C
D
E
F G
D, E, B, F, G, C, A
の順に処理を行う
3-2. 実習
9
実習の指示
• 資料：１０～１７
• 次のことを理解しマスターする
• 二分木の作成
10
ここで作成する木
11
+
1
*
2
3
実習
① ウェブブラウザを起動する
② C Tutor を使いたいので，次の URL を開く
http://www.pythontutor.com/
※ Internet Explorer でうまく動かない場合がある
→ うまく動かないときは Google Chrome を試してください
※ 途中で「Server Busy・・・」というメッセージが出るこ
とがある．
→ 混雑している．少し（数秒から数十秒）待つと自動で表示
が変わる（変わらない場合には，操作をもう一度行ってみ
る）
※ 日本語モードはない．英語で使う
12
③ 「C Tutor」をクリック
13
14
「C (gcc4.8, C11)」になっている
エディタ
実行のためのボタン
最初から main メソッドの
ひな形が入っている
双方向リストの作成
④ 次のプログラムを使う
15
次ページに続く
16
②「Visualize Execution」をクリック．
「Last」をクリック．
結果を確認する．
「Edit this code」をクリックして戻る
17
実行結果
18
レコード
レコード
レコード
レコード
レコード
実習の指示
• 資料：１８～２７
• 次のことを理解しマスターする
• 先行順 (pre-order)
• 中間順 (in-order)
• 後行順 (post-order)
19
先行順 (pre-order)
• プログラムを次のように書き換えなさい
20
次ページに続く
21
実行し，結果を確認しなさい
22
中間順 (in-order)
• プログラムを次のように書き換えなさい
23
次ページに続く
24
実行し，結果を確認しなさい
25
後行順 (post-order)
• プログラムを次のように書き換えなさい
26
次ページに続く
27
実行し，結果を確認しなさい
28
