## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

# 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.

## Discussion

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(  ) &lt; 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>```

Example 4-25. Output

`y - 2 + 4 * (x + 1) + 8 =  = 0`

Obviously, this stylesheet is not a full-fledged MathML-to-C translator. However, Chapter 9 discusses this problem more thoroughly.

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required