路径存储法在生成树形结构中的应用研究

唐青松

(四川文理学院计算机学院，四川 达州 635000)

0 引言

树形结构应用十分广泛，它不但可以为用户随时更改树的结构和随意调整树节点的层次关系带来方便，而且以树状外观展示给用户，体现出一种简约美。现有的生成树形结构主要由以下技术实现:(1)遍历节点法，即使用树的遍历算法排列出数据库中节点的访问顺序，然后根据节点序列生成树结构。该方法在遍历算法的执行过程中，每个节点至少被访问2次，并且需要从数据库中频繁地检索节点信息，当节点数量较多的时候，其算法执行的耗时比较长，导致效率低下。(2)层点展开法，使用Javascript函数监听鼠标对树节点的单击，触发异步传输技术(AJAX)加载子节点的事件，以实现展开或隐藏子节点。该方法应用比较广泛，生成树结构的效率较高，由于该方法是逐层展开树分支，因此在访问子树节点方面存在不足。(3)多表存储法，按照树结构的层次关系，分别为每一层的节点创建数据表并实现“一对多的关联”，依次从各层的数据表中取出节点即可生成树结构。该技术由于数据表数量的限制，因此在树的层次伸展方面受到了约束。

综上多种实现树形结构方法存在的问题，可通过路径存储法进行改进。该方法使用节点排序法为技术路线，在数据表中设置一个字段用于存储树节点的路径，由数据库排序检索产生的节点序列来创建树形结构。

1 路径存储法创建树结构

1.1 相关定义及性质

定义1 路径存储法是从树根节点出发，树中某一节点为终点，沿这一路径中的线性结构，把各节点依次组合而成的字符串存储在数据表特定字段中的方法。例:在图1中的节点I的路径可以表示为A，B，F，I。

图1 树形结构层次结构关系

从数学的角度分析，路径可以定义为一个集合对:P=(V，E)，其中V是节点的非空有限集合，E是边的集合，集合E的势为节点的深度，记为。根据路径存储法的定义，结合树形结构，可以得出以下性质:

性质 1 在一棵树 T={P1，P2，…，Pi，…，Pn}中，对∀Vi和 Vj(i，j=1，2，3，…，n 且 i≠j)，有 Vi∩Vj≠Ø。

证明 由树结构的定义，在一棵树中，所有节点是树根节点 Pk的后裔，又 Pi∈T，Pj∈T，则有 vk∈Vi，vk∈Vj，因此至少存在集合{vk}，使得 Vi∩Vj={vk}，命题得证。

推论 V1∩V2=Ø，则节点P1和P2不在同一棵树中。

性质 2 在树 T={P1，P2，…，Pi，…，Pn}中，节点P1，P2，若 V1∩V2=V1，则 P1是 P2的先驱节点。

证明 由定义1可知，每一个树的节点路径由其父节点、祖父节点直到树根节点所组成的一个集合，再由树结构的定义，一棵树的节点只能有一个父节点，因此，后裔节点必然按照其先驱节点进行展开，所以，后裔节点路径中的元素一定有前驱节点元素组成的集合，由此可得V1∩V2=V1，则P1是P2的先驱节点，反之，若P1是P2的先驱节点，则V1∩V2=V1。

定义2(叶子节点) 在一棵树 T={P1，P2，…，Pi，…，Pn}中，对∀Vi(i=1，2，…，n)，有 Vj⊄Vi(j≤n，i≠j)，则节点 Pi是叶子节点。

定义3(树的深度) 在一棵树 T={P1，P2，…，Pi，…，Pn}中，树的深度为 max(|Ei|)，其中 i≤n。

定义4(节点深度) 节点Pi(i≤n)的深度为。

定义5(树根节点) 在树 T={P1，P2，…，Pi，…，Pn}中，满足条件|Ei|=1的节点是树根节点。

1.2 设计存储节点的关系表

生成动态树结构，需要有提供树节点信息的数据支撑。根据路径存储法的定义，在数据库中设计一个关系数据表，用于存放各节点的信息，其结构如表1所示。

