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( ) < 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.
This form of traversal has a much narrower range of applicability then other traversal examples in this chapter. One notable application, shown in Example 4-23 and Example 4-24, is as a component of a stylesheet that converts MathML markup to C or Java-style infix expressions. Example 4-25 shows the output.
Example 4-23. Input MathML fragment
<apply> <eq/> <apply> <plus/> <apply> <minus/> <ci>y</ci> <cn>2</cn> </apply> <apply> <times/> <cn>4</cn> <apply> <plus/> <ci>x</ci> <cn>1</cn> </apply> </apply> <cn>8</cn> </apply> <cn>0</cn> </apply>
Example 4-24. In-order traversal of MathML fragment to produce a C expression
<?xml version="1.0" encoding="UTF-8"?> <xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:C="http://www.ora.com/XSLTCookbook/nampespaces/C"> <xsl:output method="text"/> <xsl:strip-space elements="*"/> <!-- Table to convert from MathML operation names to C operators --> <C:operator mathML="plus" c="+" precedence="2"/> <C:operator mathML="minus" c="-" precedence="2"/> <C:operator mathML="times" c="*" precedence="3"/> <C:operator mathML="div" c="/" precedence="3"/> <C:operator mathML="mod" c="%" precedence="3"/> <C:operator mathML="eq" c="= =" precedence="1"/> <!-- load operation conversion table into a variable --> <xsl:variable name="ops" select="document('')/*/C:operator"/> <xsl:template match="apply"> <xsl:param name="parent-precedence" select="0"/> <!-- Map mathML operation to operator name and precedence --> <xsl:variable name="mathML-opName" select="local-name(*[1])"/> <xsl:variable name="c-opName" select="$ops[@mathML=$mathML-opName]/@c"/> <xsl:variable name="c-opPrecedence" select="$ops[@mathML=$mathML-opName]/@precedence"/> <!-- Parenthises required if if the precedence of the containing expression is greater than current sub-expression --> <xsl:if test="$parent-precedence > $c-opPrecedence"> <xsl:text>(</xsl:text> </xsl:if> <!-- Recursively process the left sub-tree which is at position 2 in MathML apply element--> <xsl:apply-templates select="*[2]"> <xsl:with-param name="parent-precedence" select="$c-opPrecedence"/> </xsl:apply-templates> <!-- Process the current node (i.e. the operator at position 1 in MathML apply element --> <xsl:value-of select="concat(' ',$c-opName,' ')"/> <!-- Recursively process middle children --> <xsl:for-each select="*[position( )>2 and position( ) < last( )]"> <xsl:apply-templates select="."> <xsl:with-param name="parent-precedence" select="$c-opPrecedence"/> </xsl:apply-templates> <xsl:value-of select="concat(' ',$c-opName,' ')"/> </xsl:for-each> <!-- Recursively process right subtree--> <xsl:apply-templates select="*[last( )]"> <xsl:with-param name="parent-precedence" select="$c-opPrecedence"/> </xsl:apply-templates> <!-- Parenthises required if if the precedence of the containing expression is greater than current sub-expression --> <xsl:if test="$parent-precedence > $c-opPrecedence"> <xsl:text>)</xsl:text> </xsl:if> </xsl:template> <xsl:template match="ci|cn"> <xsl:value-of select="."/> </xsl:template> </xsl:stylesheet>
Obviously, this stylesheet is not a full-fledged MathML-to-C translator. However, Chapter 9 discusses this problem more thoroughly.