Tree traversal practice

main.rs

#![feature(box_syntax)]

use std::collections::{LinkedList, VecDeque};

use Tree::{Leaf, Node};

pub enum Tree<T> {
  Leaf,
  Node(Box<Tree<T>>, Box<Tree<T>>, T)
}

impl<T> Tree<T> where T : PartialEq
{
  pub fn bfs(&self, el: &T) -> bool {
    let mut queue: VecDeque<&Tree<T>> = VecDeque::new();

    queue.push_back(self);

    while !queue.is_empty() {
      match queue.pop_front() {
        None | Some(&Leaf) => continue,
        Some(&Node(ref lt, ref rt, ref el0)) => {
          if el == el0 {
            return true;
          }

          queue.push_back(&lt);
          queue.push_back(&rt);
        } 
      }
    }

    return false;
  }

  pub fn dfs(&self, el: &T) -> bool {
    match self {
      &Leaf => false,
      &Node(ref lf, ref rt, ref el0) => lf.dfs(el) || el == el0 || rt.dfs(el)
    }
  }

  pub fn inorder(&self) -> LinkedList<&T> {
    match self {
      &Leaf => LinkedList::new(),
      &Node(ref lf, ref rt, ref el) => {
        let mut all = LinkedList::new();
        all.append(&mut lf.inorder());
        all.push_back(el);
        all.append(&mut rt.inorder());
        all
      }
    }
  }

  pub fn preorder(&self) -> LinkedList<&T> {
    match self {
      &Leaf => LinkedList::new(),
      &Node(ref lf, ref rt, ref el) => {
        let mut all = LinkedList::new();
        all.push_back(el);
        all.append(&mut lf.preorder());
        all.append(&mut rt.preorder());
        all
      }
    }
  }

  pub fn postorder(&self) -> LinkedList<&T> {
    match self {
      &Leaf => LinkedList::new(),
      &Node(ref lf, ref rt, ref el) => {
        let mut all = LinkedList::new();
        all.append(&mut lf.postorder());
        all.append(&mut rt.postorder());
        all.push_back(el);
        all
      }
    }
  }

  pub fn levelorder(&self) -> LinkedList<&T> {
    let mut queue = VecDeque::new();
    let mut order = LinkedList::new();

    queue.push_back(self);

    loop {
      match queue.pop_front() {
        Some(&Node(ref lf, ref rt, ref v)) => {
          order.push_back(v);
          queue.push_back(lf);
          queue.push_back(rt);
        }
        Some(&Leaf) => (),
        None => break
      }
    }

    order
  }
}

macro_rules! test_order {
  ($ordered : expr, $expected : expr, $typ : ty) => (
    {
      let ordered: Vec<&$typ> = $ordered.into_iter().collect();

      assert_eq!(ordered, $expected);
    }
  )
}

#[cfg(test)] #[test]
fn tree_tests_01() {
  let tree = Node(
    // Left Subtree LEVEL 1
    box Node(
      // Left Subtree Level 1A
      box Node(
        // Left Subtree Level 1AB
        box Node(
          box Leaf,
          box Leaf,
          11),
        // Right Subtree Level 1AB
        box Node(
          box Leaf,
          box Leaf,
          13),
        17),
      // Right Subtree Level 1A
      box Leaf,
      9),
    // Right Subtree LEVEL 1
    box Leaf,
    1);

  assert!(tree.bfs(&13));
  assert!(tree.bfs(&1));
  assert!(tree.bfs(&11));
  assert!(tree.bfs(&17));
  assert!(tree.bfs(&9));

  assert!(tree.dfs(&13));
  assert!(tree.dfs(&1));
  assert!(tree.dfs(&11));
  assert!(tree.dfs(&17));
  assert!(tree.dfs(&9));

  assert!(!tree.bfs(&19));
  assert!(!tree.dfs(&19));

  test_order!(tree.inorder(), [&11, &17, &13, &9, &1], usize);
}

// Tree_traversal article on wikipedia
#[cfg(test)] #[test]
fn tree_tests_02() {
  let tree = Node(
    box Node(
      box Node(
        box Leaf,
        box Leaf,
        'A'),
      box Node(
        box Node(
          box Leaf,
          box Leaf,
          'C'),
        box Node(
          box Leaf,
          box Leaf,
          'E'),
        'D'),
      'B'),
    box Node(
      box Leaf,
      box Node(
        box Node(
          box Leaf,
          box Leaf,
          'H'),
        box Leaf,
        'I'),
      'G'),
    'F');

  test_order!(tree.preorder(), [&'F', &'B', &'A', &'D', &'C', &'E', &'G', &'I', &'H'], char);
  test_order!(tree.inorder(), [&'A', &'B', &'C', &'D', &'E', &'F', &'G', &'H', &'I'], char);
  test_order!(tree.postorder(), [&'A', &'C', &'E', &'D', &'B', &'H', &'I', &'G', &'F'], char);
  test_order!(tree.levelorder(), [&'F', &'B', &'G', &'A', &'D', &'I', &'C', &'E', &'H'], char);
}