PowerPoint プレゼンテーション - NIPPON INSTITUTE of

システムエンジニアリング
演習（１０月２３日）
復習その２＋α
再帰とマージソート
木と二分木の探索
2015/9/30
1
再帰（階乗の例）

階乗
n! = n×(n-1)×…×2×1
つまり n! = n×(n-1)!

2015/9/30
プログラム
public long factorial (long n) {
if (n <= 1) return 1;
else return n * factorial(n – 1);
}
2
５！
５！
5! = 5*24 = 120が返る
５＊４！
５＊４！
4! = 4*6 = 24が返る
４＊３！
４＊３！
3! = 3*2 = 6が返る
３＊２！
３＊２！
2! = 2*1 = 2が返る
２＊１！
２＊１！
1が返る
１
2015/9/30
１
3
マージソート
{ 4, 2, 5, 7, 3, 6, 1, 9 }
{ 4, 2, 5, 7 } + { 3, 6, 1, 9 }
{ 4, 2 } + { 5, 7 } + { 3, 6 } + {1, 9 }
{4}+{2}+{5}+{7}+{3}+{6}+{1}+
{9}
{ 2, 4 } + { 5, 7 } + { 3, 6 } + {1, 9 }
{ 2, 4, 5, 7 } + { 1, 3, 6, 9 }
{ 1, 2, 3, 4, 5, 6, 7, 9 }
2015/9/30
4
二分木巡回

先行順巡回




中間順巡回




左部分木を巡回
根を訪問
右部分木を巡回
後行順巡回



2015/9/30
根を訪問
左部分木を巡回
右部分木を巡回
左部分木を巡回
右部分木を巡回
根を訪問
5
例：こんな感じで…

2015/9/30
先行順巡回
public static void preorder(binaryTree t) {
if (t != null) {
System.out.print(“ “ + t.node);
preorder(t.left);
preorder(t.right);
}
}
6
深さ優先と幅優先探索



ポインターでつながっていない。
キューとスタックを使って、レベルを覚
えておかなければならない！
腕に憶えのある人は挑戦しよう！
頑張ってね！
2015/9/30
7

Download Report