public interface Tree<V,T extends Tree<V,T>> extends Iterable<T>
TreeNode
class.TreeNode
Modifier and Type | Interface and Description |
---|---|
static class |
Tree.Path
This class represents the path to child within a given tree.
|
Modifier and Type | Method and Description |
---|---|
default Iterator<T> |
breadthFirstIterator()
Return an iterator that traverses the subtree rooted at
this
node in breadth-first order. |
default Stream<T> |
breadthFirstStream()
Return a stream that traverses the subtree rooted at
this node in
breadth-first order. |
default Optional<T> |
childAfter(Tree<?,?> child)
Return the child which comes immediately after
this node. |
T |
childAt(int index)
Return the child node with the given index.
|
default Optional<T> |
childAtPath(int... path)
Return the child node at the given
path . |
default Optional<T> |
childAtPath(Tree.Path path)
Return the child node at the given
path . |
default Optional<T> |
childBefore(Tree<?,?> child)
Return the child which comes immediately before
this node. |
int |
childCount()
Return the number of children this tree node consists of.
|
default Iterator<T> |
childIterator()
Return an iterator of the children of this
Tree node. |
default Tree.Path |
childPath()
Return the path of
this child node from the root node. |
default Stream<T> |
childStream()
Return a forward-order stream of this node's children.
|
default int |
depth()
Returns the depth of the tree rooted at this node.
|
default Iterator<T> |
depthFirstIterator()
Return an iterator that traverses the subtree rooted at
this node
in depth-first order. |
default Stream<T> |
depthFirstStream()
Return a stream that traverses the subtree rooted at
this node in
depth-first. |
static boolean |
equals(Tree<?,?> a,
Tree<?,?> b)
Checks if the two given trees has the same structure with the same values.
|
default Optional<T> |
firstChild()
Return the first child of
this node, or Optional.empty()
if this node has no children. |
default T |
firstLeaf()
Return the first leaf that is a descendant of
this node; either
this node or its first child's first leaf. |
Optional<T> |
getParent()
Return the parent node of this tree node.
|
default ISeq<T> |
getPath()
Deprecated.
Use
pathElements() instead |
default T |
getRoot()
Returns the root of the tree that contains this node.
|
V |
getValue()
Return the value of the current
Tree node. |
static int |
hashCode(Tree<?,?> tree)
Calculates the hash code of the given tree.
|
default boolean |
identical(Tree<?,?> other)
Tests whether
this node is the same as the other node. |
default int |
indexOf(Tree<?,?> child)
Returns the index of the specified child in this node's child array, or
-1 if this node doesn't contain the given child . |
default boolean |
isAncestor(Tree<?,?> node)
Return
true if the given node is an ancestor of
this node. |
default boolean |
isChild(Tree<?,?> node)
Return
true if the given node is a child of this
node. |
default boolean |
isDescendant(Tree<?,?> node)
Return
true if the given node is a descendant of
this node. |
default boolean |
isLeaf()
Return
true if this node has no children. |
default boolean |
isRelated(Tree<?,?> node)
Returns true if and only if the given
node is in the same tree as
this node. |
default boolean |
isRoot()
Returns
true if this node is the root of the tree. |
default boolean |
isSibling(Tree<?,?> node)
Test if the given
node is a sibling of this node. |
default Iterator<T> |
iterator()
Return an iterator that traverses the subtree rooted at
this . |
default Optional<T> |
lastChild()
Return the last child of
this node, or Optional.empty()
if this node has no children. |
default T |
lastLeaf()
Return the last leaf that is a descendant of this node; either
this node or its last child's last leaf. |
default int |
leafCount()
Returns the total number of leaves that are descendants of this node.
|
default int |
level()
Returns the number of levels above this node.
|
default Optional<T> |
nextLeaf()
Returns the leaf after
this node or Optional.empty() if
this node is the last leaf in the tree. |
default Optional<T> |
nextNode()
Return the node that follows
this node in a pre-order traversal
of this tree node. |
default Optional<T> |
nextSibling()
Return the next sibling of
this node in the parent's children
array, or null if this node has no parent or it is the
last child of the paren. |
default Tree.Path |
path()
Return the
Tree.Path of this tree, such that |
default ISeq<T> |
pathElements()
Returns the path from the root, to get to this node.
|
default Iterator<T> |
pathFromAncestorIterator(Tree<?,?> ancestor)
Return an iterator that follows the path from
ancestor to
this node. |
default Iterator<T> |
postorderIterator()
Return an iterator that traverses the subtree rooted at
this
node in post-order. |
default Stream<T> |
postorderStream()
Return a stream that traverses the subtree rooted at
this node in
post-order. |
default Iterator<T> |
preorderIterator()
Return an iterator that traverses the subtree rooted at
this node
in pre-order. |
default Stream<T> |
preorderStream()
Return a stream that traverses the subtree rooted at
this node
in pre-order. |
default Optional<T> |
previousLeaf()
Return the leaf before
this node or null if this
node is the first leaf in the tree. |
default Optional<T> |
previousNode()
Return the node that precedes this node in a pre-order traversal of
this tree node. |
default Optional<T> |
previousSibling()
Return the previous sibling of
this node in the parent's children
list, or Optional.empty() if this node has no parent or is the
parent's first child. |
default Optional<T> |
sharedAncestor(Tree<?,?> node)
Returns the nearest common ancestor to this node and the given
node . |
default int |
siblingCount()
Return the number of siblings of
this node. |
default int |
size()
Return the number of nodes of
this node (sub-tree). |
default Stream<T> |
stream()
Return a stream that traverses the subtree rooted at
this node in
breadth-first order. |
default String |
toParenthesesString()
Return a compact string representation of the given tree.
|
default String |
toParenthesesString(Function<? super V,String> mapper)
Return a compact string representation of the given tree.
|
static String |
toString(Tree<?,?> tree)
Return a string representation of the given tree, like the following
example.
|
forEach, spliterator
V getValue()
Tree
node. The value may be
null
.Tree
nodeOptional<T> getParent()
Optional.empty()
if this node is the
root of the treeT childAt(int index)
index
- the child indexIndexOutOfBoundsException
- if the index
is out of
bounds ([0, childCount())
)int childCount()
default Iterator<T> childIterator()
Tree
node.Tree
node.default Stream<T> childStream()
this
nodedefault boolean isRoot()
true
if this node is the root of the tree.true
if this node is the root of its tree, false
otherwisedefault int depth()
this
node to a leaf. If
this
node has no children, 0 is returned. This operation is much
more expensive than level()
because it must effectively traverse
the entire tree rooted at this
node.default int level()
this
node. If this
node
is the root, returns 0.default int indexOf(Tree<?,?> child)
-1
if this
node doesn't contain the given child
.
This method performs a linear search and is O(n) where n
is the
number of children.child
- the TreeNode to search for among this node's children-1
if the node could not be foundNullPointerException
- if the given child
is null
default int size()
this
node (sub-tree).this
node (sub-tree)default Optional<T> childAtPath(Tree.Path path)
path
. A path consists of the
child index at a give level, starting with level 1. (The root note has
level zero.) tree.childAtPath(Path.of(2))
will return the third
child node of this
node, if it exists and
tree.childAtPath(Path.of(2, 0))
will return the first child of
the third child of this node
.path
- the child pathpath
NullPointerException
- if the given path
array is
null
childAtPath(int...)
default Optional<T> childAtPath(int... path)
path
. A path consists of the
child index at a give level, starting with level 1. (The root note has
level zero.) tree.childAtPath(2)
will return the third child node
of this
node, if it exists and tree.childAtPath(2, 0)
will
return the first child of the third child of this node
.path
- the child pathpath
NullPointerException
- if the given path
array is
null
IllegalArgumentException
- if one of the path elements is smaller
than zerochildAtPath(Path)
default boolean isAncestor(Tree<?,?> node)
true
if the given node
is an ancestor of
this
node. This operation is at worst O(h)
where h
is the distance from the root to this
node.node
- the node to testtrue
if the given node
is an ancestor of
this
node, false
otherwiseNullPointerException
- if the given node
is null
default boolean isDescendant(Tree<?,?> node)
true
if the given node
is a descendant of
this
node. If the given node
is null
,
false
is returned. This operation is at worst O(h)
where
h
is the distance from the root to this
node.node
- the node to test as descendant of this nodetrue
if this node is an ancestor of the given node
NullPointerException
- if the given node
is null
default Optional<T> sharedAncestor(Tree<?,?> node)
node
.
A node is considered an ancestor of itself.node
- node
to find common ancestor withnode
,
or Optional.empty()
if no common ancestor exists.NullPointerException
- if the given node
is null
default boolean isRelated(Tree<?,?> node)
node
is in the same tree as
this
node.node
- the other node to checknode
is in the same tree as this
node, false
otherwise.NullPointerException
- if the given node
is null
@Deprecated default ISeq<T> getPath()
pathElements()
insteaddefault ISeq<T> pathElements()
default Tree.Path path()
Tree.Path
of this
tree, such that
final Tree<Integer, ?> tree = ...;
final Tree.Path path = tree.path();
assert tree == tree.getRoot()
.childAtPath(path)
.orElse(null);
this
node.default T getRoot()
default boolean isChild(Tree<?,?> node)
true
if the given node
is a child of this
node.node
- the other node to checktrue
if node
is a child, false
otherwiseNullPointerException
- if the given node
is null
default Optional<T> firstChild()
this
node, or Optional.empty()
if this
node has no children.default Optional<T> lastChild()
this
node, or Optional.empty()
if this
node has no children.default Optional<T> childAfter(Tree<?,?> child)
this
node. This
method performs a linear search of this node's children for child
and is O(n)
where n is the number of children.child
- the child nodechild
,
or Optional.empty()
if the given node
is the
first node.NullPointerException
- if the given child
is null
default Optional<T> childBefore(Tree<?,?> child)
this
node. This
method performs a linear search of this node's children for child
and is O(n)
where n is the number of children.child
- the child nodechild
,
or null
if the given node
is the first node.NullPointerException
- if the given child
is null
default Optional<T> nextNode()
this
node in a pre-order traversal
of this
tree node. Return Optional.empty()
if this node
is the last node of the traversal. This is an inefficient way to traverse
the entire tree use an iterator instead.Optional.empty()
if this node is lastpreorderIterator()
default Optional<T> previousNode()
this
tree node. Returns Optional.empty()
if this node is
the first node of the traversal, the root of the tree. This is an
inefficient way to traverse the entire tree; use an iterator instead.Optional.empty()
if this node is the firstpreorderIterator()
default boolean isSibling(Tree<?,?> node)
node
is a sibling of this
node.node
- node to test as sibling of this nodetrue
if the node
is a sibling of this
nodeNullPointerException
- if the given node
is null
default int siblingCount()
this
node. A node is its own
sibling (if it has no parent or no siblings, this method returns
1
).this
nodedefault Optional<T> nextSibling()
this
node in the parent's children
array, or null
if this
node has no parent or it is the
last child of the paren. This method performs a linear search that is
O(n)
where n is the number of children; to traverse the entire
array, use the iterator of the parent instead.this
node that immediately follows
this
nodechildStream()
default Optional<T> previousSibling()
this
node in the parent's children
list, or Optional.empty()
if this node has no parent or is the
parent's first child. This method performs a linear search that is O(n)
where n is the number of children.this
node that immediately precedes this
nodedefault boolean isLeaf()
true
if this
node has no children.true
if this
node has no children, false
otherwisedefault T firstLeaf()
this
node; either
this node or its first child's first leaf. this
node is returned
if it is a leaf.isLeaf()
,
isDescendant(io.jenetics.ext.util.Tree<?, ?>)
default T lastLeaf()
this
node or its last child's last leaf. Returns this
node if it is a leaf.isLeaf()
,
isDescendant(io.jenetics.ext.util.Tree<?, ?>)
default Optional<T> nextLeaf()
this
node or Optional.empty()
if
this node is the last leaf in the tree.
In order to determine the next node, this method first performs a linear search in the parent's child-list in order to find the current node.
That implementation makes the operation suitable for short traversals
from a known position. But to traverse all of the leaves in the tree, you
should use depthFirstIterator()
to iterator the nodes in the
tree and use isLeaf()
on each node to determine which are leaves.
depthFirstIterator()
,
isLeaf()
default Optional<T> previousLeaf()
this
node or null
if this
node is the first leaf in the tree.
In order to determine the previous node, this method first performs a linear search in the parent's child-list in order to find the current node.
That implementation makes the operation suitable for short traversals
from a known position. But to traverse all of the leaves in the tree, you
should use depthFirstIterator()
to iterate the nodes in the tree
and use isLeaf()
on each node to determine which are leaves.
this
nodedepthFirstIterator()
,
isLeaf()
default int leafCount()
1
. This method is O(n)
,
where n is the number of descendants of this
node.isLeaf()
default Iterator<T> breadthFirstIterator()
this
node in breadth-first order. The first node returned by the iterator is
this
node.
Modifying the tree by inserting, removing, or moving a node invalidates any iterator created before the modification.
depthFirstIterator()
default Iterator<T> iterator()
this
.
The first node returned by the iterator is this
node.
Modifying the tree by inserting, removing, or moving a node invalidates any iterator created before the modification.
default Stream<T> breadthFirstStream()
this
node in
breadth-first order. The first node returned by the stream is
this
node.depthFirstIterator()
,
stream()
default Stream<T> stream()
this
node in
breadth-first order. The first node returned by the stream is
this
node.breadthFirstStream()
default Iterator<T> preorderIterator()
this
node
in pre-order. The first node returned by the iterator is this
node.
Modifying the tree by inserting, removing, or moving a node invalidates any iterator created before the modification.
postorderIterator()
default Stream<T> preorderStream()
this
node
in pre-order. The first node returned by the stream is this
node.
Modifying the tree by inserting, removing, or moving a node invalidates any iterator created before the modification.
preorderIterator()
default Iterator<T> postorderIterator()
this
node in post-order. The first node returned by the iterator is the
leftmost leaf. This is the same as a depth-first traversal.depthFirstIterator()
,
preorderIterator()
default Stream<T> postorderStream()
this
node in
post-order. The first node returned by the iterator is the leftmost leaf.
This is the same as a depth-first traversal.depthFirstIterator()
,
preorderIterator()
default Iterator<T> depthFirstIterator()
this
node
in depth-first order. The first node returned by the iterator is the
leftmost leaf. This is the same as a postorder traversal.
Modifying the tree by inserting, removing, or moving a node invalidates any iterator created before the modification.
breadthFirstIterator()
,
postorderIterator()
default Stream<T> depthFirstStream()
this
node in
depth-first. The first node returned by the iterator is the leftmost leaf.
This is the same as a post-order traversal.depthFirstIterator()
,
preorderIterator()
default Iterator<T> pathFromAncestorIterator(Tree<?,?> ancestor)
ancestor
to
this
node. The iterator return ancestor
as first element,
The creation of the iterator is O(m), where m is the number of nodes
between this
node and the ancestor
, inclusive.
Modifying the tree by inserting, removing, or moving a node invalidates any iterator created before the modification.
ancestor
- the ancestor nodethis
node to this oneIllegalArgumentException
- if the ancestor
is not an
ancestor of this nodeNullPointerException
- if the given ancestor
is null
isAncestor(io.jenetics.ext.util.Tree<?, ?>)
,
isDescendant(io.jenetics.ext.util.Tree<?, ?>)
default Tree.Path childPath()
this
child node from the root node. You will
get this
node, if you call childAtPath(Path)
on the
root node of this
node.
final Tree<?, ?> node = ...;
final Tree<?, ?> root = node.getRoot();
final int[] path = node.childPath();
assert node == root.childAtPath(path);
this
child node from the root node.childAtPath(Path)
default boolean identical(Tree<?,?> other)
this
node is the same as the other
node.
The default implementation returns the object identity,
this == other
, of the two objects, but other implementations may
use different criteria for checking the identity.other
- the other
nodetrue
if the other
node is the same as this
node.default String toParenthesesString(Function<? super V,String> mapper)
mul ├── div │ ├── cos │ │ └── 1.0 │ └── cos │ └── π └── sin └── mul ├── 1.0 └── zis printed as
mul(div(cos(1.0), cos(π)), sin(mul(1.0, z)))
mapper
- the mapper
which converts the tree value to a stringtoParenthesesString()
,
TreeFormatter.PARENTHESES
default String toParenthesesString()
mul ├── div │ ├── cos │ │ └── 1.0 │ └── cos │ └── π └── sin └── mul ├── 1.0 └── zis printed as
mul(div(cos(1.0), cos(π)), sin(mul(1.0, z)))
NullPointerException
- if the mapper
is null
toParenthesesString(Function)
,
TreeFormatter.PARENTHESES
static int hashCode(Tree<?,?> tree)
tree
- the tree where the hash is calculated fromNullPointerException
- if the given tree
is null
static boolean equals(Tree<?,?> a, Tree<?,?> b)
a
- the first treeb
- the second treetrue
if the two given trees are structurally equals,
false
otherwisestatic String toString(Tree<?,?> tree)
mul(div(cos(1.0), cos(π)), sin(mul(1.0, z)))This method is intended to be used when override the
Object.toString()
method.tree
- the input tree© 2007-2019 Franz Wilhelmstötter (2019-11-18 20:30)