Package components.tree
Interface Tree<T>
- Type Parameters:
T
- type ofTree
labels
- All Superinterfaces:
Iterable<T>
,Standard<Tree<T>>
,TreeKernel<T>
- All Known Implementing Classes:
Tree1
,TreeSecondary
TreeKernel
enhanced with secondary methods.- Mathematical Definitions:
HEIGHT( t: tree of T ): integer satisfies if t = empty_tree then HEIGHT(t) = 0 else there exists root: T, children: string of tree of T (t = compose(root, children) and HEIGHT(t) = 1 + MAX_HEIGHT(children)) MAX_HEIGHT( s: string of tree of T ): integer satisfies if s = empty_string then MAX_HEIGHT(s) = 0 else there exists t: tree of T, rest: string of tree of T (s = <t> * rest and MAX_HEIGHT(s) = max(HEIGHT(t), MAX_HEIGHT(rest))
-
Method Summary
Modifier and TypeMethodDescriptionvoid
addSubtree
(int pos, Tree<T> st) Adds the treest
at positionpos
inthis
; the declaration notwithstanding, the dynamic type ofst
must be the same as the dynamic type ofthis
.int
height()
Reports the height ofthis
.int
Returns the number of subtrees of the root ofthis
.removeSubtree
(int pos) Removes and returns the subtree at positionpos
inthis
.replaceRoot
(T x) Replaces the root ofthis
withx
, and returns the old root.root()
Reports the root ofthis
.Methods inherited from interface java.lang.Iterable
forEach, iterator, spliterator
Methods inherited from interface components.standard.Standard
clear, newInstance, transferFrom
Methods inherited from interface components.tree.TreeKernel
assemble, disassemble, newSequenceOfTree, size
-
Method Details
-
root
Reports the root ofthis
.- Returns:
- the root entry of
this
- Aliases:
- reference returned by
root
- Requires:
this /= empty_tree
- Ensures:
there exists children: string of tree of T (this = compose(root, children))
-
replaceRoot
Replaces the root ofthis
withx
, and returns the old root.- Parameters:
x
- the new root- Returns:
- the old root
- Aliases:
- reference
x
- Updates:
this
- Requires:
this /= empty_tree
- Ensures:
there exists children: string of tree of T (#this = compose(replaceRoot, children) and this = compose(x, children))
-
height
int height()Reports the height ofthis
.- Returns:
- the height
- Ensures:
height = HEIGHT(this)
-
addSubtree
Adds the treest
at positionpos
inthis
; the declaration notwithstanding, the dynamic type ofst
must be the same as the dynamic type ofthis
.- Parameters:
pos
- the position at which to addst
st
- theTree
to add- Updates:
this
- Clears:
st
- Requires:
this /= empty_tree and 0 <= pos <= [number of children of this]
- Ensures:
this = [#this with subtree #st inserted at position pos]
-
removeSubtree
Removes and returns the subtree at positionpos
inthis
.- Parameters:
pos
- the position of the subtree to remove- Returns:
- the subtree at position pos in
this
- Updates:
this
- Requires:
this /= empty_tree and 0 <= pos < [number of children of this]
- Ensures:
this = [#this with subtree at position pos removed and returned as result]
-
numberOfSubtrees
int numberOfSubtrees()Returns the number of subtrees of the root ofthis
.- Returns:
- the number of subtrees of the root of
this
- Requires:
this /= empty_tree
- Ensures:
there exists root: T, children: string of tree of T (this = compose(root, children) and numberOfSubtrees = |children|)
-