ordered tree

A tree is, by definition, a partially ordered set. An ordered tree is a tree equipped with a linear extension. In other words, its a linear order on the nodes of the tree that obeys the parent-child relationship of the tree. By Zorn’s lemma, every tree can be ordered. When a tree $T$ is finite, the linear extension of the tree can be constructed inductively:

1. First, label the nodes of $T$: each label is an $n$-tuple of positive integers, for some $n$,

   1. the root of $T$ is labeled $(1)$,

   2. if a node $V$ of $T$ has been labeled $(m_1,\mathrm{\dots },m_k)$, and if the children of $T$ are $V_1,\mathrm{\dots },V_{\mathrm{\ell }}$, then label each $V_i$ by $(m_1,\mathrm{\dots },m_k,i)$.

   From this labeling process, we see that the (direct) children of the root have labels $(1,1),(1,2),\mathrm{\dots }$. In general, if a node is of level $k$, its label is a $k$-tuple starting with $1$. It is easy to see that each label corresponds to a unique node of $T$: for if two distinct nodes are of different level, their labels are clearly different. However, if they are of the same level, then the last components of their labels are distinct.

2. Next, order the labels of the nodes lexicographically. In other words, given an $m$-tuple $p=(p_1,\mathrm{\dots },p_m)$ and an $n$-tuple $q=(q_1,\mathrm{\dots },q_n)$, compare them componentwise, starting from the first. There are two cases:

   1. either all $k$ components match, where $k=\min (m,n)$, or

   2. $p_j\ne q_j$, but $p_i=q_i$ for all , where $j\le \min (m,n)$.

   Then iff in the first case, or in the second. This ordering on the labels induces an ordering on the nodes: for nodes $V$ and $V^{\prime }$ with labels $p$ and $p^{\prime }$,

   $$V\le V^{\prime }\mathit{\hspace{1em}\hspace{1em}}\text{iff}\mathit{\hspace{1em}\hspace{1em}}p\le p^{\prime }.$$

   This ordering on the nodes is linear, and extends the partial ordering on $T$.

For example, below are two diagrams of the same tree. The one on the right is labeled by the method above:

By ordering the labels, we get the corresponding ordering of the nodes:

Title	ordered tree
Canonical name	OrderedTree
Date of creation	2013-03-22 19:00:11
Last modified on	2013-03-22 19:00:11
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	5
Author	CWoo (3771)
Entry type	Definition
Classification	msc 03E05