Struct Tree 

pub struct Tree<T> { /* private fields */ }

A tree structure that represents a hierarchical collection of nodes.

The Tree struct is a fundamental data structure in Radiate’s genetic programming system. It provides a way to represent and manipulate tree-based expressions, where each node can have zero or more child nodes. The tree is rooted, meaning it has a single root node from which all other nodes descend.

Type Parameters

• T - The type of value stored in each node. This type must implement Clone, PartialEq, and other traits required by the genetic programming operations.

Fields

• root - An optional TreeNode<T> that serves as the root of the tree. When None, the tree is considered empty.

Examples

use radiate_gp::{Tree, TreeNode, Op, Eval};

// Create a simple tree representing the expression (1 + 2) * 3
let tree = Tree::new(
    TreeNode::new(Op::mul())
        .attach(
            TreeNode::new(Op::add())
                .attach(TreeNode::new(Op::constant(1.0)))
                .attach(TreeNode::new(Op::constant(2.0)))
        )
        .attach(TreeNode::new(Op::constant(3.0)))
);

// Evaluate the tree
let result = tree.eval(&[]); // Evaluates to 9.0
assert_eq!(result, 9.0);

Tree Creation

The struct provides several ways to create trees:

• new() - Creates a tree with a given root node
• with_depth() - Creates a tree of specified depth using nodes from a NodeStore
• default() - Creates an empty tree

Tree Operations

The struct provides methods for tree manipulation and traversal:

• root() - Gets a reference to the root node
• root_mut() - Gets a mutable reference to the root node
• take_root() - Takes ownership of the root node
• size() - Returns the total number of nodes in the tree
• height() - Returns the height of the tree

Tree Traversal

The struct implements the TreeIterator trait, providing three traversal methods:

• iter_pre_order() - Traverses the tree in pre-order (root, then children)
• iter_post_order() - Traverses the tree in post-order (children, then root)
• iter_breadth_first() - Traverses the tree level by level

Tree Building

The struct provides a builder pattern for creating trees of specific depths:

use radiate_gp::{Tree, NodeType, Op};

let store = vec![
    (NodeType::Vertex, vec![Op::add(), Op::sub(), Op::mul()]),
    (NodeType::Leaf, vec![Op::constant(1.0), Op::constant(2.0)]),
];

// Create a tree of depth 3
let tree = Tree::with_depth(3, store);
assert_eq!(tree.height(), 3);

Tree Evaluation

When T implements the Eval trait, the tree can be evaluated with input data:

use radiate_gp::{Tree, TreeNode, Op, Eval};

let tree = Tree::new(
    TreeNode::new(Op::add())
        .attach(TreeNode::new(Op::var(0)))
        .attach(TreeNode::new(Op::constant(2.0)))
);

assert_eq!(tree.eval(&[1.0]), 3.0);
assert_eq!(tree.eval(&[2.0]), 4.0);

Tree Properties

The tree maintains several important properties:

• It is always rooted (has a single root node)
• It is acyclic (no node is its own ancestor)
• Each node can have zero or more children
• The tree’s height is the length of the longest path from root to leaf
• The tree’s size is the total number of nodes

Implementation Details

The struct implements several traits:

• Clone - Allows cloning of the entire tree structure
• PartialEq - Enables equality comparison between trees
• Default - Provides a way to create an empty tree
• Debug - Provides debug formatting for the tree
• AsRef<TreeNode<T>> - Allows treating the tree as a reference to its root node
• AsMut<TreeNode<T>> - Allows treating the tree as a mutable reference to its root node

Genetic Programming

The Tree struct is particularly useful in genetic programming as it can represent:

• Mathematical expressions
• Program syntax trees
• Decision trees
• Other hierarchical structures

Implementations

impl<T: Clone + Default> Tree<T>

pub fn with_depth(depth: usize, nodes: impl Into<NodeStore<T>>) -> Self

Create a tree with the given depth, where each node is a random node from the node store. This obeys the rules of the NodeStore’s NodeType’s arity, and will create a tree that is as balanced as possible.

