XSLT Cookbook

Performing an In-Order Traversal

Problem

You have an XML document or fragment that represents an expression to be processed in-order.

Solution

An in-order traversal is most applicable to a binary tree. The general form of the algorithm in this case follows:

<xsl:template match="node(  )">
     <!--Process left subtree -->
     <xsl:apply-templates select="*[1]"/>
     
     <!-- Do something with current node -->
     
     <!--Process right subtree --> 
     <xsl:apply-templates select="*[2]"/>
</xsl:template>

However, in-order traversal can extend to n-ary trees with the following algorithm:

<xsl:template match="node(  )">
     <xsl:variable name="current-node" select="."/>
     <!--Process left subtree -->
     <xsl:apply-templates select="*[1]"/>
     
     <!-- Do something with $current-node -->
   
     <!-- Apply recursively to middle children     
     <xsl:for-each select="*[position(  ) > 1 and position(  ) &lt; last(  )">
          
          <!-- Process "left" subtree --> 
          <xsl:apply-templates select="."/>
   
          <!--Do something with $current-node -->
   
     </xsl:for-each>
   
     <!--Process right subtree -->
     <xsl:apply-templates select="*[last(  )]"/>
   
</xsl:template>

The rational behind this algorithm can be better understood by considering Figure 4-1, which shows the binary equivalent of an n-ary tree. The generalized n-ary in-order traversal produces the same result as the binary in-order traversal on the binary equivalent tree.

Figure 4-1. N-ary to binary tree equivalent

Discussion

This form of ...