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