Skip to content

Instantly share code, notes, and snippets.

@collinvandyck
Created May 27, 2023 20:04
Show Gist options
  • Save collinvandyck/c2f474a82ed4fe2480f39139a6a64c24 to your computer and use it in GitHub Desktop.
Save collinvandyck/c2f474a82ed4fe2480f39139a6a64c24 to your computer and use it in GitHub Desktop.
first rust binary tree
use rand::Rng;
use std::fmt::Display;
fn main() {
let mut rng = rand::thread_rng();
let mut t = Tree::new();
for _ in 0..10 {
let v = rng.gen_range(0..100);
t.add(v)
}
t.traverse();
}
pub trait TreeLike: PartialOrd<Self> + Copy + Display {}
impl<T: PartialOrd<T> + Copy + Display> TreeLike for T {}
#[derive(Debug)]
pub struct Tree<T: TreeLike> {
root: Option<Node<T>>,
}
impl<T: TreeLike> Tree<T> {
pub fn new() -> Tree<T> {
Tree { root: None }
}
pub fn add(&mut self, v: T) {
match self.root.as_mut() {
Some(node) => node.add(v),
None => self.root = Some(Node::new(v)),
}
}
pub fn traverse(&self) {
self.root.iter().for_each(|n| n.traverse())
}
}
#[derive(Debug)]
pub struct Node<T> {
value: T,
left: Option<Box<Node<T>>>,
right: Option<Box<Node<T>>>,
}
impl<T: TreeLike> Node<T> {
fn new(v: T) -> Node<T> {
Node {
value: v,
left: None,
right: None,
}
}
fn new_node(v: T) -> Option<Box<Node<T>>> {
let new_node = Box::new(Node::new(v));
Some(new_node)
}
pub fn add(&mut self, v: T) {
if v < self.value {
match self.left.as_mut() {
Some(node) => node.add(v),
None => self.left = Node::new_node(v),
}
} else {
match self.right.as_mut() {
Some(node) => node.add(v),
None => self.right = Node::new_node(v),
}
}
}
pub fn traverse(&self) {
self.left.iter().for_each(|node| node.traverse());
println!("Value: {}", self.value);
self.right.iter().for_each(|node| node.traverse());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment