Created
May 27, 2023 20:04
-
-
Save collinvandyck/c2f474a82ed4fe2480f39139a6a64c24 to your computer and use it in GitHub Desktop.
first rust binary tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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