基于XML链式结构的研究

　　简介：在数据结构中，树型结构是一种非常重要的非线性结构，树形结构是结点之间有分支，并具有层次关系的结构。XML非常适合表达树的层次逻辑，为此将XML与数据库技术结合起来，实现树的显示和维护。

　　1 二叉链表的结构

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

　　2 树形结构的具体实现

　　2.1 二叉链表结构的设计

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

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

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

　　算法描述：

　　2.3 解析XML显示树形结构

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

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

　　算法描述：

　　2.4 基于树形结构的维护

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

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