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§

source

type OwnedValue: Sized

The value of each node in the tree.

source

type OwnedChildren: Iterator<Item = Self>

The type of iterator that can be used to iterate over each node’s children collection.

Required Methods§

source

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§

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.

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.

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.

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