基于单表结构的Web动态树设计与实现

摘 要：在Web系统开发过程中，如何更直观显示具有层级关系的信息备受关注。树型结构因其结构性强、层次性好、使用方便等特点在Web系统开发中得到了广泛应用。介绍了树型结构原理和树型结构在关系型数据库中的表示，阐述了一种基于单表结构的Web动态树设计与实现。这种树型结构简单、直观、易于数据组织，简化了数据库的设计过程，在Web系统开发中效果良好。

关键词：树型结构；关系数据库；层次关系；Web动态树

DOIDOI：10.11907/rjdk.161997

中图分类号：TP391

文献标识码：A 文章编号文章编号：16727800（2016）011017003

0 引言

树型结构是一种非常重要的非线性数据结构，具有结构清晰、层次分明、操作方便等优点，在系统开发中应用广泛，如：Windows的资源管理器、文件系统中的文件管理、数据库中的索引等，都采用了树型结构[1]。随着互联网的迅速发展，树型结构在B/S结构系统开发中得到越来越广泛的应用。在Web页面上实现树型目录，既可简化创建、管理和维护工作，又可为浏览站点用户带来方便，将信息以更直观的层次结构展现给用户，充分利用了计算机屏幕空间。

目前在互联网上广泛应用的树型结构有两种：静态结构和动态结构。静态结构使用最多，实现简单，但它不能根据信息的变化改变树的结构和内容，因此无法反映信息变化，所以静态结构主要用于系统功能层次或固定组织结构表达中；而动态结构中树节点可以根据信息变化需要进行动态增删操作，可以展现动态的数据分类、组织机构等，但是实现相对复杂。

在动态树型结构的数据结构表达中，多数系统采用的是父子关系表的多表结构存储，表达动态树节点信息。这种方法虽然能不限层次地增加节点，但由于在进行统计分析等计算操作时，必须使用递归过程[2]致使计算过程十分复杂。本文将详细介绍使用单表结构来实现多级动态树[3]方法。

1 树型结构原理

树型结构主要由根节点、叶子节点和分支节点组成。任何没有上一级节点即没有父辈节点的节点是根节点；任何没有下一级节点即没有子女节点的节点是叶子节点；既不是叶子节点也不是根节点的为分支节点。一棵树只有一个根节点，分支节点可以有下一级分支节点，一个节点所有子树中的节点为该节点的子孙节点。树型结构中每个节点包含以下信息[4]：①节点自身信息；②双亲节点信息；③孩子节点信息，见图1。

由上述定义可看出：在树型结构中，树由多个子树构成，子树由一些更小的子树构成。总而言之，一个节点可以有0、1个或多个子节点，除根节点没有父节点[5]外，其余节点有且只有一个父节点。

关系数据库[6]（Relational Database ，简称RDB）已成为数据库产品的主流。关系数据库是将数据按表结构形式组织，而树型结构是一种非线性的数据结构。显然，树与表格在结构上有很大差别，若把具有树结构的数据简单线性排列起来，就不能体现数据间的父子关系（层次关系），意味着信息的丢失。因此，在关系型数据库中需要解决如何把非线性数据线性化排列且保留数据间的原有关系问题。

在关系型数据库中通常采用下面几种表示树的方法[7]：①字段表示法；②代码表示法；③静态指针表示法。

本文采用一种新的表示法，这种表示法是对代码表示法的一种变型。代码段的宽度根据树的层次不同而不同（根结点一般是一个全局结构描述的节点，可以用一个静态节点表示，本文使用静态节点处理）。

例如：某树的层次结构是** *** *** *** ***，用空格来区分树型结构层次，用*表示每个层次的代码段宽度。这个层次结构有4个空格，说明这个树型结构层次是5层。第一层代码段的宽度是2，第二层代码段的宽度是3，第三层代码段的宽度是4，依此类推可以得出每一层代码段的宽度。为了更好地表示树型结构的层次关系，本文把当前层次节点以上的层次节点代码宽度都加到当前层次代码宽度上，修改后的层级代码宽度为：第一层代码宽度是2，第二层代码宽度是5，第三层代码宽度是8，第四层代码宽度是11，第五层代码宽度是14。

根据这个层次结构，第一级节点可以用01表示，第二级节点可以用01001表示（前两位01表示当前节点的父节点），第三级节点可以用01001001表示（前五位01001表示当前节点的父节点），以此类推。这样不仅可以更直观地表示父节点、子节点及当前节点结构，还可以直观表示出树的层次关系。下面以部门为例对这种表示法进行说明。

2 动态树实现

2.1 数据库设计

为了记录节点变化，本文以数据库为载体。数据库中数据表至少要有以下字段：节点编号、节点名称、节点说明、节点代码，这些是构建树结构所必须的信息。建立数据表如表1所示。

2.2 创建树型结构流程

根据数据表设计，得到创建树型结构流程，如图2所示。

2.3 树的实现

为了对动态树构建有一个更清楚的理解，下面以部门树为例介绍实现过程。本示例采用Netbeans 6.1开发工具开发，服务器采用Netbeans 6.1自带的tomact，界面使用JSF进行设计[89]。

首先定义一个全局常量Levelno，设置树的层级结构假定为**** **** **** **** **结构，在实现动态树构建过程中定义几个函数：

