树型结构之数据结构设计(附加JAVA版本实现)
发布日期:2022-02-15 02:36:10 浏览次数:3 分类:技术文章

本文共 7272 字,大约阅读时间需要 24 分钟。

我们经常需要在关系型数据库中保存一些树状结构数据,比如分类、菜单、论坛帖子树状回复等。常用的方法有两种:

1. 领接表的方式;

2. 预排序遍历树方式;

假设树状结构如下图:

领接表方式

主要依赖于一个 parent 字段,用于指向上级节点,将相邻的上下级节点连接起来,id 为自动递增自动,parent_id 为上级节点的 id。一目了然,“Java”是“Language”的子节点。

我们要显示树,PHP 代码也可以很直观,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
<?php
/**
 
* 获取父节点下的所有子节点
 
*
 
* @since 2011-05-18
 
*
 
* @param $parent_id 父节点 id,0 则显示整个树结构。
 
* @param $level 当前节点所处的层级,用于缩进显示节点。
 
* @return void
 
*/
function
show_children (
$parent_id
= 0,
$level
= 0)
{
    
// 获取父节点下的所有子节点
    
$result
= mysql_query(
'SELECT id, name FROM tree WHERE parent_id='
.
intval
(
$parent_id
));
    
// 显示每个子节点
    
while
(
$row
= mysql_fetch_array(
$result
)) {
        
// 缩进显示
        
echo
'<div style="margin-left:'
. (
$level
* 12) .
'px">'
.
$row
[
'name'
] .
'</div>'
;
        
// 递归调用当前函数,显示再下一级的子节点
        
show_children(
$row
[
'id'
],
$level
+ 1);
    
}
}
?>

想要显示整个树结构,调用 show_children()。想要显示“Database”子树,则调用 show_children(2),因为“Database”的 id 是 2。

还有一个经常用到的功能是获取节点路径,即给出一个节点,返回从根节点到当前节点的路径。用函数实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
<?php
/**
 
* @param $id 需要获取路径的当前节点的 id。
 
* @return array
 
*/
function
get_path(
$id
)
{
    
// 获取当前节点的父节点 id 和当前节点名
    
$result
= mysql_query(
'SELECT parent_id, name FROM tree WHERE id='
.
intval
(
$id
));
    
$row
= mysql_fetch_array(
$result
);
    
// 使用此数组保存路径
    
$path
=
array
();
    
// 将当前节点名保存进路径数组中
    
$path
[] =
$row
[
'name'
];
    
// 如果父节点非 0,即非根节点,则进行递归调用获取父节点的路径
    
if
(
$row
[
'parent_id'
]) {
        
// 递归调用,获取父节点的路径,并且合并到当前路径数组的其它元素前边
        
$path
=
array_merge
(get_path(
$row
[
'parent_id'
]),
$path
);
    
}
    
return
$path
;
}
?>

想要获取“MySQL 5.0”的路径,调用 get_path(4),4 即是这个节点的 id。

领接表方式的优点在于容易理解,代码也比较简单明了。缺点则是递归中的 SQL 查询会导致负载变大,特别是需要处理比较大型的树状结构的时候,查询语句会随着层级的增加而增加,WEB 应用的瓶颈基本都在数据库方面,所以这是一个比较致命的缺点,直接导致树结构的扩展困难重重。

排序遍历树方式

现在我们来聊聊第二种方式─预排序遍历树方式(即通常所说的 MPTT,Modified Preorder Tree Traversal)。此算法是在第一种方式的基础之上,给每个节点增加一个左、右数字,用于标识节点的遍历顺序,如下图所示:

从根节点开始左边为 1,然后下一个节点的左边为 2,以此类推,到最低层节点之后,最低层节点的右边为其左边的数字加 1。顺着这些节点,我们可以很容易地遍历完整个树。根据上图,我们对数据表做一些改变,增加两个字段,lft 和 rgt 用于存储左右数字(由于 left 和 right 是 MySQL 的保留字,所以我们改用简写)。表中各行的内容也就变成了:

接下来看看显示树/子树是多么简单,只需要一条 SQL 语句即可,比如显示“Database”子树,则需要获取到“Database”的左右数字,左为 2,右为 11,那么 SQL 语句是:

1
SELECT
*
FROM
tree
WHERE
lft
BETWEEN
2
AND
11;

