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

システムエンジニアリング
演習(10月23日)
復習その2+α
再帰とマージソート
木と二分木の探索
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!
5! = 5*24 = 120が返る
5*4!
5*4!
4! = 4*6 = 24が返る
4*3!
4*3!
3! = 3*2 = 6が返る
3*2!
3*2!
2! = 2*1 = 2が返る
2*1!
2*1!
1が返る
1
2015/9/30
1
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