1<?xml version="1.0"?> 2<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"> 3 <xsl:output encoding="utf-8"/> 4 <xsl:template match="node" mode="keep"> 5 <node key="{@key}"> 6 <xsl:if test="left"> 7 <left> 8 <xsl:apply-templates select="left/node" mode="keep"/> 9 </left> 10 </xsl:if> 11 <xsl:if test="right"> 12 <right> 13 <xsl:apply-templates select="right/node" mode="keep"/> 14 </right> 15 </xsl:if> 16 </node> 17 </xsl:template> 18 19 <xsl:template match="*"/> 20 21 <xsl:template match="node"> 22 <xsl:choose> 23 <xsl:when test="(left and not(right)) or (left/node/@key < right/node/@key)"> 24 <node key="{left/node/@key}"> 25 <left> 26 <xsl:apply-templates select="left/node"/> 27 </left> 28 <xsl:if test="right"> 29 <right> 30 <xsl:apply-templates select="right/node" mode="keep"/> 31 </right> 32 </xsl:if> 33 </node> 34 </xsl:when> 35 <xsl:when test="right"> 36 <node key="{right/node/@key}"> 37 <xsl:if test="left"> 38 <left> 39 <xsl:apply-templates select="left/node" mode="keep"/> 40 </left> 41 </xsl:if> 42 <right> 43 <xsl:apply-templates select="right/node"/> 44 </right> 45 </node> 46 </xsl:when> 47 <xsl:otherwise> 48 </xsl:otherwise> 49 </xsl:choose> 50 </xsl:template> 51 52</xsl:stylesheet>