Tree

A tree is a special case of a directed graph. Additionally compared to a directed graph it holds for a tree:

1. There is one vertex without a predecessor, and this vertex is called the root. From the root there is a path to every other vertex in the graph.

2. Each vertex different from the tree has exactly one predecessor, which is also called the father. The vertex following a father is called it's son. Because a father in a tree can have more than one son the set of sons is also called the children. For a path $\pi$ in the tree with $\pi = v, ..., v'$ one calls the v the ancestor of v' and the v' the descendant of v. Because v = v' is possible one has to say that every vertex is his own ancestor and his own descendant. A vertex without a son is called a leaf and all vertices without the leaves of a tree are called the inner vertices. A path $\pi$ which is no cycle and with no leave is infinite.

3. The children of each vertex are ordered from left to right following some ordering relation.