A binary search tree in rust 0.5. Very mutable, non-functional style. An exercise to try and learn parts of the language.

gistfile1.rs

extern mod std;
use core::cmp::*;

fn main() {
  let b = make_bst::<int>();
	b.add(8);
	b.add(3);
	b.add(6);
	b.add(7);
	b.add(4);
	b.add(1);
	b.add(10);
	b.add(14);
	b.add(13);
	let f = 100;
	let in = b.contains(f);
	io::println(fmt!("%?", b));
	io::println(fmt!("%d? %?", f, in));
}

enum Maybe<T: Ord Eq>{
	None,
	Some(@Node<T>)
}

struct Node<T: Ord Eq> {
	Data: T,
	mut Left: @Maybe<T>,
	mut Right: @Maybe<T>
}

struct BST<T: Ord Eq> {
	mut Root: @Maybe<T>
}

fn BST_add<T: Ord Eq>(t: &BST<T>, d: T) {
	match *t.Root {
		None => t.Root = @Some(@Node{Data: d, Left: @None, Right: @None}),
		Some(r) => node_add(r, d)
	};
}

fn node_add<T: Ord Eq>(n: &Node<T>, d: T) {
	if d < n.Data {
		match *n.Left {
			None => n.Left = @Some(@Node{Data: d, Left: @None, Right: @None}),
			Some(s) => node_add(s, d)
		};
	}
	else {
		match *n.Right {
			None => n.Right = @Some(@Node{Data: d, Left: @None, Right: @None}),
			Some(s) => node_add(s, d)
		};
	}
}

fn BST_contains<T: Ord Eq>(t: &BST<T>, i: T) -> bool {
	match *t.Root {
		None => false,
		Some(n) => node_contains(n, i)
	}
}

fn node_contains<T: Ord Eq>(n: &Node<T>, i: T) -> bool {
	if n.Data == i {
		true
	}
	else if n.Data < i {
		match *n.Right {
			None => false,
			Some(s) => node_contains(s, i)
		}
	}
	else {
		match *n.Left {
			None => false,
			Some(s) => node_contains(s, i)
		}
	}
}

fn make_bst<T: Ord Eq>() -> BST<T> {
	BST { Root: @None }
}

fn make_node<T: Ord Eq>(i: T) -> Maybe<T> {
	Some(@Node{Data: i, Left: @None, Right: @None})
}

impl<T: Ord Eq> BST<T> {
	fn add(i: T) {
		BST_add(&self, i);
	}

	fn contains(i: T) -> bool {
		BST_contains(&self, i)
	}
}

No remove method. No tests. Next time!