Trait tree_iterators_rs::prelude::OwnedTreeNode
source · pub trait OwnedTreeNodewhere
Self: Sized,{
type OwnedValue: Sized;
type OwnedChildren: Iterator<Item = Self>;
// Required method
fn get_value_and_children(
self
) -> (Self::OwnedValue, Option<Self::OwnedChildren>);
// Provided methods
fn bfs(self) -> impl TreeIteratorMut<Item = Self::OwnedValue> { ... }
fn dfs_preorder(self) -> impl TreeIteratorMut<Item = Self::OwnedValue> { ... }
fn dfs_postorder(self) -> impl TreeIteratorMut<Item = Self::OwnedValue> { ... }
}
Expand description
A tree node where getting its children consumes its value.
Required Associated Types§
sourcetype OwnedValue: Sized
type OwnedValue: Sized
The value of each node in the tree.
sourcetype OwnedChildren: Iterator<Item = Self>
type OwnedChildren: Iterator<Item = Self>
The type of iterator that can be used to iterate over each node’s children collection.
Required Methods§
sourcefn get_value_and_children(
self
) -> (Self::OwnedValue, Option<Self::OwnedChildren>)
fn get_value_and_children( self ) -> (Self::OwnedValue, Option<Self::OwnedChildren>)
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.
Provided Methods§
sourcefn bfs(self) -> impl TreeIteratorMut<Item = Self::OwnedValue>
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
sourcefn dfs_preorder(self) -> impl TreeIteratorMut<Item = Self::OwnedValue>
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
sourcefn dfs_postorder(self) -> impl TreeIteratorMut<Item = Self::OwnedValue>
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.