基于XML链式结构的研究

　　1 引 言

　　在数据结构中，树型结构是一种非常重要的非线性结构，树形结构是结点之间有分支，并具有层次关系的结构。

　　它非常类似于自然界中的树。树结构在客观世界中是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构;在数据库系统中，可用树来组织信息;在分析算法的行为时，可用树来描述其执行过程。这里可以充分利用其优点进行系统管理。

　　XML(Extensible Markup Language，可扩展的标记语言)。XML是一套定义语义标记的规则，这些标记将文档分成许多部件并对这些部件加以标识。它也是元标记语言，即定义了用于定义其他与特定领域有关的、语义的、结构化的标记语言的句法语言。其起源于SGML(Stand-ard Generalized Markup Language)，是SGML的一个子集合，即SGML的一个简化版本，它非常适合于在Web上或其他多种数据源问进行数据的交换。XML非常适合表达树的层次逻辑，为此将XML与数据库技术结合起来，实现树的显示和维护。

　　2 二叉链表的结构

　　在计算机中存储一棵树，不仅要存储树中每个结点的数值，而且还要存储结点与结点之间的关系。二叉树(Binary Tree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由1个根结点及2棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。

　　3 树形结构的具体实现

　　3.1 二叉链表结构的设计

　　给出一个二叉树接点的Java接口，称之为BinNode。BinNode类中存储指向Object类的引用。创建二叉树时，可以根据需要而采用实际的数据类型。成员函数包括返回元素的值，返回左、XML右节点指针，设置元素的值，判断该结点是否为叶结点。

　　3.2 将数据库中树的信息转化成XML

　　初始条件：树T存在，id是树中某个结点编号。操作目的：将以id为根结点的子树转化为XML格式。算法思想：根据当前根结点找出左孩子和右兄弟，添加当前结点信息到XML中，然后递归以左孩子为根结点的子树，最后在递归以右兄弟为根结点的子树。还要注意如果当前结点为该树的根结点，则不能递归以它的右兄弟为根结点的子树。

　　算法描述：

　　3.3 解析XML显示树形结构

　　将数据库中以二叉链表结构存储的树的信息通过上述方法转化为所需的XML后，现在就可以通过操作XML文档对象模型将数据岛显示在浏览器端。

　　初始条件：XML形式的数据岛。操作目的：通过JavaScript解析XML并以HTML的形式在浏览器端显示树。算法思想：将数据岛加载到DOM对象后，向浏览器添加根结点的HTML代码，对DOM对象根结点的所有一级子结点，再递归调用显示其下一级子结点的HTML代码。