摘要：本文介绍了树型结构数据在关系数据库中存储的思想和一种在网页中显示树型数据结构的方法。把树型结构数据存储在关系数据库中，以便于对每一个节点进行各种有关树的操作。在网页中直观的显示存储在关系数据库中的平面数据节点需要DBMS提供的递归计算功能的配合和HTML的使用技巧。
关键字：树型结构 嵌套标签 平面关系
Research of storage in Relational Database and display on web based data of tree structure
Abstract：
A thinking about data of tree structure how to stored in relational database and a method of how about these data is displayed on web is discussed in this paper. When data of tree structure is stored in database ,it is easy to observer modifications of each data node .Display of plane data note stored in relational [1]database on web needs cooperation of recursive calculational function provided by DBMS and skill of usage about HTML.
Key words: tree structure nesting label plane relation
引言：树型结构是很熟悉的一种模型。它的应用十分广泛，比如组织结构，物料清单，资料档案管理，资产管理等等都是以树型结构为基础。在现实生活中，有许多事物可以抽象为树状结构。这种结构可以简化对某些事物的理解，使概念清晰。树型结构在数据库存储的表结构可以很简单也可以很复杂。根据不同的需求，表结构不是一成不变的，读取数据的方法也不尽相同。在B/S架构下直观的表达树型结构需要深刻理解HTML标签的作用和显示的效果之间的关系，以及利用数据库提供的递归计算功能。
1.
树型结构的特征和数据库存储
树型结构是数据结构中的一种重要结构，由节点和分支组成。两个节点由分支连接，一端的节点称作父节点，另一端的节点称为子节点,
同一个节点的孩子相互之间是兄弟。有两条规则可以识别节点和分支。第一条规则是每个节点只能有一个父节点，有一个节点没有父节点。这个没有父节点的节点称作树的根节点（或者称为根），第二条规则是每棵树必须有且只有一个根节点。没有子节点的节点称为叶子节点。树有许多不同的形式，一棵树可以只包含一个节点，树的节点可以有不同数目的子节点，也可以没有子节点。
(图1)简单二叉树
二叉树是每个节点最多由两个孩子节点组成的树，它是一种典型的树型结构。下面以简单二叉树为例说明树结构的存储。简单二叉树仅仅说明了有直接关系的两个节点的父子关系。在数据库中，把每个节点看作一个单独的实体，每个实体有一个标识，称为键。每个节点至少需要存储一个键（node_id），相应的数据(date)，当前节点在兄弟节点中的位置 (pos)，子节点的个数(node_id_num),和节点的键(pNode_id)。由于父节点的键(pNode_id)为参照自身表的外键，这个表一中递归表。相应的E_R（Entity_Relation）图如图2所示：
(图2)二叉树的数据库存储的概念模型
可以使用这种表存储树结构数据，并可以分别的观察每个节点的变化情况。以二叉树为例，
pos
字段可以存储汉字“左“或者“右
”,
也可以存储代表左和右的数字
,
在二叉树上进行的操作也可以在数据库中存储的二叉树中进行操作，比如可以查看一个节点的所有孩子节点信息，按照先序递归遍历，按照中序或者后序进行便利，统计节点的个数等等。
存储在数据库中的树结构数据是平面的二维表，包含每个节点实体的数据。这些数据在表达节点之间的关系方面显得不够直观。为了方便表达这些节点之间的关系，需要对这些数据的表示进行改进。以简单二叉树在网页上的显示为例来说明树结构数据的显示。
2.
基于网页的树型结构数据表示
普通的客户端浏览动态网页的过程是客户端发送页面请求，服务器端按照客户端的请求，根据脚本动态生成页面的
HTML(
超文本标记语言
)
代码发送到客户端，客户端浏览器解析
HTML
代码并显示给客户。
HTML
代码是服务器端生成的重要资源，根据这些代码，客户端就可以显示不同的网页效果。经研究发现，使用
HTML
中的
<Table>
标签可以模拟生成二叉树的表示，并且不占用太多的资源。在
HTML
中，
<table>
标签是页面布局的常用手段
,
方便定位和控制大小。下面是使用
<table>
嵌套标签来表示的简单二叉树。
|
A
|
|||
|
B
|
C
|
||
|
E
|
F
|
G
|
H
|
(
图
3)
网页的表示
从数据库中读取的二叉树数据，并不像普通的带有指针的二叉树数据容易控制。经过研究发现，每个表格
<table>
中包括多个行
<TR>
，每一行包括多个单元格
<TD>
。这些表格同样是平面的，只包括行和列。在整个树的表示中，让根节点
A
为表中的单独的一行，并且只有一个单元格，跨两个列，第二行有两个单元格，如果根节点
A
有左孩子
B
，在第一个单元格中则嵌套一个表，显示以
B
为根节点的子树，如果
A
有右孩子，则在第二个单元格中新建一个表，在表中显示以
C
为根节点的字树。以此类推，便可以显示整个树的结构。由于
HTML
中的标签需要封闭，即如果有一个
<Table>
则必须对应一个
</table>,
在，服务器端生成动态页面是流水线形式的，不可能有类似于回退指针的形式。所以必须在合适的时候封闭对应的标签。按照以上的分析，整个图的结构需要的
HTML
标签应该类似于以下的代码
<TABLE><TR><TD colspan=2>A</TD></TR>
<TR><TD><TABLE><TR><TD>B…….</TABLE> </TD> …. </TR>
</TABLE>
3.
二叉树数据存储与网页显示的关键技术
在支持存储过程和递归运算的数据库管理系统中可以使用递归算法来解决这个问题，以
MSSQL
为例，可以写出如下存储过程，由于
MSSQL
支持的自定义字符类型变量最大长度为
8000
字符，为了显示更多层的节点，使用以下的字符代替相应的标签
,
在网页程序脚本中按照一定的次序替换这些字符便可以在在
8000
个字符的以内表示
10
层以内的节点数据。
--f=<table><TR><TD colspan=2>
--n=</TD></TR></table>
--p=</TD></TR><TR><TD>
--q=</TD><TD>
递归读取树型结构数据的存储过程定义如下：
--
定义的存储过程可以第归调用
zgdh2
位用户名
,@level
参数可以控制显示多少层。
--
初始化，定义变量
--
递归出口
if(@level < 1)return 'f'+rtrim(@data)+'n'
..
处理当前节点数据
--
如果有左孩子，递归调用算法
if exists(select 1 from tree where pnode_id=@node_id and pos = 1)
set @str = @str + zgdh2.getGraph(@child_id,@level -1)…
--
关闭
/
开启标签
set @str = @str + 'q'
--
如果有右孩子，递归调用算法
if exists(select 1 from tree where pnode_id=@node_id and pos = 2)
set @str = @str + zgdh2.getGraph(@child_id,@level -1)…
--
封闭标签并返回结果
set @str = @str + 'n'
return @str
在
asp
中假设已经连接到数据库，并且把结果读取到变量
str
中
则可以按照如下的替换调用顺序替换字符为标签，然后输出
str = replace(str,"n","</TD></TR></table>")
str =replace(str,"p","</div></TD></TR><TR><TD>")
str =replace(str,"q","</TD><TD valign='top'>")
str = replace (str,"f","<table><TR><TD colspan=2>")
4
试验结果:
在数据库中存储了树结构关系的人名，如
(
图
4)
所示，
张松霞下面是彭清兰和许惋春，整个图有
5
层，经过替换后从数据库中读取出来的结果大约有
200
个字符，替换为
HTML
表前后大约有
3500
个字符。
|
张松霞
|
|||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||
(
图
4)
人名的二叉树排列
5.
结论
:
树型结构的数据存储在数据库中需要一定的技巧，把每个节点作为一个实体，相互之间的关系也存储在数据库中，以便于依据
DBMS
的特点进行与树有关的操作。存储在关系数据库中的树是平面的，把数据库中存储的平面关系的树型结构显示出来，不仅要有
DBMS
提供的功能特点，也需要相关特定编程语言提供的功能的配合。树型图不仅能显示二叉树，也可是显示
3
叉树，
n
叉树，这种显示树型图的方法具有通用性和较强的实用性。
参考文献：
[1]
《
Database Solutiongs
》
[M]Thomas M.Connolly Carolyn E.Begg
北京
机械工业出版社
2005
[2]
《数据库系统概论》
[M]
（第三版）
萨师煊
王珊
北京
高等教育出版社
2003
[4]
《算法分析与设计技术》
[M]
贺红
,
马绍汉编著
科学出版社
2004
[5]
《
ASP
数据库系统开发案例精选》
[M]
盖天宇
,
孙明丽
,
邹天思编著
人民邮电出版社
2006
[6]
《数据库管理系统原理与设计》
[M] (
美
) Raghu Ramakrishnan, Johannes Gehrke
著
北京
-
清华大学出版社
2004
[7]
《
SQL Server
数据库管理、设计与实现教程》
[M]
赵杰，李涛，朱慧编著
北京
-
清华大学出版社
2004
[8]
《
SQL Server
高级开发与专业应用》
[M]
敬铮主编
北京
-
国防工业出版社
2002
[9] 《PowerDesigner 系统分析与建模》[M] 赵韶平…[等]编著 北京-清华大学出版社 2004
本文转自凌辉博客51CTO博客，原文链接http://blog.51cto.com/tianli/34900如需转载请自行联系原作者
lili00okok