表1 存放树节点信息的数据表结构

数据表中节点编号(id)为主键，根据节点编号值在数据表中的唯一性这一特点，因此在存储树节点信息时，设置路径信息由节点编号值组成，各编号之间逗号分隔，并将这些编号和逗号连接成字符串，存储到节点路径字段中。这种方式组成的路径值，可以保证节点路径的准确性。

1.3 生成动态树结构的原理

在J2EE工程中创建Java类，使之与节点信息建立对象关系映射(ORM)，然后在工程中设计出数据事务处理类，用于对节点信息实现在数据表中添加、修改、删除和检索节点信息等方法，在类中创建一个返回值为节点对象集合的函数，函数中使用以路径为排序依据的数据库查询语句，查询结果的每一个数据项对节点对象进行初始化，并按照结果的序列将对象添加到集合中，用于为生成树结构的程序提供数据。

生成树形结构的过程中，依次取出底层数据事务对象提供的节点信息，依据节点路径中的逗号数量，计算出该节点在树中的深度，由此控制节点在树形图中的缩进位置。根据节点的相关定义和性质，判定得出节点名称前的显示图标。

为呈现树形图和实现树节点的展开和收缩状态，可以在HTML中使用表格嵌套的方式装载树节点(见图2)，设计出对节点名称前的图标添加鼠标点击的JS事件，当点击图标时触发JS函数，调用函数执行后，以实现隐藏或显示装载子树的表格。

图2 网页中表格嵌套布局设计

2 应用实例

在MyEclipse开发平台上，结合MySQL数据库，为某高校开发学生学籍卡管理系统，设计要求系统能直观展示出二级学院、专业、年级、班级等层次信息，操作中点击节点信息能显示出相应的学生信息。需求中的教学组织机构就是一个树结构，为此，设计了教学机构信息表(机构编号N(4)，机构名称C(50)，路径信息C(50))和学生信息数据表(学号C(12)，姓名C(10)，性别C(2)，…，机构编号 N(4))，使用教学机构数据表中的机构编号与学生信息表的机构编号建立一对多的联系，图3显示了教学机构信息表和学生信息表的部分数据和它们的关系。

图3 教学机构表和学生信息表之间的关系图

2.1 创建节点信息类

在J2EE工程中创建节点信息类(NodeInfo)，该类的对象由机构信息表中的数据进行初始化，用于生成树结构的事务中为程序提供数据支持，其属性主要有节点编号、节点名称、节点深度等，并设置各属性的Set和Get方法，用于提取对象的属性值。以下程序给出了节点信息对象的初始化方法:

以上程序中，实现了节点信息类的构造函数，其中的路径参数用于取节点的深度，由定义3得之，该节点的深度为路径中的逗号的数量。

2.2 教学机构节点排序的实现

使用路径存储的方式存储树节点信息，可以由路径升序的查询方式，快速地检索出数据表中存放的节点信息，并且检索出的结果节点序列符合生成树结构的条件。

设计SQL查询语句为“select*from dept_info order by path asc”，该语句实现对节点信息的排序检索，程序执行查询后，得到图4所示的结果。

图4 树节点排序检索结果图

在J2EE工程中创建与数据库连接的环境，通过JDBC实现对数据的访问，在程序中定义节点信息类的集合(List＜NodeInfo＞)，在查询的结果中依次取出每一条数据，该数据初始化节点信息对象后，添加到集合中，实现了对树节点信息的排序。

2.3 树形教学机构的实现

按照节点信息集合的序列，依次取出集合中的对象，并将该对象的信息装载到网页元素中，通过Web服务器对动态网页的解析，生成相应的HTML，从而在客户端浏览器中可以直观查看到树形结构。实现树结构的主要程序代码如下:

2.4 使用路径存储法的优势分析

在学生学籍卡管理系统中应用路径存储法，生成高校教学机构的树形图，通过系统的开发与运行，表现出的优势主要体现在以下方面:

