- 浏览: 56319 次
- 性别:
- 来自: 深圳
最新评论
-
liuweihug:
fusioncharts 图片2种方式使用java导出 - 项 ...
fusioncharts生成图表后导出图片 -
donggongai:
先表示一下感谢
fusioncharts生成图表后导出图片 -
shihuan830619:
谢谢博主的肯定。终于有人认可http://shihuan830 ...
fusioncharts生成图表后导出图片 -
purplesimon:
请问,隐藏这个图表之后还能下在图片不?谢谢!
fusioncharts生成图表后导出图片 -
woweiwokuang:
woweiwokuang 写道 我找这你的做了,修改节点的 ...
java树形结构 算法
最近看到一个有意思的树形结构,为每个节点添加了lft和rgt两个属性。这样查找该节点的子节点、查找该节点所有父节点,就不用去递归查询,只需要用between、and语句就可以实现。下面以创建一个栏目树为例,以下是我的理解。
一般来讲,我们创建栏目树的时候,大多只需要一个外键parentid来区分该节点属于哪个父节点。数据库的设计如下图:
这样一来,
1.查找该节点的所有子节点,则需要采用sql的递归语句:
(oracle 写法,mysql目前不支持,如果mysql想查找树形,可以利用存储过程).
2.查找该节点的父节点的sql递归语句:
如果数据量过大或者层次太多,那么这样操作是会影响性能的。
“任何树形结构都可以用二叉树来表示”。其实我们创建的栏目树就是一个简型的二叉树。根据数据结构里面二叉树的遍历,再稍微修改下,将数据库设计如下图所示:
1.查找该节点的所有子节点的Sql语句为: <!--EndFragment--> 2.查找该节点的所有父节点的sql语句为: <!--EndFragment--> 下面来详细讲解下,怎么用java来实现这种算法。 1. 新增节点 新增节点比较简单,基本步骤为 A. 查找当前插入节点的父节点的lft值 B. 将树形中所有lft和rgt节点大于父节点左值的节点都+2 C. 将父节点左值+1,左值+2分别作为当前节点的lft和rgt 因为项目中采用的是struts2+hibernate3.2+spring2.5的框架,代码如下: <!--EndFragment--> 2. 修改节点 修改的时候比较麻烦,具体步骤为: 在修改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--> 3. 删除节点 删除节点也比较简单,具体步骤为: A. 查找要删除节点的lft值 B. 将所有lft和rgt大于删除节点lft值的都-2 Java代码如下:
<!--EndFragment-->
<!--EndFragment-->select * from tableName connect by prior id=sj_parent_id start with id=1
select * from tableName connect by prior sj_parent_id =id start with id=1
这样我们查找该节点的所有子节点,则只需要查找id在lft和rgt之间的所有节点即可。select * from tb_subject s,tb_subject t where s.lft between t.lft and t.rgt and t.id=1
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
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;
}
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);
}
}
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-->
评论
不好意思. 是我搞错了.. 但是这些数据如何类维护呢? . 我现在是用parent 来建立了一个树,但是已经要几百条数据了. 如果在原数据的基础上添加这两个编号呢?
如:
根目录
目录1
目录2
目录2.1
01
0101
010101
0102
02
0201
020101
中等数据规模,100级以下
1 A 14
/ \
2 B 9 10 C 13
/ \ \
3 D 6 7 E 8 11 F 12
/
4 G 5
我要删除B,按照增加算法,删除后为
1 A 12
/ \
8 C 11
/ \ \
1 D 4 5 E 6 9 F 10
/
2 G 3
不知是否可以删除树枝?
从sql查询来看,还是满足条件的,但是二叉树被破坏了。
这个不是纯粹的算法,只是为了方便我们项目的一个工具,在项目中栏目树不能删除树枝,所以暂时未加考虑。。呵呵。不好意思。
不过您提出的问题,值得思考。。
如何保证,between lft 和 rgt 不会包含兄弟的子节点啊?
1
/ \
2 3
/ \ /
4 5 6
/
7
2节点的lft和rgt分别是?
这个id是数据库的主键,不一定是自动增长的,根据自己选择的数据库类型来定,只要唯一就可以了。
“如何保证,between lft 和 rgt 不会包含兄弟的子节点啊?”这个问题,查询的sql语句我已经给出来了,你可以测试一下。
1 A 14
/ \
2 B 9 10 C 13
/ \ \
3 D 6 7 E 8 11 F 12
/
4 G 5
其中A、B、C等字母代表节点,而数字分别代表lft和rgt,比如A的lft=1,rgt=14
谢谢,我基本看懂了
新的问题
1 A 14
/ \
2 B 9 10 C 13
/ \ \
3 D 6 7 E 8 11 F 12
/
4 G 5
我要为G增加一个兄弟,按照增加算法,增加后为
1 A 16
/ \
2 B 11 12 C 15
/ \ \
3 D 8 9 E 10 13 F 14
/ \
6 G 7 4 X 5
遍历路径似乎不太对了吧。
也许还是我对LFT何RGT的由来有点疑问导致的,到底这两个值是如何计算出来的?
是通过前序遍历算法得来的么?
这个遍历路径是不准确了。不过,这个算法是在新闻发布栏目树里面用到的,只是方便N层栏目的查询,而得到的数据,我们可以根据别的字段来进行排序,达到想要的结果。如果再去考虑遍历的路径,个人觉得有点多余了。
不过您提到的问题,值得思考。谢谢
/ \
2 B 9 10 C 13
/ \ \
3 D 6 7 E 8 11 F 12
/
4 G 5
这样的树形结构是怎么生成的?
以你的算法生成树应该是
1 A 6
/ \
4 B 4 2 C 3
才对
1 A 14
/ \
2 B 9 10 C 13
/ \ \
3 D 6 7 E 8 11 F 12
/
4 G 5
我要删除B,按照增加算法,删除后为
1 A 12
/ \
8 C 11
/ \ \
1 D 4 5 E 6 9 F 10
/
2 G 3
不知是否可以删除树枝?
从sql查询来看,还是满足条件的,但是二叉树被破坏了。
如何保证,between lft 和 rgt 不会包含兄弟的子节点啊?
1
/ \
2 3
/ \ /
4 5 6
/
7
2节点的lft和rgt分别是?
这个id是数据库的主键,不一定是自动增长的,根据自己选择的数据库类型来定,只要唯一就可以了。
“如何保证,between lft 和 rgt 不会包含兄弟的子节点啊?”这个问题,查询的sql语句我已经给出来了,你可以测试一下。
1 A 14
/ \
2 B 9 10 C 13
/ \ \
3 D 6 7 E 8 11 F 12
/
4 G 5
其中A、B、C等字母代表节点,而数字分别代表lft和rgt,比如A的lft=1,rgt=14
谢谢,我基本看懂了
新的问题
1 A 14
/ \
2 B 9 10 C 13
/ \ \
3 D 6 7 E 8 11 F 12
/
4 G 5
我要为G增加一个兄弟,按照增加算法,增加后为
1 A 16
/ \
2 B 11 12 C 15
/ \ \
3 D 8 9 E 10 13 F 14
/ \
6 G 7 4 X 5
遍历路径似乎不太对了吧。
也许还是我对LFT何RGT的由来有点疑问导致的,到底这两个值是如何计算出来的?
是通过前序遍历算法得来的么?
呸....
呸....
现在已经有数十种 acts_as_nested_set 和 acts_as_tree 了 ……
Pro Activerecord Database 这个本书没找到 能提供更多信息吗
现在已经有数十种 acts_as_nested_set 和 acts_as_tree 了 ……
不如把数据全抓出来重作
相关推荐
基于JAVA建立树形结构的算法优化.pdf
Java递归算法构造JSON树形结构,Java递归算法构造JSON树形结构Java递归算法构造JSON树形结构
本篇文章主要介绍了Java创建树形结构算法实例代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下。
基于JAVA建立树形结构的算法优化
主要介绍了java数据结构排序算法之树形选择排序,结合具体实例形式分析了java树形选择排序的原理、实现技巧与相关注意事项,需要的朋友可以参考下
java递归形成树形结构
比较详细的树形无递归技术文档,可以选择参考。
主要介绍了使用递归算法结合数据库解析成Java树形结构的代码解析的相关资料,需要的朋友可以参考下
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
JAVA_SQL递归树形,用递归算法结合数据库对J2EE实现树结构
无论您是初学者还是有经验的Java开发者,通过学习DFS算法,您将获得解决各种图形和树形结构问题的能力。 深度优先搜索(DFS)算法是解决图形和树形结构问题的重要工具,具有广泛的应用。本教程将深入介绍DFS算法的...
3.树形结构 (1)二叉树的性质及存储结构 (2)二叉树的遍历 (3)线索二叉树 (4)树的存储结构 (5)树、二叉树与森林的转化方法 (6)哈夫曼树 (7)二叉排序树及平衡化 (8)堆排序树 (9)B-树 4.图形结构 ...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...
逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)以及集合和队列等抽象数据类型。 存储结构(物理结构):描述数据在计算机中如何...