一篇不錯的文章，收藏了，呵呵！
最近看到一個有意思的樹形結構，為每個節(jié)點添加了lft和rgt兩個屬性。這樣查找該節(jié)點的子節(jié)點、查找該節(jié)點所有父節(jié)點，就不用去遞歸查詢，只需要用between、and語句就可以實現。下面以創(chuàng)建一個欄目樹為例，以下是我的理解。
一般來講，我們創(chuàng)建欄目樹的時候，大多只需要一個外鍵parentid來區(qū)分該節(jié)點屬于哪個父節(jié)點。數據庫的設計如下圖：
這樣一來，
1.查找該節(jié)點的所有子節(jié)點，則需要采用sql的遞歸語句：
Sql代碼
select * from tableName connect by prior id=sj_parent_id start with id=1
select * from tableName connect by prior id=sj_parent_id start with id=1
(oracle 寫法，mysql目前不支持，如果mysql想查找樹形，可以利用存儲過程).
2.查找該節(jié)點的父節(jié)點的sql遞歸語句：
Sql代碼
select * from tableName connect by prior sj_parent_id =id start with id=1
select * from tableName connect by prior sj_parent_id =id start with id=1
如果數據量過大或者層次太多，那么這樣操作是會影響性能的。
“任何樹形結構都可以用二叉樹來表示”。其實我們創(chuàng)建的欄目樹就是一個簡型的二叉樹。根據數據結構里面二叉樹的遍歷，再稍微修改下，將數據庫設計如下圖所示：
這樣我們查找該節(jié)點的所有子節(jié)點，則只需要查找id在lft和rgt之間的所有節(jié)點即可。
1.查找該節(jié)點的所有子節(jié)點的Sql語句為：
<!--EndFragment-->
<!--EndFragment-->
Sql代碼
select * from tb_subject s,tb_subject t where s.lft between t.lft and t.rgt and t.id=1
select * from tb_subject s,tb_subject t where s.lft between t.lft and t.rgt and t.id=1
2.查找該節(jié)點的所有父節(jié)點的sql語句為：
<!--EndFragment-->
Sql代碼
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
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. 新增節(jié)點
新增節(jié)點比較簡單，基本步驟為
A． 查找當前插入節(jié)點的父節(jié)點的lft值
B． 將樹形中所有l(wèi)ft和rgt節(jié)點大于父節(jié)點左值的節(jié)點都+2
C． 將父節(jié)點左值+1，左值+2分別作為當前節(jié)點的lft和rgt
因為項目中采用的是struts2+hibernate3.2+spring2.5的框架，代碼如下：
<!--EndFragment-->
Java代碼
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);
//查找父節(jié)點的左值
if (parentId != null) {
String hql = "select b.lft from " + beanName
+ " b where b.id=:pid";
myPosition = (Integer) session.createQuery(hql).setLong("pid",
parentId).uniqueResult();
}
//將樹形結構中所有大于父節(jié)點左值的右節(jié)點+2
String hql1 = "update " + beanName
+ " b set b.rgt = b.rgt + 2 WHERE b.rgt > :myPosition";
//將樹形結構中所有大于父節(jié)點左值的左節(jié)點+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);
//定位自己的左值(父節(jié)點左值+1)和右值(父節(jié)點左值+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 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);
//查找父節(jié)點的左值
if (parentId != null) {
String hql = "select b.lft from " + beanName
+ " b where b.id=:pid";
myPosition = (Integer) session.createQuery(hql).setLong("pid",
parentId).uniqueResult();
}
//將樹形結構中所有大于父節(jié)點左值的右節(jié)點+2
String hql1 = "update " + beanName
+ " b set b.rgt = b.rgt + 2 WHERE b.rgt > :myPosition";
//將樹形結構中所有大于父節(jié)點左值的左節(jié)點+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);
//定位自己的左值(父節(jié)點左值+1)和右值(父節(jié)點左值+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;
}
?。? 修改節(jié)點
修改的時候比較麻煩，具體步驟為：
在修改lft和rgt之前，當前節(jié)點的父節(jié)點id已經改變
a. 查出當前節(jié)點的左右節(jié)點（nodelft、nodergt），并nodergt-nodelft+1 = span，獲取父節(jié)點的左節(jié)點parentlft
b. 將所有大于parentlft的lft(左節(jié)點)、rgt(右節(jié)點)的值+span
c. 查找當前節(jié)點的左右節(jié)點（nodelft、nodergt），并parentlft-nodelft+1 = offset
d. 將所有l(wèi)ft(左節(jié)點) between nodelft and nodergt的值+offset
e. 將所有大于nodergt的lft(左節(jié)點)、rgt(右節(jié)點)的值-span
Java代碼如下：
<!--EndFragment-->
Java代碼
public void updateParent(HibernateTree tree, HibernateTree preParent,
HibernateTree curParent) {
if (preParent != null && preParent != null
&& !preParent.equals(curParent)) {
String beanName = tree.getClass().getName();
// 獲得節(jié)點位置
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;
// 獲得當前父節(jié)點左位置
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 updateParent(HibernateTree tree, HibernateTree preParent,
HibernateTree curParent) {
if (preParent != null && preParent != null
&& !preParent.equals(curParent)) {
String beanName = tree.getClass().getName();
// 獲得節(jié)點位置
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;
// 獲得當前父節(jié)點左位置
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);
}
}
３. 刪除節(jié)點
刪除節(jié)點也比較簡單，具體步驟為：
A． 查找要刪除節(jié)點的lft值
B． 將所有l(wèi)ft和rgt大于刪除節(jié)點lft值的都-2
Java代碼如下：
<!--EndFragment-->
<!--EndFragment-->
Java代碼
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);
//查找要刪除的節(jié)點的左值
String hql = "select b.lft from " + beanName + " b where b.id=:id";
Integer myPosition = (Integer) session.createQuery(hql).setLong(
"id", tree.getId()).uniqueResult();
//將所有大于刪除節(jié)點左值的rgt都-2
String hql1 = "update " + beanName
+ " b set b.rgt = b.rgt - 2 WHERE b.rgt > :myPosition";
//將所有大于刪除節(jié)點左值的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);
}
}
