[−][src]Trait treers::TreeTraversal

pub trait TreeTraversal<K: Ord, V>: SedgewickMap<K, V> {
    fn pre_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>);

    fn in_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>);

    fn post_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>);

    fn level_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>, level: usize);

    fn traverse(&self, traverse: &Traversals) -> IntoIter<(&K, &V)> { ... }
}

A immutable recursive traversals over Binary Trees.

Pre order In order Post order Level order

Examples

Basic usage:

use treers::bst::BST;
use treers::{SedgewickMap, Traversals, TreeTraversal};

let mut bst: BST<char, i32> = BST::new();
bst.put('c', 3);
bst.put('d', 4);
bst.put('b', 2);
bst.put('a', 1);

// Pre order Traversal by keys
for (a, _) in bst.traverse(&Traversals::PreOrder) {
    print!("{}, ", *a);
}

// In order Traversal by keys
for (a, _) in bst.traverse(&Traversals::InOrder) {
    print!("{}, ", *a);
}

// Post order Traversal by keys
for (a, _) in bst.traverse(&Traversals::PostOrder) {
    print!("{}, ", *a);
}

// Level order Traversal by keys
for (a, _) in bst.traverse(&Traversals::LevelOrder) {
    print!("{}, ", *a);
}

Required methods

fn pre_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>)

fn in_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>)

fn post_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>)

fn level_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>, level: usize)

Loading content...

Provided methods

fn traverse(&self, traverse: &Traversals) -> IntoIter<(&K, &V)>

Loading content...

Implementors

impl<K: Ord + Clone, V: Clone> TreeTraversal<K, V> for BST<K, V>[src]

fn pre_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>)[src]

Returns traverse pre ordered

Examples

Basic usage:

use treers::bst::BST;
use treers::{SedgewickMap, TreeTraversal, Traversals};

let mut bst: BST<char, i32> = BST::new();
bst.put('c', 3);
bst.put('d', 4);
bst.put('b', 2);
bst.put('a', 1);
//    c
//   / \
//  b   d
// /
// a
assert_eq!(bst.traverse(&Traversals::PreOrder).as_slice(),
      &[(&'c', &3), (&'b', &2), (&'a', &1), (&'d', &4)]);

fn in_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>)[src]

Returns traverse in ordered

Examples

Basic usage:

use treers::bst::BST;
use treers::{SedgewickMap, TreeTraversal, Traversals};

let mut bst: BST<char, i32> = BST::new();
bst.put('c', 3);
bst.put('d', 4);
bst.put('b', 2);
bst.put('a', 1);
//    c
//   / \
//  b   d
// /
// a
assert_eq!(bst.traverse(&Traversals::InOrder).as_slice(),
      &[(&'a', &1), (&'b', &2), (&'c', &3), (&'d', &4)]);

fn post_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>)[src]

Returns traverse post ordered

Examples

Basic usage:

use treers::bst::BST;
use treers::{SedgewickMap, TreeTraversal, Traversals};

let mut bst: BST<char, i32> = BST::new();
bst.put('c', 3);
bst.put('d', 4);
bst.put('b', 2);
bst.put('a', 1);
//    c
//   / \
//  b   d
// /
// a
assert_eq!(bst.traverse(&Traversals::PostOrder).as_slice(),
      &[(&'a', &1), (&'b', &2), (&'d', &4), (&'c', &3)]);

fn level_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>, level: usize)[src]

Returns traverse level ordered

Examples

Basic usage:

use treers::bst::BST;
use treers::{SedgewickMap, TreeTraversal, Traversals};

let mut bst: BST<char, i32> = BST::new();
bst.put('c', 3);
bst.put('d', 4);
bst.put('b', 2);
bst.put('a', 1);
//    c
//   / \
//  b   d
// /
// a
assert_eq!(bst.traverse(&Traversals::LevelOrder).as_slice(),
      &[(&'c', &3), (&'b', &2), (&'d', &4), (&'a', &1)]);

impl<K: Ord + Clone, V: Clone> TreeTraversal<K, V> for RedBlackTree<K, V>[src]

fn pre_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>)[src]

Returns traverse post ordered

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::{SedgewickMap, TreeTraversal, Traversals};

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
rbtree.put('a', 1);
rbtree.put('b', 2);
rbtree.put('c', 3);
rbtree.put('d', 4);
rbtree.put('e', 5);
rbtree.put('f', 6);
// Generate a balanced Red-Black Binary Search Tree
//          d(B)           <-- height: 0
//        /      \
//     (R)b       f(B)     <-- height: 1
//      / \      /    \
//   (B)a  c(B) e(R)       <-- height: 2
assert_eq!(rbtree.traverse(&Traversals::PreOrder).as_slice(),
      &[(&'d', &4), (&'b', &2), (&'a', &1),
        (&'c', &3), (&'f', &6), (&'e', &5)]);

fn in_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>)[src]

Returns traverse in ordered

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::{SedgewickMap, TreeTraversal, Traversals};

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
rbtree.put('a', 1);
rbtree.put('b', 2);
rbtree.put('c', 3);
rbtree.put('d', 4);
rbtree.put('e', 5);
rbtree.put('f', 6);
// Generate a balanced Red-Black Binary Search Tree
//          d(B)           <-- height: 0
//        /      \
//     (R)b       f(B)     <-- height: 1
//      / \      /    \
//   (B)a  c(B) e(R)       <-- height: 2
assert_eq!(rbtree.traverse(&Traversals::InOrder).as_slice(),
      &[(&'a', &1), (&'b', &2), (&'c', &3),
        (&'d', &4), (&'e', &5), (&'f', &6)]);

fn post_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>)[src]

Returns traverse post ordered

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::{SedgewickMap, TreeTraversal, Traversals};

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
rbtree.put('a', 1);
rbtree.put('b', 2);
rbtree.put('c', 3);
rbtree.put('d', 4);
rbtree.put('e', 5);
rbtree.put('f', 6);
// Generate a balanced Red-Black Binary Search Tree
//          d(B)           <-- height: 0
//        /      \
//     (R)b       f(B)     <-- height: 1
//      / \      /    \
//   (B)a  c(B) e(R)       <-- height: 2
assert_eq!(rbtree.traverse(&Traversals::PostOrder).as_slice(),
      &[(&'a', &1), (&'c', &3), (&'b', &2),
        (&'e', &5), (&'f', &6), (&'d', &4)]);

fn level_order<'a>(&'a self, vec: &mut Vec<(&'a K, &'a V)>, level: usize)[src]

Returns traverse level ordered

Examples

Basic usage:

use treers::rbtree::RedBlackTree;
use treers::{SedgewickMap, TreeTraversal, Traversals};

let mut rbtree: RedBlackTree<char, i32> = RedBlackTree::new();
rbtree.put('a', 1);
rbtree.put('b', 2);
rbtree.put('c', 3);
rbtree.put('d', 4);
rbtree.put('e', 5);
rbtree.put('f', 6);
// Generate a balanced Red-Black Binary Search Tree
//          d(B)           <-- height: 0
//        /      \
//     (R)b       f(B)     <-- height: 1
//      / \      /    \
//   (B)a  c(B) e(R)       <-- height: 2
assert_eq!(rbtree.traverse(&Traversals::LevelOrder).as_slice(),
      &[            (&'d', &4),               // <-- height: 0
               (&'b', &2), (&'f', &6),        // <-- height: 1
        (&'a', &1), (&'c', &3), (&'e', &5)]); // <-- height: 2
Loading content...