SQL 语句是简单了,但我们所希望的缩进显示却是个问题。什么时候应该显示缩进?缩进多少单位?解决这个问题,需要使用堆栈,即后进先出(LIFO),每到一个节点,将其右边的数字压入堆栈中。我们知道,所有节点右边的值都比其父节点右边的值小,那么将当前节点右边的值和堆栈最上边的右边值进行比较,如果当前节点比堆栈最上边的值小,表示当前堆栈里边剩下的都是父节点了,这时可以显示缩进,堆栈的元素数量即是缩进深度。PHP 代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
<?php
/**
 
* @param $root_id 需要显示的树/子树根节点 id。
 
*/
function
show_tree(
$root_id
= 1)
{
    
// 获取当前根节点的左右数值
    
$result
= mysql_query(
'SELECT lft, rgt FROM tree WHERE id='
.
intval
(
$root_id
));
    
$row
= mysql_fetch_array(
$result
);
    
// 堆栈,存储节点右边的值,用于显示缩进
    
$stack
=
array
();
    
// 获取 $root_id 节点的所有子孙节点
    
$result
= mysql_query(
'SELECT name, lft, rgt FROM tree WHERE lft BETWEEN '
.
$row
[
'lft'
].
' AND '
.
$row
[
'rgt'
].
' ORDER BY lft ASC'
);
    
// 显示树的每个节点
    
while
(
$row
= mysql_fetch_array(
$result
)) {
        
if
(
count
(
$stack
)>0) {
//仅当堆栈非空的时候检测
            
// 如果当前节点右边的值比堆栈最上边的值大,则移除堆栈最上边的值,因为这个值对应的节点不是当前节点的父节点
            
while
(
$row
[
'rgt'
] >
$stack
[
count
(
$stack
)-1]) {
                
array_pop
(
$stack
);
            
}
//while 循环结束之后,堆栈里边只剩下当前节点的父节点了
        
}
        
// 现在可以显示缩进了
        
echo
'<div style="margin-left:'
.(
count
(
$stack
)*12).
'px">'
.
$row
[
'name'
].
'</div>'
;
        
// 将当前的节点压入堆栈里边,为循环后边的节点缩进显示做好准备
        
array_push
(
$stack
,
$row
[
'rgt'
]);
    
}
}
?>

获取整个树调用 show_tree(),获取“Database”子树调用show_tree(2)。在这个函数中,我们总算不需要用到递归了,呵呵。

接下来是显示从根节点到某节点的路径,这比起领接表方式来说也简单了很多,只需要一句 SQL 就行,不用递归  比如获取“ORACLE”这个节点的路径,其左右值分别是 7 和 10,则 SQL 语句为:

1
SELECT
name
FROM
tree
WHERE
lft <= 7
AND
rgt >= 10
ORDER
BY
lft
ASC
;

PHP 函数实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<?php
/**
 
* @param $node_id 需要获取路径的节点 id
 
*/
function
get_path2(
$node_id
) {
    
// 获取当前节点的左右值
    
$result
= mysql_query(
'SELECT lft, rgt FROM tree WHERE id='
.
intval
(
$node_id
));
    
$row
= mysql_fetch_array(
$result
);
    
// 获取路径中的所有节点
    
$result
= mysql_query(
'SELECT name FROM tree WHERE lft <= '
.
$row
[
'lft'
].
' AND rgt >= '
.
$row
[
'rgt'
].
' ORDER BY lft ASC'
);
    
$path
=
array
();
    
while
(
$row
= mysql_fetch_array(
$result
)) {
        
$path
[] =
$row
[
'name'
];
    
}
    
return
$path
;
}
?>

显示树和路径都没问题了,现在需要了解一下如何插入一个节点。插入新节点之前,首先要给这个节点腾出空位来,假设我们现在要在“ORACLE 9i”这个节点右边增加一个“ORACLE 10”,则腾位的 SQL 语句如下(“ORACLE 9i”的右边值为 9):

1
2
UPDATE
tree
SET
rgt=rgt+2
WHERE
rgt>9;
UPDATE
tree
SET
lft=lft+2
WHERE
lft>9;

位置空出来了,开始插入新节点吧:

1
INSERT
INTO
tree
SET
lft=10, rgt=11,
name
=
'ORACLE 10'
;

调用 show_tree() 看看结果对不对  具体的 PHP 实现代码这里就不写了。

现在总结一下预排序遍历树方式的优缺点。缺点是算法比较抽象,不容易理解,增加节点的时候虽然只用了几条 SQL 语句,但可能会需要更新很多记录,从而造成阻塞。优点是树的构造,路径获取方面性能都比领接表方式好很多。也就是说,这个算法牺牲了一些写的性能来换取读的性能,在 WEB 应用中,读数据库的比例远大于写数据库的比例,所以预排序遍历树方式比领接表方式更加受欢迎,更加实用,很多应用中都能看到 MPTT 的影子,通常所用的表里都有字段 lft 和 rgt。

转自:

 

以下是java版本的实现

 

 

