adt::Tree -- abstract data type
``Tree''
Introductionadt::Tree implements the abstract data type
``Tree''.
Call(s)adt::Tree(tree)
Parameterstree |
- | the tree, given as a special list (see details) |
Returnsan object of the type adt::Tree
Related
Functions
Detailsadt::Tree implements the abstract data type
``Tree''.output::tree (or
the method "print" of a tree). The nodes and leaves of the
tree will be printed by MuPAD
when the tree will be displayed.matchlib::analyze and prog::calltree.The methods of all abstract datatypes must be called especially and will result changing the object itself as sideeffect.
T := adt::Tree([_plus, 3, 4, [_mult, 5, 3], 1]) builds
a tree and assigns it to the variable T.Tree followed by a
number. This name is generated by genident.expose or the method
"print" of the tree itself must be used.All following methods changes the value of
T itself. A new assignment to the variable (in this
example T) is not necessary, in contrast to all other
MuPAD functions and data types.
nops, op, expr,
print, indent, chars are now
available for handling with trees.T::nops()T. Also a subtree is an operand and will be counted as one
operand.T has 4 operands, the
numbers 3, 4, 1 and the subtree
adt::Tree([_mult, 5, 3]).T::op( <n>)T. Also a
subtree is an operand and will be returned as one operand (see
T::nops above).T::op(n) returns the specified operands of the tree.
n can be a number between 0 and
T::nops() (0 gives the root of the tree), a
sequence i..j (to return the ith to
jth operand), or a list to specify operands of subtrees
(exactly as for the kernel function op). T::op() returns all
operands except the 0-th as expression sequence. See
example 2.T::expr()T. The roots of the subtrees will be interpreted as
operations that will applied to the remaining operands (see example 4). In this example the corresponding expression
will be _plus(3, 4, _mult(5, 3), 1) that is 3 + 4 +
5*3 + 1 and will be evaluated to 23. If the roots
are no operations or identifiers, the method expr can be
result to an error.T::print()T and returns the empty
object null().T::indent( <n>)T::indent() returns the indent width of each operand
or subtree. With T::indent(n) the indent width will be set
to the positive integer n.T::chars( <list>)T::chars() returns the characters that will be used to
display a tree, that are | (vertical line), +
(middle branch), - (extension of a branch), `
(last branch) and a space between the branch and the corresponding
operand. With T::chars(list) and list is a
list of five characters the characters can be changed (see example 3). This list will be given as argument to
output::tree.
Example
1Creating a simple tree with only two leaves. To access and display a tree it must be assigned to a variable:
>> T := adt::Tree(["ROOT", "LEFT", "RIGHT"])
Tree1
The tree will only be printed by its name. To display
the tree, the function expose or the method
"print" of the tree must be used:
>> T::print()
ROOT
|
+-- LEFT
|
`-- RIGHT
>> expose(T)
ROOT
|
+-- LEFT
|
`-- RIGHT
The next tree contains two subtrees as leaves:
>> T := adt::Tree(["ROOT", ["LROOT", "LLEFT", "LRIGHT"],
["RROOT", "RLEFT", "RRIGHT"]]):
T::print()
ROOT
|
+-- LROOT
| |
| +-- LLEFT
| |
| `-- LRIGHT
|
`-- RROOT
|
+-- RLEFT
|
`-- RRIGHT
Example
2Get the operands of a tree: Also a subtree can be an operand:
>> T := adt::Tree(["ROOT", ["LROOT", "LLEFT", "LRIGHT"],
"MIDDLE",
["RROOT", "RLEFT", "RRIGHT"]]):
T::op()
Tree4, "MIDDLE", Tree5
Use expose to display subtrees:
>> map(%, expose)
LROOT , "MIDDLE", RROOT
| |
+-- LLEFT +-- RLEFT
| |
`-- LRIGHT `-- RRIGHT
Get all operands including the root:
>> T::op(0..T::nops())
"ROOT", Tree6, "MIDDLE", Tree7
Access to various operands:
>> T::op(0); T::op(2..3); T::op([1, 2])
"ROOT"
"MIDDLE", Tree9
"LRIGHT"
Example
3The default characters are [", "+", ", ``", "
"]:
>> T := adt::Tree(["ROOT", ["LROOT", "LLEFT", "LRIGHT"],
["RROOT", "RLEFT", "RRIGHT"]]):
T::print()
ROOT
|
+-- LROOT
| |
| +-- LLEFT
| |
| `-- LRIGHT
|
`-- RROOT
|
+-- RLEFT
|
`-- RRIGHT
The characters can be changed:
>> T::chars(["|", "|", "_", "|", " "]): T::print()
ROOT
|
|__ LROOT
| |
| |__ LLEFT
| |
| |__ LRIGHT
|
|__ RROOT
|
|__ RLEFT
|
|__ RRIGHT
Example
4A tree visualizes the structure of an expression:
>> T:= adt::Tree([_plus, [_power, [sin, x], 2], [_power, [cos, x], 2]]): T::print()
_plus
|
+-- _power
| |
| +-- sin
| | |
| | `-- x
| |
| `-- 2
|
`-- _power
|
+-- cos
| |
| `-- x
|
`-- 2
A tree can be converted to a MuPAD expression:
>> T::expr(), simplify(T::expr())
2 2
cos(x) + sin(x) , 1