generic-binary-tree.rs

enum BinaryTree<T> {
    Leaf(T),
    Branch(Box<BinaryTree<T>>, T, Box<BinaryTree<T>>),
}

trait TreeWeight<T>
where
    T: std::ops::Add<Output = T> + Copy,
{
    fn tree_weight(&self) -> T;
}

impl<T> TreeWeight<T> for BinaryTree<T>
where
    T: std::ops::Add<Output = T> + Copy,
{
    fn tree_weight(&self) -> T {
        match *self {
            BinaryTree::Leaf(payload) => payload,
            BinaryTree::Branch(ref left, payload, ref right) => {
                left.tree_weight() + payload + right.tree_weight()
            }
        }
    }
}

trait Traversal<T> {
    fn traverse<F>(&self, cb: &F)
    where
        F: Fn(&T);
}

impl<T> Traversal<T> for BinaryTree<T> {
    fn traverse<F>(&self, cb: &F)
    where
        F: Fn(&T),
    {
        match *self {
            BinaryTree::Leaf(ref payload) => cb(payload),
            BinaryTree::Branch(ref left, ref payload, ref right) => {
                left.traverse(cb);
                cb(payload);
                right.traverse(cb);
            }
        }
    }
}

fn print_payload<T>(payload: &T)
where
    T: std::fmt::Display,
{
    println!("payload: {}", payload);
}

fn main() {
    let tree_int = BinaryTree::Branch(
        Box::new(BinaryTree::Leaf(5)),
        10,
        Box::new(BinaryTree::Leaf(3)),
    );
    println!("weight: {}", tree_int.tree_weight());
    tree_int.traverse(&print_payload::<i32>);
    // alternatively: tree_int.traverse(&|p| println!("payload: {}", p));

    let tree_float = BinaryTree::Branch(
        Box::new(BinaryTree::Leaf(12.34)),
        11.22,
        Box::new(BinaryTree::Leaf(56.78)),
    );
    println!("weight: {}", tree_float.tree_weight());
    tree_float.traverse(&print_payload::<f32>);

    let tree_string = BinaryTree::Branch(
        Box::new(BinaryTree::Leaf(String::from("abc"))),
        String::from("def"),
        Box::new(BinaryTree::Leaf(String::from("ghi"))),
    );
    // won't compile: println!("weight: {}", tree_string.tree_weight());
    tree_string.traverse(&print_payload::<String>);
}