public ResultObject addFile(int parentid,int lft,int rgt,int userid,String newFileName,String fileType){		getSession();		ResultObject ro=new  ResultObject();		String addedNodeId=null;		try {			Query updateRgt=service.createSQLQuery("update `uidesign_workfile` set rgt=rgt+"+2+" where user_id="+userid+" and rgt>="+rgt);			updateRgt.executeUpdate();			Query updateLft=service.createSQLQuery("update `uidesign_workfile` set lft=lft+"+2+" where user_id="+userid+" and lft>"+rgt);			updateLft.executeUpdate();			Query insertItem=service.createSQLQuery("insert into `uidesign_workfile` (parent_id,lft,rgt,filename,user_id,createtime,organization,creator,fileType) values ("+parentid+","+rgt+","+(rgt+1)+",'"+newFileName+"',"+userid+",'"+DateFormat.getDate("yyyy-MM-dd")+"',1,1,'"+fileType+"')");				insertItem.executeUpdate();			Object[] file=(Object[])loadFile(rgt,"lft",userid);			addedNodeId=file[0].toString();		}catch (Exception e){			e.printStackTrace();			ro.setErrormess("后台错误:添加数据失败,请联系管理员。");		}		ro.setResult(getAllFiles(userid));		if (fileType.equals("file")) ro.setOperateType("addfile");		if (fileType.equals("folder")) ro.setOperateType("addfolder");				ro.setParams(setParams("id",addedNodeId));		service.close();		return ro;	}	public ResultObject modFile(int currId,int userid,String newFileName){		getSession();		ResultObject ro=new  ResultObject();		int modId=currId;		try {			Query updateItem=service.createSQLQuery("update `uidesign_workfile` set filename='"+newFileName+"' where user_id="+userid+" and id="+currId);			updateItem.executeUpdate();		}catch (Exception e){			e.printStackTrace();			ro.setErrormess("后台错误:修改数据失败,请联系管理员");		}		ro.setResult(getAllFiles(userid));		ro.setParams(setParams("id",modId));		ro.setOperateType("modfile");		service.close();		return ro;	}	public ResultObject delFile(Integer id,Integer lft,Integer rgt,Integer userid){		getSession();		ResultObject ro=new  ResultObject();		int pyl=(rgt-lft+1);		try {			Query delSelf=service.createSQLQuery("delete from `uidesign_workfile`  where user_id="+userid+" and lft>="+lft+" and lft<"+rgt);			delSelf.executeUpdate();			Query updateRgt=service.createSQLQuery("update `uidesign_workfile` set rgt=rgt-"+pyl+" where user_id="+userid+" and rgt>"+rgt);			updateRgt.executeUpdate();			Query updateLft=service.createSQLQuery("update `uidesign_workfile` set lft=lft-"+pyl+" where user_id="+userid+" and lft>"+lft);			updateLft.executeUpdate();		}catch (Exception e){			e.printStackTrace();			ro.setErrormess("后台错误:更新数据失败,请联系管理员");		}		ro.setResult(getAllFiles(userid));		ro.setOperateType("delfile");		service.close();		return ro;	}

 

 

转载地址:https://blog.csdn.net/peterlu20110415/article/details/6616467 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:FLEX日志等系统信息输出设计
下一篇:html汇总

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月14日 23时32分45秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java 自助更改密码 api_搭建ldap自助修改密码系统--Self Service Password 2019-04-21
php继承exten,stylus中文文档 » 继承(@extend) » 张鑫旭-鑫空间-鑫生活 2019-04-21
mysql函数大全 pdf,MySQL函数大全 2019-04-21
php 常用文件系统函数,php 文件系统函数整理介绍 2019-04-21
android pm.java,java – AM / PM的Android DateFormat因设备而异 2019-04-21
oracle存储过程调用sql文件,oracle - 在SQL Developer中运行存储过程? 2019-04-21
oracle同时报604和12507,V$SES_OPTIMIZER_ENV 查不到刚修改的隐含参数, 2019-04-21
zblog的php更换域名,zblogphp更换域名后,原zblog里使用了固定域名,登录不进去怎么办... 2019-04-21
oracle dnfs 配置,Source of Oracle参数解析(dnfs_batch_size) - django-\/\/ i K | 2019-04-21
oracle所需的环境,转:面对一个全新的oracle环境,首先应该了解什么? 2019-04-21
linux 小数四则运行,shell四则运算(整数及浮点数)的方法介绍 2019-04-21
linux系统分区后进入紧急模式,Linux系统的救援模式应用详解 2019-04-21
linux配置匿名ftp服务器,在Linux环境中使用vsftpd搭建ftp实现匿名上传详细配置 2019-04-21
linux创建硬盘分区lvm,LVM创建及分区调整、更换LVM硬盘 2019-04-21
FreeBSD可以安装Linux软件吗,在Linux服务器上面通过网络安装FreeBSD 2019-04-21
.net core linux 桌面应用,C# dotnet core + AvaloniaUI 开发桌面软件,hello world 2019-04-21
linux tcp 113错误,linux系统报tcp_mark_head_lost错误的处理方法 2019-04-21
南昌工程学院c语言答案,南昌工程学院C语言程序设计基础课件第3讲运算符和表达式... 2019-04-21
python学画画_python学画画(下) 2019-04-21
云栖社区 mysql_【直播结束,已更新回放】PG、MySQL到底哪个好?云栖说这次请来五位专家撕了一下-阿里云开发者社区... 2019-04-21