What is the formal definition of ordered tree?

Question

Hi I understand that for rooted tree, the definition is as follow:

1. Is a directed graph $D=<V,E>$
2. $\exists v\in V\rightarrow \deg^-(v)=0$ which indicate the in-degree of $v$ is $0$
3. $\forall v'\in(V/\{v\})\rightarrow\deg^-(v')=1$ which indicate the in-degree of nodes other than $v$ is $1$

I understand that an ordered tree is based on a rooted tree, which all sub-nodes of any node have an order. But I cannot find a formal mathematical expression for this.

May I ask how should I define it with formal mathematical expression??

Answer 1

Let $T$ be such a tree and let us write $xTy$ for the unique path in $T$ between vertices $x$ and $y$. Let us denote $r$ as the root vertex in $T$.

We can impose a partial ordering on $V(T)$ by letting $x \leq y$ if $x \in rTy,\ \forall x,y \in V(T)$. In such a structure every leaf node is a maximal element of $T$.

Here is an example, generated via sage:

However, we can endow our tree structure with different orderings, e.g. horizontal orderings. Have a look on this exemplary collection of different partial orderings for rooted trees on wikipedia.