-
Notifications
You must be signed in to change notification settings - Fork 0
/
bintree.rs
78 lines (65 loc) · 1.93 KB
/
bintree.rs
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
use std::env;
struct Tree{
left: Option<Box<Tree>>,
right: Option<Box<Tree>>,
item: i32
}
impl Tree{
pub fn new(depth: i32, i: i32) -> Tree {
if depth <= 0 { return Tree { item: i , left: None, right: None } }
Tree { left: Some(Box::new(Tree::new(depth - 1, 2 * i - 1))),
right: Some(Box::new(Tree::new(depth - 1, 2 * i))),
item: i }
}
fn itemCheck(&self) -> i32 {
let mut sum : i32 = self.item;
match self.left {
None => return sum,
Some(ref p) => { sum += p.itemCheck() }
}
match self.right {
None => return sum,
Some(ref p) => { sum -= p.itemCheck() }
}
return sum;
}
}
fn walkTree(t: Tree) {
println!("{}", t.item);
match t.left {
Some(nt) => { println!("left -> "); walkTree(*nt) }
None => return
}
match t.right {
Some(nt) => { println!("right -> "); walkTree(*nt) }
None => return
}
}
fn main() {
let mindep = 4;
let args: Vec<_> = env::args().collect();
let depth;
if args.len() > 1 {
depth = args[1].parse::<i32>().unwrap();
} else {
println!("Parameter missing.");
return
}
println!("Depth is : {}", depth);
let stretch = depth + 1;
let checkTree = Tree::new(stretch, 0);
println!("stretch tree of depth {}\t check: {}", stretch, checkTree.itemCheck());
let longLived = Tree::new(depth, 0);
let mut i = mindep;
while i <= depth {
let iterations = 1 << (depth - i + mindep);
let mut check : i32 = 0;
for j in 1 .. iterations+1 {
check += Tree::new(i, j).itemCheck();
check += Tree::new(i, -j).itemCheck();
}
println!("{}\ttrees of depth {}\t check: {}", iterations * 2, i, check);
i += 2;
}
println!("long lived tree of depth {}\t check: {}", depth , longLived.itemCheck());
}