`
zhanglun1225
  • 浏览: 57305 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

java树形结构 算法

    博客分类:
  • java
阅读更多

最近看到一个有意思的树形结构,为每个节点添加了lftrgt两个属性。这样查找该节点的子节点、查找该节点所有父节点,就不用去递归查询,只需要用betweenand语句就可以实现。下面以创建一个栏目树为例,以下是我的理解。

  一般来讲,我们创建栏目树的时候,大多只需要一个外键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

 

 如果数据量过大或者层次太多,那么这样操作是会影响性能的。

 

  “任何树形结构都可以用二叉树来表示”。其实我们创建的栏目树就是一个简型的二叉树。根据数据结构里面二叉树的遍历,再稍微修改下,将数据库设计如下图所示:

 


这样我们查找该节点的所有子节点,则只需要查找idlftrgt之间的所有节点即可。

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. 将树形中所有lftrgt节点大于父节点左值的节点都+2

 C. 将父节点左值+1,左值+2分别作为当前节点的lftrgt

 因为项目中采用的是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;
	}

 

 2. 修改节点

  修改的时候比较麻烦,具体步骤为:

  在修改lftrgt之前,当前节点的父节点id已经改变

a. 查出当前节点的左右节点(nodelftnodergt),并nodergt-nodelft+1 = span,获取父节点的左节点parentlft

b. 将所有大于parentlftlft(左节点)rgt(右节点)的值+span

c. 查找当前节点的左右节点(nodelftnodergt),并parentlft-nodelft+1 = offset

d. 将所有lft(左节点) between nodelft and nodergt的值+offset

e. 将所有大于nodergtlft(左节点)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);
			
		}
	}

 

 3. 删除节点

 删除节点也比较简单,具体步骤为:

 A. 查找要删除节点的lft

 B. 将所有lftrgt大于删除节点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
分享到:
评论
43 楼 woweiwokuang 2012-04-16  
woweiwokuang 写道
   我找这你的做了,修改节点的时候有问题的.   我特意用图画了一下..


不好意思. 是我搞错了.. 但是这些数据如何类维护呢? .  我现在是用parent 来建立了一个树,但是已经要几百条数据了.  如果在原数据的基础上添加这两个编号呢?
42 楼 woweiwokuang 2012-04-13  
   我找这你的做了,修改节点的时候有问题的.   我特意用图画了一下..
41 楼 waainli 2012-04-06  
可以支持多个子节点吗?
40 楼 zzpxingfu 2010-06-08  
看起来还不错 只是还没有研究过
Java不错算法
39 楼 xyflash 2010-06-08  
我要是想显示树形列表 sql 又该如何书写 ?


如:
根目录
  目录1
  目录2
    目录2.1
38 楼 bloodwolf_china 2010-03-18  
我的算法是用节点深度加parentID解决
01
  0101
      010101
  0102
02
  0201
      020101
中等数据规模,100级以下

 
37 楼 cqwww 2010-03-03  
加一个字段orders ,平级排序,记录上级ID,记录子级所有ID, 一条SQL搞定。不用规递
36 楼 jv520jv 2010-03-03  
受用了..
35 楼 zhanglun1225 2010-03-02  
andsofish 写道
新的问题

            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查询来看,还是满足条件的,但是二叉树被破坏了。



这个不是纯粹的算法,只是为了方便我们项目的一个工具,在项目中栏目树不能删除树枝,所以暂时未加考虑。。呵呵。不好意思。
不过您提出的问题,值得思考。。
34 楼 zhanglun1225 2010-03-02  
andsofish 写道
zhanglun1225 写道
andsofish 写道
还有一个问题:你的id是自增长编号么?
如何保证,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层栏目的查询,而得到的数据,我们可以根据别的字段来进行排序,达到想要的结果。如果再去考虑遍历的路径,个人觉得有点多余了。
不过您提到的问题,值得思考。谢谢
33 楼 quysc 2010-03-02  
            1 A 14
        /        \
    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
才对   
32 楼 曾经de迷茫 2010-03-01  
left / right 如何维护?
31 楼 andsofish 2010-03-01  
新的问题

            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查询来看,还是满足条件的,但是二叉树被破坏了。
30 楼 andsofish 2010-03-01  
zhanglun1225 写道
andsofish 写道
还有一个问题:你的id是自增长编号么?
如何保证,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的由来有点疑问导致的,到底这两个值是如何计算出来的?
是通过前序遍历算法得来的么?
29 楼 andsofish 2010-03-01  
抛出异常的爱 写道
askyuan 写道
给一个树形结构的例子,包括前台jsp+后台java代码+数据库,写完整咯

呸....


28 楼 抛出异常的爱 2010-03-01  
askyuan 写道
给一个树形结构的例子,包括前台jsp+后台java代码+数据库,写完整咯

呸....
27 楼 hcqenjoy 2010-03-01  
night_stalker 写道
参见 Pro Activerecord Database (2007) 102 页
现在已经有数十种 acts_as_nested_set 和 acts_as_tree 了 ……

Pro Activerecord Database 这个本书没找到 能提供更多信息吗
26 楼 askyuan 2010-02-28  
给一个树形结构的例子,包括前台jsp+后台java代码+数据库,写完整咯
25 楼 night_stalker 2010-02-27  
参见 Pro Activerecord Database (2007) 102 页
现在已经有数十种 acts_as_nested_set 和 acts_as_tree 了 ……
24 楼 抛出异常的爱 2010-02-27  
fxyc 写道
我也用过,查询是很快,但是添加和删除就会变得有点复杂。

不如把数据全抓出来重作

相关推荐

    基于JAVA建立树形结构的算法优化.pdf

    在设计树形结构算法时,需要考虑如何高效地从原始数据中构建出所需的树形结构。算法设计的关键在于节点的查找和插入,尤其是如何高效地从上一级节点找到下一级的所有子节点。在树形结构中,每个节点可能包含多个子...

    Java递归算法构造JSON树形结构

    Java 递归算法构造 JSON 树形结构 Java 递归算法构造 JSON 树形结构是指通过 Java 语言使用递归算法将数据库中的菜单表构建成树形的 JSON 格式发送给第三方。这种方法可以将复杂的树形结构数据转换成易于理解和处理...

    树形结构设计总结java demo

    在实际应用中,树形结构常用于实现文件系统、数据库索引、图算法(如A*寻路)、表达式解析、编译器语法树等。例如,在设计一个组织结构管理系统时,每个节点可以代表一个员工,其子节点则表示其下属,这样就形成了一...

    java树形结构

    Java树形结构是一种数据结构,它模仿了自然界中的树状模型,由节点(或称为顶点)和边组成。在计算机科学中,每个节点可以有零个或多个子节点,而根节点没有父节点。这种结构广泛应用于各种编程场景,如文件系统、...

    java树节点逐级汇总.zip

    "java树节点逐级汇总.zip"这个压缩包提供的内容,旨在帮助开发者处理无序列表数据,并将其转化为可以逐级汇总的树形结构。下面将详细介绍这个过程中的关键知识点。 1. **树形结构**: - 树形结构是一种非线性的...

    树形结构算法

    ### 树形结构算法:非递归方法与JSTree应用 #### 引言 在IT行业,尤其是在软件开发和数据库管理领域,树形结构是一种常见的数据组织方式,用于表示层级关系的数据集。传统的树形结构操作往往依赖于递归算法,这在...

    树形结构(增删改查刷新等功能附SQL脚本)

    在IT领域,树形结构是一种常见的数据组织方式,它模拟了自然界中的树状层次关系,广泛应用于文件系统、数据库索引、计算机科学的算法设计等多个方面。在这个项目中,我们探讨的是如何在Java环境中,利用JSP(Java...

    Java创建树形结构算法实例代码

    总结起来,Java创建树形结构算法的核心在于使用数据结构(如List和Map)和适当的排序机制来构建层次关系。`MenuExt`类和`createTreeMenus()`方法的实现是这种思路的具体体现,它们能帮助开发者在JavaWeb应用中构建出...

    java数据结构排序算法之树形选择排序详解

    树形选择排序的算法过程可以分为三步:构建树形结构、比较和选择、排序输出。 首先,我们构建一个树形结构,每个叶子结点代表一个记录,非叶子结点代表一个比较结果。然后,我们从叶子结点开始,逐步比较和选择最小...

    Java数据结构和算法.pdf

    * 递归可以实现树形结构的遍历。 六、哈希表 * 哈希表是一种基于键值对的数据结构。 * 哈希表可以实现快速查找、插入、删除等操作。 七、高级排序 * 高级排序包括快速排序、归并排序、堆排序等。 * 快速排序是...

    基于JAVA建立树形结构的算法优化.zip

    在Java编程中,构建树形结构是一种常见的任务,特别是在数据结构和算法的设计中。树形结构是一种非线性数据结构,它由多个节点组成,每个节点可以有零个或多个子节点,这样的结构使得数据之间的关系更为清晰。本文将...

    Java数据结构和算法中文第二版

    5. **树(Tree)**:树形数据结构表示具有层次关系的数据集合,其中最常见的是二叉树。 6. **图(Graph)**:图是由顶点和边组成的非线性数据结构,用于表示对象之间的复杂关系。 7. **散列表(Hash Table)**:散列表通过...

    在java中 遍历mysql中的树形结构

    在Java中遍历MySQL数据库中的树形结构是一个复杂但重要的任务,涉及数据库设计、递归算法以及性能优化等多个方面。通过深入理解树形结构的特点,并采用合适的遍历算法和优化策略,可以有效地管理和操作复杂的层级...

    jpa单表递归树形结构实现

    在本示例中,我们将探讨如何使用Spring JPA来实现单表递归树形结构。 首先,我们需要理解递归树形结构。在数据库中,树形结构通常通过自关联来表示,即一个表的某个字段引用该表自身,形成一个层级关系。对于单表...

    java_树形结构文档

    在这个"java_树形结构文档"中,我们可能会深入探讨如何在Java中实现和操作树形结构。 树形结构由节点(或称为顶点)和边组成,其中每个节点可以有零个或多个子节点,这种关系形成了一种层次结构。在Java中,我们...

    使用递归算法结合数据库解析成Java树形结构的代码解析

    使用递归算法结合数据库解析成Java树形结构的代码解析是指通过递归算法解析数据库中的树形结构数据,并将其转换为Java树形结构的过程。 首先,需要准备好表结构及对应的表数据。在这个示例中,我们创建了一个名为TB...

    树形结构地址联动

    在编程中实现树形结构地址联动,可以使用各种编程语言,如JavaScript、Python、Java等,通常会用到数据结构库(如JavaScript的lodash.get和_.set,Python的jsonpath-ng等)来方便地操作和查询树形数据。 总的来说,...

    递归形成树形结构.txt

    java递归形成树形结构

    java数据结构与算法分析

    递归允许函数调用自身,常用于树形结构的遍历或解决复杂问题的简化。分治策略则是将大问题分解为小问题来解决,如快速排序和归并排序就是典型的分治算法。 在Java中,集合框架提供了丰富的数据结构实现,如...

    java基础数据结构算法总结 面试

    递归在处理树形结构和回溯问题时特别有用,例如汉诺塔问题。 汉诺塔问题是一个经典的递归问题,目标是将所有盘子从一根柱子移动到另一根柱子,同时遵循以下规则: 1. 每次只能移动一个盘子。 2. 不允许大盘子位于小...

Global site tag (gtag.js) - Google Analytics