## `adt::Tree` -- abstract data type ``Tree''

#### Introduction

`adt::Tree` implements the abstract data type ``Tree''.

#### Call(s)

`adt::Tree(tree)`

#### Parameters

`tree` | - | the tree, given as a special list (see details)

#### Returns

an object of the type `adt::Tree`

#### Related Functions

`output::tree`

#### Details

- `adt::Tree` implements the abstract data type ``Tree''.
- A tree must be given as a special MuPAD list:
- The first object of the list is the root of the tree. All further objects are leaves or subtrees of the tree. A subtree is again a special list (as described), and any other MuPAD object will be interpreted as leaf of the tree (see example 1).
- A tree can be used to display data in tree structure using the function `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.
- A tree can also be used as datatype to keep and handle any MuPAD data. Examples for using trees are, e.g., the library functions `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`.
- Every tree will be displayed as `Tree` followed by a number. This name is generated by `genident`.
- To display the content of a tree, the function `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.

- The methods `nops`, `op`, `expr`, `print`, `indent`, `chars` are now available for handling with trees.

- #### Method T::nops: number of operands

  - `T::nops()`
  - - This method returns the number of operands of the tree `T`. Also a subtree is an operand and will be counted as one operand.
    - In this example `T` has `4` operands, the numbers `3`, `4`, `1` and the subtree `adt::Tree([_mult, 5, 3])`.

  #### Method T::op: operands of a tree

  - `T::op( <n>)`
  - - This method returns the operands of the tree `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.

  #### Method T::expr: convert a tree to an expression

  - `T::expr()`
  - - This method returns a MuPAD expression derivated of the tree `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.

  #### Method T::print: display a tree

  - `T::print()`
  - - This method displays the tree `T` and returns the empty object `null()`.

  #### Method T::indent: indent width of each operand

  - `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`.

  #### Method T::chars: indent width of each operand

  - `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 1

  Creating 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 2

  Get 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 3

  The 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 4

  A 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

  #### Changes

  - new function

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000