[−][src]Trait treers::TreeTraversal
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)
Provided methods
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