java树形结构 算法

最近看到一个有意思的树形结构，为每个节点添加了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-->

很好，很强大，以前没想过还可以这样，谢谢啦，收下

恕我愚昧 请问lft和rgt两个属性分别记录的是？

还有一个问题：你的id是自增长编号么？
如何保证，between lft 和 rgt 不会包含兄弟的子节点啊？

          1
      /    \
     2      3
    / \    /
   4   5  6 
  /
7

2节点的lft和rgt分别是？

http://intelligent-enterprise.informationweek.com/001020/celko.jhtml;jsessionid=D4NGPOGZWDQZPQE1GHPSKH4ATMY32JVN?_requestid=402826

牛叉树...就是加 减 节点时有点柴废

在项目中并没有什么实际的意义。只是作为一个标识来方便我们查找。

呵呵。。欢迎多多指教。

这个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

http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

这种算法的英文版，上面图画的挺清楚，可以参考一下。

看起来好像很不错，还没细细研究，我想问问：根据你的说明 lft 和 rgt 只是方便我们解决递归查找性能问题的2个属性，那它到底记录什么？当我增加一个节点，它们的值分别怎么赋值？从根节点开始说吧 ，我比较笨，呵呵，谢谢。