ソフトウェアエンジニアの技術ブログ：Software engineer tech blog

### 行きがけ順(上から左下へ)
下のような木構造の場合、左から順に 0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6 と探索していく。
0
1 2
3 4 5 6
これは、再帰処理を行う。

struct Tree {
    node: Vec<[i32; 2]>,
}

fn search(pos: usize) {
    let tree = Tree { node: vec![[1, 2], [3, 4], [5, 6], [7, 8],[9, 10], [11, 12], [13, 14], [0, 0], [0, 0], [0, 0], [0, 0],[0, 0],[0, 0],[0, 0],[0, 0]]};
    println!("{}", pos);
    for i in tree.node[pos] {
        if i != 0 {
            search(i.try_into().unwrap());
        }
    }
}

fn main() {
    search(0);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.01s
Running `target/debug/rust`
0
1
3
7
8
4
9
10
2
5
11
12
6
13
14

### 帰りがけ順(子ノード優先して上へ)
下のような木構造の場合、左から順に 3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0 と子ノードから順番に探索していく。一番上が一番最後になる。
0
1 2
3 4 5 6

fn search(pos: usize) {
    let tree = Tree { node: vec![[1, 2], [3, 4], [5, 6], [7, 8],[9, 10], [11, 12], [13, 14], [0, 0], [0, 0], [0, 0], [0, 0],[0, 0],[0, 0],[0, 0],[0, 0]]};
    for i in tree.node[pos] {
        if i != 0 {
            search(i.try_into().unwrap());
        }
    }
    println!("{}", pos);
}

fn main() {
    search(0);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.68s
Running `target/debug/rust`
7
8
3
9
10
4
1
11
12
5
13
14
6
2
0

### 通りがけ順(子ノードから上下上下)
下のような木構造の場合、左から順に 3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6 と子ノードから順番に探索していく。一番右の子ノードが一番最後になる。
0
1 2
3 4 5 6

fn search(pos: usize) {
    let tree = Tree { node: vec![[1, 2], [3, 4], [5, 6], [7, 8],[9, 10], [11, 12], [13, 14], [0, 0], [0, 0], [0, 0], [0, 0],[0, 0],[0, 0],[0, 0],[0, 0]]};
    if tree.node[pos][0] != 0 && tree.node[pos][1] != 0 {
        search(tree.node[pos][0].try_into().unwrap());
        println!("{}", pos);
        search(tree.node[pos][1].try_into().unwrap());
    } else if tree.node[pos][0] != 0 || tree.node[pos][1] != 0 {
        search(tree.node[pos][0].try_into().unwrap());
        println!("{}", pos);
    } else {
        println!("{}", pos);
    }
}

fn main() {
    search(0);
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.26s
Running `target/debug/rust`
7
3
8
1
9
4
10
0
11
5
12
2
13
6
14

最初のif文では子ノードがあれば左を再帰処理、自信をprintして右を再帰処理
2つ目のif文ではどちらかに子ノードがあれば左を再帰処理
2つ目のif文では子ノードがないので自身をprint

帰りがけは完全に子ノードからボトムアップだが、通りがけは左からツリーを作っていくような順番だ。

Treeの中から一つだけ探したい場合は、幅優先探索が最も早い。
全ての答えを見つける時、決められた深さまで探索する時は、深さ優先探索がよく使われる。

基本ロジックはわかったので、応用編を試してみたいですな。

幅優先探索は、木構造で横に順番に探索していく。
木構造をプログラムで表現するには、各ノードの下のノードの番号を配列で持つようにする。
例えば 下のような木構造があった場合、
0
1 2
3 4 5 6

0は1, 2を子ノードとして持つので、[1, 2]
1は3, 4を子ノードとして持つので、[3, 4]
2は5, 6を子ノードとして持つので、[5, 6] となる。

use std::collections::VecDeque;

struct Tree {
    node: Vec<[i32; 2]>,
}

fn main() {
    let tree = Tree { node: vec![[1, 2], [3, 4], [5, 6], [7, 8],[9, 10], [11, 12], [13, 14], [0, 0], [0, 0], [0, 0], [0, 0],[0, 0],[0, 0],[0, 0],[0, 0]]};
    
    let mut data: VecDeque<i32> = [0].into();

    while data.len() > 0 {
        let pos = data.pop_front();
        println!("{:?} ", pos.unwrap());
        for i in tree.node[pos.unwrap() as usize] {
            if i != 0 {
                data.push_back(i);
            }
        }
    }
}

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/rust`
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14

ノードのデータの表現の仕方が勉強になりますね。

fn main() {
    let data = vec![10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
    let target = 50;
    binary_search(data, target);
    
}

fn binary_search(data: Vec<u32>, target: u32) {
    let mut left = 0;
    let mut right = data.len() - 1;
    
    while left <= right {
        let mid = (left + right) / 2;
        if data[mid] == target {
            println!("ターゲットは要素の[{}]です。", mid);
            break;
        } else if data[mid] < target {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
}

Compiling rust v0.1.0 (/home/vagrant/dev/algorithm/rust)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.13s
Running `target/debug/rust`
ターゲットは要素の[4]です。

これは凄い面白いなあ

fn main() {
    let target = 40;
    let mut flg = format!("{}{}", target, "はデータの中にありません");
    let data = [50, 30, 90, 10, 20, 70, 60, 40, 80];
    for d in data {
        if d == 40 {
            flg = format!("{}{}", target, "はデータの中にあります!");
        }
    }
    println!("{}", flg);
}

Compiling rust v0.1.0 (/home/vagrant/dev/algorithm/rust)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.56s
Running `target/debug/rust`
40はデータの中にあります!

### 関数を定義
配列だと、data: [u32; 10] というように要素数を指定しなければならないので、Vectorの方が使い勝手が良い。

fn main() {
    let data = vec![50, 30, 90, 10, 20, 70, 60, 40, 80, 55];
    let target = 40;
    linear_search(data, target);
    
}

fn linear_search(data: Vec<u32>, target: u32) {
    let mut flg = format!("{}{}", target, "はデータの中にありません");
    for d in data {
        if d == 40 {
            flg = format!("{}{}", target, "はデータの中にあります!");
        }
    }
    println!("{}", flg);
}