# What is the formal definition of ordered tree?

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

1. Is a directed graph $$D=$$
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??

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.

• Thanks a lot!!!! May I further ask that does $V(T)$ impose the vertex set of the tree $T$ Feb 22, 2021 at 3:44
• And $x\in rTy$ impose that x is a vertex that in path $rTy$ ?? Feb 22, 2021 at 3:49
• $V(T)$ is just a different notation for referring to the vertex set of $T$ if one have not written $T=(V,E)$. $x \in rTy$ means that $x$ is in the path $rTy$. Feb 22, 2021 at 8:27