Árvores Binárias em XML


Written on January 25, 2009 – 5:15 am | by André Gomes

Na sequência da disciplina de Processamento Estruturado de Documentos do meu mestrado resolvi fazer aqui uma pequena brincadeira em que tentei construir um XML Schema para um tipo de dados que reprenta uma árvore binária.

A maneira mais comum de pensar numa árvore binária será qualquer coisa como:

Uma árvore binária é Vazia ou tem um Nodo e mais duas sub-árvores binárias como filhas desse nodo.

Pois bem, foi mais ou menos assim que construi o meu XML Schema. Criei um elemento de nome arvbin que pode conter ou um elemento vazia ou um elemento nodo.

Um elemento vazia é so mesmo a tag : <vazia/>

Um elemento nodo já é um pouco mais que isso. Contém uma sequência de duas referências recursivas para o elemento arvbin e ainda um atributo valor que contém apenas um inteiro. ( De notar que poderíamos preencher a nossa árvore binária com a informação que quiséssemos dentro da tag <nodo>.)

Segue-se então o códido do Schema:

<?xml version="1.0" encoding="ISO-8859-1"?>
<!-- edited with XMLSpy v2008 sp1 (http://www.altova.com) by André (EMBRACE) -->
<!--W3C Schema generated by XMLSpy v2008 sp1 (http://www.altova.com)-->
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">
 <xs:element name="arvbin">
  <xs:complexType>
   <xs:choice>
    <xs:element name="vazia"/>
    <xs:element ref="nodo"/>
   </xs:choice>
  </xs:complexType>
 </xs:element>
 <xs:element name="nodo">
  <xs:complexType>
   <xs:sequence>
    <xs:element ref="arvbin"/>
    <xs:element ref="arvbin"/>
   </xs:sequence>
   <xs:attribute name="valor" type="xs:int" use="required"/>
  </xs:complexType>
 </xs:element>
</xs:schema>

Podem fazer download de uma instância desta árvore binária aqui.

(PS: O programa que uso para trabalhar com XML é o XML Spy.)



Veja também:

Tags: ,

Post a Comment