Note that the root node will try to be a NodeType::Root if it is available in the NodeStore, otherwise it will be a NodeType::Vertex. This allows caller’s to specify what the root node is if desired, otherwise it will be a random vertex node from the NodeStore.

The NodeStore must contain at least one NodeType::Root or one NodeType::Vertex

Arguments

• depth - The depth of the tree.
• nodes - The node store to use for the tree.

Returns

A tree with the given depth, where each node is a random node from the node store.

impl<T> Tree<T>

pub fn new(root: impl Into<TreeNode<T>>) -> Self

pub fn root(&self) -> Option<&TreeNode<T>>

pub fn root_mut(&mut self) -> Option<&mut TreeNode<T>>

pub fn take_root(self) -> Option<TreeNode<T>>

pub fn size(&self) -> usize

pub fn height(&self) -> usize

Trait Implementations

impl<T> AsMut<TreeNode<T>> for Tree<T>

fn as_mut(&mut self) -> &mut TreeNode<T>

Converts this type into a mutable reference of the (usually inferred) input type.

impl<T> AsRef<TreeNode<T>> for Tree<T>

fn as_ref(&self) -> &TreeNode<T>

Converts this type into a shared reference of the (usually inferred) input type.

impl<F> BatchFitnessFunction<Tree<Op<F>>, F> for Regression<F>

where F: OpFloat + Into<Score>,

fn evaluate(&self, inputs: Vec<Tree<Op<F>>>) -> Vec<F>

impl<T: Clone> Clone for Tree<T>

fn clone(&self) -> Tree<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T> Codec<TreeChromosome<T>, Tree<T>> for TreeCodec<T, Tree<T>>

where T: Clone + PartialEq + Default,

fn encode(&self) -> Genotype<TreeChromosome<T>>

fn decode(&self, genotype: &Genotype<TreeChromosome<T>>) -> Tree<T>

impl<T: Debug> Debug for Tree<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Default> Default for Tree<T>

fn default() -> Tree<T>

Returns the “default value” for a type.

impl<T: OpFloat> Eval<Tree<Op<T>>, Option<AccuracyResult>> for Accuracy<'_, T>

fn eval(&self, tree: &Tree<Op<T>>) -> Option<AccuracyResult>

impl<T, V> Eval<[V], V> for Tree<T>

where T: Eval<[V], V>, V: Clone,

Implements the Eval trait for Tree<T> where T is Eval<[V], V>. All this really does is call the eval method on the root node of the Tree. The real work is done in the TreeNode implementation below.

fn eval(&self, input: &[V]) -> V

impl<T, V> EvalInto<[V], [V]> for Tree<T>

where T: Eval<[V], V>, V: Clone,

fn eval_into(&self, input: &[V], buffer: &mut [V])

impl<T, V> EvalMut<[V], Vec<V>> for Tree<T>

where T: Eval<[V], V>, V: Clone + Default,

fn eval_mut(&mut self, input: &[V]) -> Vec<V>

impl<F> FitnessFunction<Tree<Op<F>>, F> for Regression<F>

where F: OpFloat + Into<Score>,

— Trees —

fn evaluate(&self, input: Tree<Op<F>>) -> F

impl<T: Debug> Format for Tree<T>

fn format(&self) -> String

impl<T: Hash> Hash for Tree<T>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<T: PartialEq> PartialEq for Tree<T>

fn eq(&self, other: &Tree<T>) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl<T: PartialEq> StructuralPartialEq for Tree<T>

impl<T> ToDot for Tree<T>

where T: Display,

fn to_dot(&self) -> String

impl<T> TreeIterator<T> for Tree<T>

Implement the TreeIterator trait for Tree

This allows for traversal of the entire tree in pre-order, post-order, and breadth-first order.

fn iter_pre_order(&self) -> PreOrderIterator<'_, T>

fn iter_post_order(&self) -> PostOrderIterator<'_, T>

fn iter_breadth_first(&self) -> TreeBreadthFirstIterator<'_, T>

fn apply<F: Fn(&mut TreeNode<T>)>(&mut self, visit_fn: F)