103 lines
2.3 KiB
Rust
103 lines
2.3 KiB
Rust
fn main() {
|
|
part_b();
|
|
}
|
|
|
|
/*```Pseudocode
|
|
let left: int[] = [1, 3, -1, -1, 5, -1, -1]
|
|
let right: int[] = [2, 4, -1, -1, 6, -1, -1]
|
|
let values: int[] = [31, 16, 45, 7, 24, 19, 29]
|
|
```*/
|
|
|
|
fn part_b() {
|
|
let left: Vec<Option<usize>> = vec![Some(1), Some(3), None, None, Some(5), None, None];
|
|
let right: Vec<Option<usize>> = vec![Some(2), Some(4), None, None, Some(6), None, None];
|
|
let values: Vec<usize> = vec![31, 16, 45, 7, 24, 19, 29];
|
|
|
|
println!("POST ORDER");
|
|
post_order(&left, &right, &values, 0);
|
|
|
|
println!("BREADTH FIRST CHEATING");
|
|
breadth_first_cheating(&values);
|
|
|
|
println!("BREADTH FIRST");
|
|
breadth_first(&left, &right, &values, 0);
|
|
}
|
|
|
|
/*```Pseudocode
|
|
fn post_order(left, right, values, node) {
|
|
if (left[node] != -1) {
|
|
post_order(left, right, values, left[node])
|
|
}
|
|
|
|
if (right[node] != -1) {
|
|
post_order(left, right, values, right[node])
|
|
}
|
|
|
|
print(values[node])
|
|
}
|
|
```*/
|
|
|
|
fn post_order(left: &Vec<Option<usize>>, right: &Vec<Option<usize>>, values: &Vec<usize>, node: usize) {
|
|
match left[node] {
|
|
Some(new_node) => post_order(left, right, values, new_node),
|
|
None => {},
|
|
}
|
|
|
|
match right[node] {
|
|
Some(new_node) => post_order(left, right, values, new_node),
|
|
None => {},
|
|
}
|
|
|
|
println!("{}", values[node])
|
|
}
|
|
|
|
/*```Pseudocode
|
|
for i in 0..values.len {
|
|
print(values[i])
|
|
}
|
|
```*/
|
|
|
|
fn breadth_first_cheating(values: &Vec<usize>) {
|
|
for value in values {
|
|
println!("{value}");
|
|
}
|
|
}
|
|
|
|
/*```Pseudocode
|
|
fn breadth_first(left, right, values, root) {
|
|
queue = new Queue
|
|
queue.enqueue(root)
|
|
|
|
while (queue.isNotEmpty()) {
|
|
node = queue.dequeue()
|
|
print(values[node])
|
|
|
|
if (left[node] != -1) {
|
|
queue.enqueue(left[node])
|
|
}
|
|
|
|
if (right[node] != -1) {
|
|
queue.enqueue(right[node])
|
|
}
|
|
}
|
|
}
|
|
```*/
|
|
|
|
fn breadth_first(left: &Vec<Option<usize>>, right: &Vec<Option<usize>>, values: &Vec<usize>, root: usize) {
|
|
let mut queue = std::collections::VecDeque::new();
|
|
queue.push_back(root);
|
|
|
|
while let Some(node) = queue.pop_front() {
|
|
println!("{}", values[node]);
|
|
|
|
if let Some(left_child) = left[node] {
|
|
queue.push_back(left_child);
|
|
}
|
|
|
|
if let Some(right_child) = right[node] {
|
|
queue.push_back(right_child);
|
|
}
|
|
}
|
|
}
|
|
|