最近看到一个有意思的树形结构，为每个节点添加了lft和rgt两个属性。这样查找该节点的子节点、查找该节点所有父节点，就不用去递归查询，只需要用between、and语句就可以实现。下面以创建一个栏目树为例，以下是我的理解。
一般来讲，我们创建栏目树的时候，大多只需要一个外键parentid来区分该节点属于哪个父节点。数据库的设计如下图：
这样一来，
1.查找该节点的所有子节点，则需要采用sql的递归语句：
select * from tableName connect by prior id=sj_parent_id start with id=1
(oracle 写法，mysql目前不支持，如果mysql想查找树形，可以利用存储过程).
2.查找该节点的父节点的sql递归语句：
select * from tableName connect by prior sj_parent_id =id start with id=1
如果数据量过大或者层次太多，那么这样操作是会影响性能的。
“任何树形结构都可以用二叉树来表示”。其实我们创建的栏目树就是一个简型的二叉树。根据数据结构里面二叉树的遍历，再稍微修改下，将数据库设计如下图所示：
这样我们查找该节点的所有子节点，则只需要查找id在lft和rgt之间的所有节点即可。
1.查找该节点的所有子节点的Sql语句为：
<!--EndFragment-->
<!--EndFragment-->
select * from tb_subject s,tb_subject t where s.lft between t.lft and t.rgt and t.id=1
2.查找该节点的所有父节点的sql语句为：
<!--EndFragment-->
select s.* from tb_subject s,tb_subject t where s.lft<t.lft and (s.rgt-s.lft)>1 and s.rgt>t.rgt and t.id=1
下面来详细讲解下，怎么用java来实现这种算法。
<!--EndFragment-->
1. 新增节点
新增节点比较简单，基本步骤为
A． 查找当前插入节点的父节点的lft值
B． 将树形中所有lft和rgt节点大于父节点左值的节点都+2
C． 将父节点左值+1，左值+2分别作为当前节点的lft和rgt
因为项目中采用的是struts2+hibernate3.2+spring2.5的框架，代码如下：
<!--EndFragment-->
public boolean onSave(Object entity, Serializable id, Object[] state,
String[] propertyNames, Type[] types) {
if (entity instanceof HibernateTree) {
HibernateTree tree = (HibernateTree) entity;
Long parentId = tree.getParentId();
String beanName = tree.getClass().getName();
Session session = getSession();
FlushMode model = session.getFlushMode();
session.setFlushMode(FlushMode.MANUAL);
Integer myPosition = new Integer(0);
//查找父节点的左值
if (parentId != null) {
String hql = "select b.lft from " + beanName
+ " b where b.id=:pid";
myPosition = (Integer) session.createQuery(hql).setLong("pid",
parentId).uniqueResult();
}
//将树形结构中所有大于父节点左值的右节点+2
String hql1 = "update " + beanName
+ " b set b.rgt = b.rgt + 2 WHERE b.rgt > :myPosition";
//将树形结构中所有大于父节点左值的左节点+2
String hql2 = "update " + beanName
+ " b set b.lft = b.lft + 2 WHERE b.lft > :myPosition";
if (!StringUtils.isBlank(tree.getTreeCondition())) {
hql1 += " and (" + tree.getTreeCondition() + ")";
hql2 += " and (" + tree.getTreeCondition() + ")";
}
session.createQuery(hql1).setInteger("myPosition", myPosition)
.executeUpdate();
session.createQuery(hql2).setInteger("myPosition", myPosition)
.executeUpdate();
session.setFlushMode(model);
//定位自己的左值(父节点左值+1)和右值(父节点左值+2)
for (int i = 0; i < propertyNames.length; i++) {
if (propertyNames[i].equals(HibernateTree.LFT)) {
state[i] = myPosition + 1;
}
if (propertyNames[i].equals(HibernateTree.RGT)) {
state[i] = myPosition + 2;
}
}
return true;
}
return false;
}
２. 修改节点
修改的时候比较麻烦，具体步骤为：
在修改lft和rgt之前，当前节点的父节点id已经改变
a. 查出当前节点的左右节点（nodelft、nodergt），并nodergt-nodelft+1 = span，获取父节点的左节点parentlft
b. 将所有大于parentlft的lft(左节点)、rgt(右节点)的值+span
c. 查找当前节点的左右节点（nodelft、nodergt），并parentlft-nodelft+1 = offset
d. 将所有lft(左节点) between nodelft and nodergt的值+offset
e. 将所有大于nodergt的lft(左节点)、rgt(右节点)的值-span
Java代码如下：
<!--EndFragment-->
public void updateParent(HibernateTree tree, HibernateTree preParent,
HibernateTree curParent) {
if (preParent != null && preParent != null
&& !preParent.equals(curParent)) {
String beanName = tree.getClass().getName();
// 获得节点位置
String hql = "select b.lft,b.rgt from " + beanName
+ " b where b.id=:id";
Object[] position = (Object[]) super.createQuery(hql).setLong(
"id", tree.getId()).uniqueResult();
System.out.println(hql+"| id = "+tree.getId());
int nodeLft = ((Number) position[0]).intValue();
int nodeRgt = ((Number) position[1]).intValue();
int span = nodeRgt - nodeLft + 1;
// 获得当前父节点左位置
hql = "select b.lft from " + beanName + " b where b.id=:id";
int parentLft = ((Number) super.createQuery(hql).setLong("id",
curParent.getId()).uniqueResult()).intValue();
System.out.println(hql+"| id = "+curParent.getId());
// 先空出位置
String hql1 = "update " + beanName + " b set b.rgt = b.rgt + "
+ span + " WHERE b.rgt > :parentLft";
String hql2 = "update " + beanName + " b set b.lft = b.lft + "
+ span + " WHERE b.lft > :parentLft";
if (!StringUtils.isBlank(tree.getTreeCondition())) {
hql1 += " and (" + tree.getTreeCondition() + ")";
hql2 += " and (" + tree.getTreeCondition() + ")";
}
super.createQuery(hql1).setInteger("parentLft", parentLft)
.executeUpdate();
super.createQuery(hql2).setInteger("parentLft", parentLft)
.executeUpdate();
System.out.println(hql1+"| parentLft = "+parentLft);
System.out.println(hql2+"| parentLft = "+parentLft);
// 再调整自己
hql = "select b.lft,b.rgt from " + beanName + " b where b.id=:id";
position = (Object[]) super.createQuery(hql).setLong("id",
tree.getId()).uniqueResult();
System.out.println(hql+"| id = "+tree.getId());
nodeLft = ((Number) position[0]).intValue();
nodeRgt = ((Number) position[1]).intValue();
int offset = parentLft - nodeLft + 1;
hql = "update "
+ beanName
+ " b set b.lft=b.lft+:offset, b.rgt=b.rgt+:offset WHERE b.lft between :nodeLft and :nodeRgt";
if (!StringUtils.isBlank(tree.getTreeCondition())) {
hql += " and (" + tree.getTreeCondition() + ")";
}
super.createQuery(hql).setParameter("offset", offset)
.setParameter("nodeLft", nodeLft).setParameter("nodeRgt",
nodeRgt).executeUpdate();
System.out.println(hql+"| offset = "+offset+" | nodelft = "+nodeLft+" | nodergt = "+ nodeRgt);
// 最后删除（清空位置）
hql1 = "update " + beanName + " b set b.rgt = b.rgt - " + span
+ " WHERE b.rgt > :nodeRgt";
hql2 = "update " + beanName + " b set b.lft = b.lft - " + span
+ " WHERE b.lft > :nodeRgt";
if (tree.getTreeCondition() != null) {
hql1 += " and (" + tree.getTreeCondition() + ")";
hql2 += " and (" + tree.getTreeCondition() + ")";
}
super.createQuery(hql1).setParameter("nodeRgt", nodeRgt)
.executeUpdate();
super.createQuery(hql2).setParameter("nodeRgt", nodeRgt)
.executeUpdate();
System.out.println(hql1+"| nodeRgt = "+nodeRgt);
System.out.println(hql2+"| nodeRgt = "+nodeRgt);
}
}
３. 删除节点
删除节点也比较简单，具体步骤为：
A． 查找要删除节点的lft值
B． 将所有lft和rgt大于删除节点lft值的都-2
Java代码如下：
<!--EndFragment-->
<!--EndFragment-->
public void onDelete(Object entity, Serializable id, Object[] state,
String[] propertyNames, Type[] types) {
if (entity instanceof HibernateTree) {
HibernateTree tree = (HibernateTree) entity;
String beanName = tree.getClass().getName();
Session session = getSession();
FlushMode model = session.getFlushMode();
session.setFlushMode(FlushMode.MANUAL);
//查找要删除的节点的左值
String hql = "select b.lft from " + beanName + " b where b.id=:id";
Integer myPosition = (Integer) session.createQuery(hql).setLong(
"id", tree.getId()).uniqueResult();
//将所有大于删除节点左值的rgt都-2
String hql1 = "update " + beanName
+ " b set b.rgt = b.rgt - 2 WHERE b.rgt > :myPosition";
//将所有大于删除节点左值的lft都-2
String hql2 = "update " + beanName
+ " b set b.lft = b.lft - 2 WHERE b.lft > :myPosition";
if (tree.getTreeCondition() != null) {
hql1 += " and (" + tree.getTreeCondition() + ")";
hql2 += " and (" + tree.getTreeCondition() + ")";
}
session.createQuery(hql1).setInteger("myPosition", myPosition)
.executeUpdate();
session.createQuery(hql2).setInteger("myPosition", myPosition)
.executeUpdate();
session.setFlushMode(model);
}
}
<!--EndFragment-->
<!--EndFragment-->
<!--EndFragment-->
<!--EndFragment-->
<!--EndFragment-->
<!--EndFragment-->
- 大小: 8.5 KB
- 大小: 12.6 KB
分享到：
相关推荐
在设计树形结构算法时，需要考虑如何高效地从原始数据中构建出所需的树形结构。算法设计的关键在于节点的查找和插入，尤其是如何高效地从上一级节点找到下一级的所有子节点。在树形结构中，每个节点可能包含多个子...
Java 递归算法构造 JSON 树形结构 Java 递归算法构造 JSON 树形结构是指通过 Java 语言使用递归算法将数据库中的菜单表构建成树形的 JSON 格式发送给第三方。这种方法可以将复杂的树形结构数据转换成易于理解和处理...
在实际应用中，树形结构常用于实现文件系统、数据库索引、图算法（如A*寻路）、表达式解析、编译器语法树等。例如，在设计一个组织结构管理系统时，每个节点可以代表一个员工，其子节点则表示其下属，这样就形成了一...
Java树形结构是一种数据结构，它模仿了自然界中的树状模型，由节点（或称为顶点）和边组成。在计算机科学中，每个节点可以有零个或多个子节点，而根节点没有父节点。这种结构广泛应用于各种编程场景，如文件系统、...
"java树节点逐级汇总.zip"这个压缩包提供的内容，旨在帮助开发者处理无序列表数据，并将其转化为可以逐级汇总的树形结构。下面将详细介绍这个过程中的关键知识点。 1. **树形结构**： - 树形结构是一种非线性的...
### 树形结构算法：非递归方法与JSTree应用 #### 引言 在IT行业，尤其是在软件开发和数据库管理领域，树形结构是一种常见的数据组织方式，用于表示层级关系的数据集。传统的树形结构操作往往依赖于递归算法，这在...
在IT领域，树形结构是一种常见的数据组织方式，它模拟了自然界中的树状层次关系，广泛应用于文件系统、数据库索引、计算机科学的算法设计等多个方面。在这个项目中，我们探讨的是如何在Java环境中，利用JSP（Java...
总结起来，Java创建树形结构算法的核心在于使用数据结构（如List和Map）和适当的排序机制来构建层次关系。`MenuExt`类和`createTreeMenus()`方法的实现是这种思路的具体体现，它们能帮助开发者在JavaWeb应用中构建出...
树形选择排序的算法过程可以分为三步：构建树形结构、比较和选择、排序输出。 首先，我们构建一个树形结构，每个叶子结点代表一个记录，非叶子结点代表一个比较结果。然后，我们从叶子结点开始，逐步比较和选择最小...
* 递归可以实现树形结构的遍历。 六、哈希表 * 哈希表是一种基于键值对的数据结构。 * 哈希表可以实现快速查找、插入、删除等操作。 七、高级排序 * 高级排序包括快速排序、归并排序、堆排序等。 * 快速排序是...
在Java编程中，构建树形结构是一种常见的任务，特别是在数据结构和算法的设计中。树形结构是一种非线性数据结构，它由多个节点组成，每个节点可以有零个或多个子节点，这样的结构使得数据之间的关系更为清晰。本文将...
5. **树(Tree)**：树形数据结构表示具有层次关系的数据集合，其中最常见的是二叉树。 6. **图(Graph)**：图是由顶点和边组成的非线性数据结构，用于表示对象之间的复杂关系。 7. **散列表(Hash Table)**：散列表通过...
在Java中遍历MySQL数据库中的树形结构是一个复杂但重要的任务，涉及数据库设计、递归算法以及性能优化等多个方面。通过深入理解树形结构的特点，并采用合适的遍历算法和优化策略，可以有效地管理和操作复杂的层级...
在这个"java_树形结构文档"中，我们可能会深入探讨如何在Java中实现和操作树形结构。 树形结构由节点（或称为顶点）和边组成，其中每个节点可以有零个或多个子节点，这种关系形成了一种层次结构。在Java中，我们...
在本示例中，我们将探讨如何使用Spring JPA来实现单表递归树形结构。 首先，我们需要理解递归树形结构。在数据库中，树形结构通常通过自关联来表示，即一个表的某个字段引用该表自身，形成一个层级关系。对于单表...
使用递归算法结合数据库解析成Java树形结构的代码解析是指通过递归算法解析数据库中的树形结构数据，并将其转换为Java树形结构的过程。 首先，需要准备好表结构及对应的表数据。在这个示例中，我们创建了一个名为TB...
在编程中实现树形结构地址联动，可以使用各种编程语言，如JavaScript、Python、Java等，通常会用到数据结构库（如JavaScript的lodash.get和_.set，Python的jsonpath-ng等）来方便地操作和查询树形数据。 总的来说，...
java递归形成树形结构
递归允许函数调用自身，常用于树形结构的遍历或解决复杂问题的简化。分治策略则是将大问题分解为小问题来解决，如快速排序和归并排序就是典型的分治算法。 在Java中，集合框架提供了丰富的数据结构实现，如...
递归在处理树形结构和回溯问题时特别有用，例如汉诺塔问题。 汉诺塔问题是一个经典的递归问题，目标是将所有盘子从一根柱子移动到另一根柱子，同时遵循以下规则： 1. 每次只能移动一个盘子。 2. 不允许大盘子位于小...