-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathrec_to_stack.rs
More file actions
48 lines (42 loc) · 1.06 KB
/
rec_to_stack.rs
File metadata and controls
48 lines (42 loc) · 1.06 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
enum Node {
Node(i32, Box<Node>, Box<Node>),
Empty,
}
impl Node {
fn new(val: i32, left: Node, right: Node) -> Node {
Node::Node(val, Box::new(left), Box::new(right))
}
fn leaf(val: i32) -> Node {
Node::new(val, Node::Empty, Node::Empty)
}
fn empty() -> Node {
Node::Empty
}
}
enum Cont<'a> {
Init(&'a Node),
Right(i32, &'a Node),
}
fn in_order(node: &Node) -> Vec<i32> {
let mut list = vec![];
let mut stack = vec![Cont::Init(node)];
while let Some(frame) = stack.pop() {
match frame {
Cont::Init(Node::Empty) => {}
Cont::Init(Node::Node(v, l, r)) => {
stack.push(Cont::Right(*v, r));
stack.push(Cont::Init(l));
}
Cont::Right(v, r) => {
list.push(v);
stack.push(Cont::Init(r));
}
}
}
list
}
fn main() {
let tree = Node::new(1, Node::leaf(2), Node::new(3, Node::leaf(4), Node::empty()));
let list = in_order(&tree);
println!("{:?}", list);
}