ordered tree


A tree is, by definition, a partially ordered setMathworldPlanetmath. An ordered tree is a tree equipped with a linear extensionMathworldPlanetmathPlanetmath. 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. 1.

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

    1. (a)

      the root of T is labeled (1),

    2. (b)

      if a node V of T has been labeled (m1,,mk), and if the children of T are V1,,V, then label each Vi by (m1,,mk,i).

    From this labeling process, we see that the (direct) children of the root have labels (1,1),(1,2),. 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 componentsPlanetmathPlanetmathPlanetmath of their labels are distinct.

  2. 2.

    Next, order the labels of the nodes lexicographically. In other words, given an m-tuple p=(p1,,pm) and an n-tuple q=(q1,,qn), compare them componentwise, starting from the first. There are two cases:

    1. (a)

      either all k components match, where k=min(m,n), or

    2. (b)

      pjqj, but pi=qi for all i<j, where jmin(m,n).

    Then p<q iff m<n in the first case, or pj<qj in the second. This orderingMathworldPlanetmath on the labels induces an ordering on the nodes: for nodes V and V with labels p and p,

    VV  iff  pp.

    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:

a<b<e<f<c<g<h<i<j<k<d.
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