public int getnodesize（String levelno，String sno）：根据树的层级结构levelno来判断给出的节点sno是第几层，如0001是第一级节点，00010001是第二级节点。

public int getFamtString（int i，String levelno，String sno）：根据树的层级结构levelno，把给出的节点sno转换为长度为i的数组，如000100010001转换为长度为3的数据{0001，00010001，000100010001}。

public int getChildNode（TreeNode PNode，String Cnum）：判断节点PNode的子节点中有没有节点值等于Cnum，如果有，返回当前节点，否则返回空节点。

public int getNode（String[]nodes）：在树结构中找到一个节点，这个节点是数组nodes中nodes[nodes.length-1]所对应节点的父节点，这个过程需要调用getChildNode（TreeNode PNode，String Cnum）方法进行辅助查找。

public int TreeNode_action（）：点击一个树节点时要触发的事件，如增加节点、修改节点、删除节点等事件处理代码。

按照动态树的构建流程进行设计。首先将无序数据从数据库中读出，在服务器端必须将排序后的数据发送到客户端显示。本文把数据按照节点代码顺序一次从数据库读出，执行代码select * from departments order by departLevelno。这种排序可以保证当添加到一个子节点时直接得到它的父节点（已经添加到树中了）。接着读第一条记录，把这条记录中的代码段与定义的全局变量进行比较，得到这条记录层次。如果层次是1，则说明是根节点，直接加到树型结构中，读下一条记录；如果层次不是1，则根据当前节点的代码段获取当前节点的直接父节点，添加到它的直接父节点下，读下一条记录。记录全部读完时，在Web页面（本文采用的是JSF）加载这部分代码，这样树型结构就构建成功了。具体代码如下：

//读第一条记录的sno

String leveno = this.getApplicationBean1（）.getLevelno（）；//得到前面定义的全局//变量

int i = this.getnodesize（leveno，sno）；

String[]childStr = this.getFamtString（i，leveno，sno）；

TreeNode childNode = new TreeNode（）；

if （i == 1） {

childNode.setId（"a" + sno）；

childNode.setText（departname）；

childNode.setImageURL（"/resources/tree_document.gif"）；

ExpressionFactory exFactory = this.getApplication（）.getExpressionFactory（）；

ELContext elContext = getFacesContext（）.getELContext（）； childNode.setActionExpression（exFactory.createMethodExpression（elContext，"#{HrResourceTree.TreeNode_action}"，String.class，new Class[0]））；

child.add（childNode）；

}

else {

childNode = this.getNode（childStr）；

TreeNode addChildNode = new TreeNode（）；

addChildNode.setId（"a" + sno）；

addChildNode.setText（departname）；

addChildNode.setImageURL（"/resources/tree_document.gif"）；

ExpressionFactory exFactory = this.getApplication（）.getExpressionFactory（）；

ELContext elContext = getFacesContext（）.getELContext（）；

addChildNode.setActionExpression（exFactory.createMethodExpression（elContext，"#{HrResourceTree.tripNode_action}"，String.class，new Class[0]））；

childNode.getChildren（）.add（addChildNode）；

}

//读下一条记录，直到最后一条记录

2.4 树的显示效果

本文对人力资源部门进行树型结构设计[10]，生产部、车间一、第一车段这3部分显示不同的层次关系，选定一个节点后可以进行其它相关操作（在TreeNode_action中添加相应事件代码），效果如图3所示。

3 结语

树型结构适合表达具有层次结构的信息，在数据库应用程序开发中经常用它表示对象之间的层次关系，便于用户操作和使用。本文通过一个树型结构例子，说明了层次关系数据在数据表中的存储方式和树型结构的构建方式，并把这种存储方式和构建方式应用于人力资源管理系统开发中。通过分析和实例验证，使用这种方式不仅能直观显示信息，而且能显示出信息的层次关系。

参考文献：

[1] 唐青松.路径存储法在生成树形结构中的应用研究[J].计算机与现代化，2014（14）：178181.

[2] 张维国，孙效玉，周冲.树形结构数据在数字矿山中的存储管理与应用[J].计算机技术与发展，2015，25（3）：150153.

[3] 特日根，李巍，李雄飞.动态有序树存储模型与实现方法[J].计算机研究与发展，2013，50（50）：969985.

[4] 吕刚，蒋勇铭，王军.基于关系型数据库的树形结构设计与实现[J].计算机光盘软件与应用，2112（17）：224225.

[5] 张雨佳，苏中滨，吴华瑞，等.半结构化数据的动态树存储模型研究[J].计算机应用与软件，2011，28（5）：8690.

[6] 李恒新，韩坚华.关系型数据库数据的高效判重[J].华南师范大学学报，2015（47）：121126.

[7] 施伯乐，丁宝康，楼荣生.数据库系统导论[M].北京：高等教育出版社，2008.

[8] 李俊飞，陈皓，赵卫东.树形结构数据输入输出控件的设计与实现[J].计算机工程与设计，2011（32）：30543058.

[9] 陈志平，徐锡山，陈玉教.一种基于Ajax的动态树型结构设计与实现[C].2007中国控制与决策学术年会论文集，2007：735742.

[10] 吴珊珊.某企业办公自动化系统的设计与实现[D].厦门：厦门大学，2013.