基于XML链式结构的研究

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

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代码。

算法描述：

3.4 基于树形结构的维护

从数据库中提取树的信息后，在浏览器端树上设置JavaScript事件，通过它们我们可以对该树进行维护，包括插入、删除、更新、移动等操作。维护的时候，JavaScript事件将用户对树的维护情况记录到XML对象中。

其他删除、更新、移动结点操作需要对XML增加的信息与此相似。用户维护结束，将该XML对象提交到服务器，后台负责根据设置的插入、删除等操作标志解析上述XML对象，就可以生成相应的插入、删除、更新的SQL语句，最后提交到数据库。另外需要注意的是，由于数据库中存储的二叉链表形式的各结点相互间有关联，所以对其进行插入、删除、移动操作时候还必须考虑因此操作而引起的相关结点的信息的更新，比如当删除一个结点时，除了需要删除该结点外，还可能要修改其父结点的左孩子指针的值，或者需要修改其上一个兄弟结点的右兄弟指针的值。

4 结 语

软件设计中数据结构的选择十分重要。对目前应用非常广泛的树形结构做了比较深入的研究，发现应用XML技术和二叉链表的存储结构相结合能够非常方便稳定地存储、显示、维护树，并且此种存储结构应用于支持递归SQL的Oracle数据库时更能体现其方便性，如获取该树的一个子树，以及取得某结点的父结点等都可以通过1条简洁的递归SQL语句实现，为该树的可扩展性和可通用性提供了必要的条件。