(1)优化了数据库的设计。传统的多表关联技术，在设计数据表时，根据层次信息，需要用到存储二级学院信息、专业信息、年级信息和班级信息等4张数据表，并且在学生信息表中需要添加这4个表的主键字段与之建立关联。从图3的结构可以看出，使用树结构的方式存储机构信息，用2张数据表就可以满足要求。

(2)提高了检索子树节点的效率。结合图3中的数据可以看出，若要显示计算机科学与技术专业的学生信息，只需要执行以下SQL查询操作就可以得到学生数据:

select*from学生信息表where id in(select id from机构信息表 where path like‘1，2，%’)

其中的“select id from机构信息表where path like‘1，2，%’”子句，实现了快速查找到该节点的所有子树节点。该方式与自关联方式的数据表存储树节点的方式相比，在自关联数据表的存储结构中，查找子树节点需要使用树的遍历算法，算法执行中则要频繁地执行查询子节点或兄弟节点信息的操作，容易得知，当树节点数量较大的时候，其耗时较长。由此，该技术在查找子树节点方面也有着明显的优势。

3 结束语

本文分析了多种生成树形结构的方法，以树节点在关系数据库的存储方式为视角，给出了树节点的性质和相关定义，提出使用路径存储的方式将树节点保存在数据库中，并将该技术应用在某高校学生学籍卡管理系统的学生组织机构模块。学籍卡系统运行结果表明，路径存储法能在超大量节点存储状态中，快速检索教学组织机构的子树节点，并根据搜索到的结果快速查找到学生信息。该方法实施起来简单容易，对现有B/S系统的树结构模块改进具有一定的实用性。

［1］陈洁，张燕平，赵姝.一种结构化描述方法:保序性与或图［J］.南京大学学报:自然科学版，2013，49(2):235-243.

［2］张嘉惠，崔超艳.树形WBS在科研项目管理系统中的应用［J］.计算机系统应用，2012，21(4):23-26.

［3］吕刚，蒋勇铭，王军.基于关系型数据库的树形结构设计与实现［J］.计算机光盘软件与应用，2112(17):224-225.

［4］魏斌，马继辉，牛虎.基于递归算法的树型结构图的设计与实现［J］.计算机应用与软件，2011，28(1):96-98.

［5］李俊飞，陈皓，赵卫东.树形结构数据输入输出控件的设计与实现［J］.计算机工程与设计，2011，32(9):3054-3058.

［6］张华兴，孙毅，单继宏.网页树形结构自动生成研究［J］.计算机系统应用，2009，18(7):61-66.

［7］李睿，曾俊瑀，周四望.基于局部标签树匹配的改进网页聚类算法［J］.计算机应用，2010，30(3):818-820.

［8］魏纪东，王昭顺，戴桂兰，等.树形结构数据帧解析和处理［J］.小型微型计算机系统，2010，31(12):2252-2254.

［9］Marco Di Summa，Andrea Grosso，Marco Locatelli.Complexity of the critical node problem over trees［J］.Computers＆ Operations Research，2011，38(12):1766-1774.

［10］Coudert David，Huc Florian，Mazauric Dorian.A distributed algorithm for computing the node search number in trees［J］.Algorithmica，2012，63(2):158-190.

［11］Dunren Che.An efficient algorithm for tree pattern query minimization under broad integrity constraints［J］.International Journal of Web Information Systems，2007，24(3):103-118.

［12］Yuge T，Tagami K，Yanagi S.Calculating top event probability of a fault tree with many repeated events［J］.Journal of Quality in Maintenance Engineering，2006，33(4):1126-1153.

［13］Han K，Feng Y T，Owen D R J.Performance comparisons of tree-based and cell-based contact detection algorithms［J］.Engineering Computations，2007，30(2):247-261.

［14］Alfred V Aho，John E Hopcroft，Jeffrey D Ullman.The Design and Analysis of Computer Algorithms［M］.Addison Wesley/Pearson，2005.