Package net.bmahe.genetics4j.core.chromosomes

Class TreeNode<T>

java.lang.Object
net.bmahe.genetics4j.core.chromosomes.TreeNode<T>
Type Parameters:
T - the type of data stored in each node
public class TreeNode<T> extends Object
Represents a node in a tree structure used for genetic programming and tree-based chromosomes.

TreeNode provides a flexible, generic tree data structure that forms the foundation for tree-based genetic programming operations. Each node contains data of a specified type and can have zero or more child nodes, enabling the representation of complex hierarchical structures such as mathematical expressions, decision trees, or program syntax trees.

Key features include:

  • Generic data storage: Can hold any type of data (functions, terminals, values)
  • Dynamic structure: Supports adding, removing, and modifying children
  • Tree metrics: Provides size and depth calculations for analysis
  • Hierarchical operations: Enables tree traversal and manipulation

Common uses in genetic programming:

  • Expression trees: Mathematical or logical expressions with operators and operands
  • Program trees: Structured representation of executable code or algorithms
  • Decision trees: Conditional logic structures for classification or control
  • Grammar trees: Parse trees representing valid grammatical constructs

Tree structure characteristics:

  • Mutable structure: Children can be added, removed, or replaced during evolution
  • Type safety: Generic parameterization ensures consistent data types
  • Recursive operations: Size and depth calculations traverse the entire subtree
  • Equality semantics: Two trees are equal if their structure and data match

Example usage in genetic programming: 


 // Creating a simple mathematical expression: (x + 2) * 3
 TreeNode<String> multiply = new TreeNode<>("*");
 TreeNode<String> add = new TreeNode<>("+");
 TreeNode<String> x = new TreeNode<>("x");
 TreeNode<String> two = new TreeNode<>("2");
 TreeNode<String> three = new TreeNode<>("3");
 
 add.addChild(x);
 add.addChild(two);
 multiply.addChild(add);
 multiply.addChild(three);
 
 // Tree metrics
 int treeSize = multiply.getSize();   // Total nodes in tree
 int treeDepth = multiply.getDepth(); // Maximum depth from root
 
 // Factory method for creating nodes with children
 TreeNode<String> expression = TreeNode.of("*", List.of(
     TreeNode.of("+", List.of(
         new TreeNode<>("x"),
         new TreeNode<>("2")
     )),
     new TreeNode<>("3")
 ));

Integration with genetic operations:

  • Crossover: Subtree exchange between parent trees
  • Mutation: Replacement or modification of individual nodes or subtrees
  • Size constraints: Enforcement of maximum tree size or depth limits
  • Evaluation: Tree traversal for fitness computation

Performance considerations:

  • Memory usage: Each node maintains a list of children references
  • Tree traversal: Size and depth calculations have O(n) complexity
  • Structural sharing: Nodes can be shared between trees with care
  • Deep trees: Very deep trees may cause stack overflow in recursive operations
See Also:

  • Field Details

  • Constructor Details

    • TreeNode

      public TreeNode(T _data)
      Constructs a new tree node with the specified data and no children.

      Creates a leaf node that can later have children added to it. The data provided becomes the payload for this node and cannot be changed after construction.

      Parameters:
      _data - the data to store in this node
      Throws:
      IllegalArgumentException - if data is null

  • Method Details

    • getData

      public T getData()
      Returns the data stored in this node.
      Returns:
      the data payload of this node

    • getChildren

      public List<TreeNode<T>> getChildren()
      Returns the list of direct children of this node.

      The returned list is the actual internal list used by this node. Modifications to the returned list will affect this node's structure.

      Returns:
      the mutable list of child nodes

    • getChild

      public TreeNode<T> getChild(int childIndex)
      Returns the child node at the specified index.
      Parameters:
      childIndex - the index of the child to retrieve (0-based)
      Returns:
      the child node at the specified index
      Throws:
      IllegalArgumentException - if childIndex is negative
      IndexOutOfBoundsException - if childIndex is >= number of children

    • setChild

      public void setChild(int childIndex, TreeNode<T> childData)
      Replaces the child node at the specified index with a new node.

      This operation modifies the tree structure by replacing an existing child with a new subtree rooted at the provided node.

      Parameters:
      childIndex - the index of the child to replace (0-based)
      childData - the new child node to set at the specified index
      Throws:
      IllegalArgumentException - if childIndex is negative
      IndexOutOfBoundsException - if childIndex is >= number of children

    • addChild

      public void addChild(TreeNode<T> childData)
      Adds a new child node to this node.

      The new child is appended to the end of the children list. This operation increases the arity of this node by one.

      Parameters:
      childData - the child node to add
      Throws:
      IllegalArgumentException - if childData is null

    • addChildren

      public void addChildren(Collection<TreeNode<T>> childrenNodes)
      Adds multiple child nodes to this node.

      All nodes in the provided collection are appended to the children list in the order they appear in the collection.

      Parameters:
      childrenNodes - the collection of child nodes to add
      Throws:
      IllegalArgumentException - if childrenNodes is null or empty

    • getSize

      public int getSize()
      Returns the total number of nodes in the subtree rooted at this node.

      This method recursively counts all nodes in the subtree, including this node and all its descendants. The size is useful for analyzing tree complexity and implementing size-based genetic operations.

      Returns:
      the total number of nodes in this subtree (always >= 1)

    • getDepth

      public int getDepth()
      Returns the maximum depth of the subtree rooted at this node.

      The depth is defined as the length of the longest path from this node to any leaf node in the subtree. A leaf node has depth 1.

      Returns:
      the maximum depth of this subtree (always >= 1)

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • equals

      public boolean equals(Object obj)
      Overrides:
      equals in class Object

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • of

      public static <U> TreeNode<U> of(U data, Collection<TreeNode<U>> children)
      Creates a new tree node with the specified data and children.

      This factory method provides a convenient way to construct trees with a specific structure in a single operation. All provided children are added to the new node.

      Type Parameters:
      U - the type of data stored in the nodes
      Parameters:
      data - the data to store in the root node
      children - the collection of child nodes to add
      Returns:
      a new tree node with the specified data and children
      Throws:
      IllegalArgumentException - if data is null, children is null, or children is empty