Class TreeNode<T>
- Type Parameters:
T
- the type of data stored in each node
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 Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionvoid
Adds a new child node to this node.void
addChildren
(Collection<TreeNode<T>> childrenNodes) Adds multiple child nodes to this node.boolean
getChild
(int childIndex) Returns the child node at the specified index.Returns the list of direct children of this node.getData()
Returns the data stored in this node.int
getDepth()
Returns the maximum depth of the subtree rooted at this node.int
getSize()
Returns the total number of nodes in the subtree rooted at this node.int
hashCode()
static <U> TreeNode
<U> of
(U data, Collection<TreeNode<U>> children) Creates a new tree node with the specified data and children.void
Replaces the child node at the specified index with a new node.toString()
-
Field Details
-
data
-
children
-
-
Constructor Details
-
TreeNode
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
Returns the data stored in this node.- Returns:
- the data payload of this node
-
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
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 negativeIndexOutOfBoundsException
- if childIndex is >= number of children
-
setChild
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 negativeIndexOutOfBoundsException
- if childIndex is >= number of children
-
addChild
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
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() -
equals
-
toString
-
of
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 nodechildren
- 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
-