Trait tree_iterators_rs::prelude::OwnedBinaryTreeNode

source · 
pub trait OwnedBinaryTreeNode
where
    Self: Sized,
{
    type OwnedValue;

    // Required method
    fn get_value_and_children_binary(
        self
    ) -> (Self::OwnedValue, [Option<Self>; 2]);

    // Provided methods
    fn get_value_and_children(
        self
    ) -> (Self::OwnedValue, Option<FlatMap<IntoIter<Option<Self>, 2>, Option<Self>, fn(_: Option<Self>) -> Option<Self>>>) { ... }
    fn bfs(self) -> impl TreeIteratorMut<Item = Self::OwnedValue> { ... }
    fn dfs_preorder(self) -> impl TreeIteratorMut<Item = Self::OwnedValue> { ... }
    fn dfs_inorder(self) -> impl TreeIteratorMut<Item = Self::OwnedValue> { ... }
    fn dfs_postorder(self) -> impl TreeIteratorMut<Item = Self::OwnedValue> { ... }
}
Expand description

A binary tree node where getting its children consumes its value.

Required Associated Types§

source

type OwnedValue

The value of each node in the tree.

Required Methods§

source

fn get_value_and_children_binary(self) -> (Self::OwnedValue, [Option<Self>; 2])

This method gets the value and left and right children from this node, consuming it in the process. The other methods of this trait assume that the children do not contain any circular references. If they do, it will create an infinite loop.

Provided Methods§

source

fn get_value_and_children( self ) -> (Self::OwnedValue, Option<FlatMap<IntoIter<Option<Self>, 2>, Option<Self>, fn(_: Option<Self>) -> Option<Self>>>)

This method gets the value and children from this node, consuming it in the process. The other methods of this trait assume that the ‘Children’ list does not contain any circular references. If it does, it will create an infinite loop.

source

fn bfs(self) -> impl TreeIteratorMut<Item = Self::OwnedValue>

This method retrieves an iterator that can be used to perform Breadth First (Queue - specifically VecDeque-based) searches of a tree.

A Breadth First Search (BFS) is defined as:

A tree traversal that involves breadth-first searching a tree from the top down. Given a tree of the following shape, this traversal type would traverse the elements in the order 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

In this traversal, we scan each level of the tree from left to right before going down to the next level.

ⓘ
       0
      / \
     1   2
    / \ / \
   3  4 5  6
          /
         7
          \
           8
          /
         9
          \
          10
source

fn dfs_preorder(self) -> impl TreeIteratorMut<Item = Self::OwnedValue>

This method retrieves an iterator that can be used to perform Depth First Preorder searches of a tree.

A Depth First Preorder search is defined as:

A tree traversal that involves depth-first searching a tree from the top down. Given a tree of the following shape, this traversal type would traverse the elements in the order 0, 1, 3, 4, 2, 5, 6, 7, 8, 9, 10.

In this traversal, each node will only be traversed before any of its children have been traversed.

ⓘ
       0
      / \
     1   2
    / \ / \
   3  4 5  6
          /
         7
          \
           8
          /
         9
          \
          10
source

fn dfs_inorder(self) -> impl TreeIteratorMut<Item = Self::OwnedValue>

This method retrieves an iterator that can be used to perform Depth First In Order searches of a tree.

A Depth First In Order search is defined as:

A tree traversal that involves depth-first searching a tree from the left to the right. Given a tree of the following shape, this traversal type would traverse the elements in the order 3, 1, 4, 0, 5, 2, 7, 9, 10, 8, 6.

In this traversal, each node will be traversed after its left child and before its right child.

ⓘ
       0
      / \
     1   2
    / \ / \
   3  4 5  6
          /
         7
          \
           8
          /
         9
          \
          10
source

fn dfs_postorder(self) -> impl TreeIteratorMut<Item = Self::OwnedValue>

This method retrieves an iterator that can be used to perform Depth First Postorder searches of a tree.

A Depth First Postorder search (referred to as DFS Postorder) is defined as:

A tree traversal that involves depth-first searching a tree from the bottom up. Given a tree of the following shape, this traversal type would traverse the elements in the order 3, 4, 1, 5, 10, 9, 8, 7, 6, 2, 0.

In this traversal, each node will only be traversed after all of its children have been traversed.

ⓘ
       0
      / \
     1   2
    / \ / \
   3  4 5  6
          /
         7
          \
           8
          /
         9
          \
          10

This traversal type guarantees that getChildren() will only be called once per node of the tree.

Object Safety§

This trait is not object safe.

Implementors§