【Rust】木構造(tree)の深さ優先探索(depth-first search)

### 行きがけ順(上から左下へ)
下のような木構造の場合、左から順に 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の中から一つだけ探したい場合は、幅優先探索が最も早い。
全ての答えを見つける時、決められた深さまで探索する時は、深さ優先探索がよく使われる。

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