After the posts on elementary data structures, we move on to deal with trees. Before going into the details of how to implement data structures of this type, let us delve into the theoretical aspect.

First, let’s look at the classic definition

A (rooted) tree is a pair `T=(N,A)`

consisting of a set `N`

of nodes and a set `A`

of arcs, `A`

being a proper subset of `NxN`

(i.e. of the Cartesian product of `N`

by `N`

), the arcs in fact being pairs of nodes, and the concept of an arc models the relationship.

There is a rather intuitive nomenclature regarding trees.
In a tree every node `v`

(except the root) has only one parent (or father) `u`

`such that `

(u,v)` belongs to `

A` (the set of arcs)

A node may have `1`

or more `v`

children `such that `

(u,v)` belongs to `

A` and their number is called degree

With these definitions we have already established some important concepts.

We will not deal here with all the definitions for root, leaves, inner nodes,ancestors,descendants,depth.

Nodes with the same father are called siblings, trees with leaves all on the same level are called complete trees.

A basic specification of the `Tree`

data type must necessarily include operations such as those below.

- DATA-TYPE
`Tree`

- DATA
`N`

=`set of`

nodes`A`

=`set of`

arcs

- OPERATIONS
- numberOfNodes() -> int
- returns the number of nodes in the
`tree`

- returns the number of nodes in the
- degree(Node
`v`

) ->int- returns the number of children of node
`v`

- returns the number of children of node
- parent(Node
`v`

) -> Node- returns the parent of node
`v`

or`null`

if`v`

is the`root`

- returns the parent of node
- (node,node,…,node) children(Node `vv)
- returns the children of the
`v`

node one after the other

- returns the children of the
- addNode(Node
`u`

,Node`v`

) -> node- inserts a new node
`v`

as a child of`u`

in the tree and returns it, if`v`

is the first node to be inserted in the tree it becomes root and`u`

is ignored

- inserts a new node
- addSubtree(Tree
`t`

,Node`u`

)- inserts the subtree
`t`

into the tree so that the root of`t`

becomes a child of`u`

- inserts the subtree
- removeSubtree(Node v) ->
`Tree`

- detaches and returns the entire subtree rooted in
`v`

, the operation deletes the`v`

node and all its descendants from the tree

- detaches and returns the entire subtree rooted in

- numberOfNodes() -> int

A questo punto passare dalla specifica in pseudocodice ad una in linguaggio Java è immediato.

```
interface Node {
//stuff
}
interface Tree {
int numberOfNodes();
int degree(Node v);
Node parent(Node v);
List<Node> children(Node v);
Node addNode(Node u,Node v);
void addSubTree(Tree a,Node u) ;
Tree removeSubTree(Node v);
}
```

Such a structure which does not carry some information content is in itself of little use, `Node`

should in fact contain as a property e.g. a key, a label. Think for example of a tree structure to represent the family tree of a family.

Using generics would in fact be more interesting to work with classes of this type
`Tree<T>`

and `Node<T>`

.

In the JDK, there are interesting implementations such as `javax.swing.tree.TreeModel`

and `javax.swing.tree.TreeNode`

used in `Swing`

for building GUIs in desktop environments.

There are several possible representations for trees, either based on indexed or linked structures; which one we choose depends on the kind of problems we think we need to solve. If we think the most common or critical operation is to find the children of a node, we’ll use one; if the most critical operation is to navigate the tree by levels, we’ll use one optimised for that.