【DRP】树形结构操作之递归删除

叁歲伎倆 2022-08-27 14:43 169阅读 0赞

如图所示呈现了一颗树形结构。本文从删除树形结构的任意结点出发，提供了一种解决思路

> > ![SouthEast][]

图中，不包含其它结点的是叶子结点。包含其他结点的是父结点，即不是叶子结点。

一 本文的知识点：

**（1）递归调用：**

因为待删除的结点的层次是不确定的，如果是叶子结点则可以直接获取id直接删除，如：北京中医医院、华北区。如果待删除的结点是父结点，则需要继续向下查询，依次遍历出其子结点，从下往上依次删除，如‘华北区’。因此我们使用递归调用。

**（2）保证事务的原子性**

假设待删除的结点是‘华北区’，则相当于删除了3条信息（华北区、北京市、北京中医医院），通常认为同时删除多条数据，是具有原子性的。删除100条信息，相当于一个事务。要么一起删除，要么都不删除。

事务控制，表现为两方面：一个是递归删除过程中采用一个Connection（同时防止递归中循环调用导致Connection效率不高）；另一个是设置手动提交。

**（3）异常是throws ？还是catch？**

主方法delClientOrRegion为public 采用try…catch……finally打印堆栈中的错误信息；主方法中调用的方法，如：recursionDelNode、getChildren、modifyIsLeafField，均为private仅供方法内部调用，同时采用throws SQLException抛出异常，而不是catch捕捉异常。

这是因为假设getChildren内部catch了错误，打印了堆栈信息，那么上面一层不知道它出错的话，因此就不会事务回滚。因此建议内部抛出异常throws SQLException，外部使用捕获异常try catch

**（4）树的几种设计方式**

1）不带冗余字段，id主键，pid父结点主键

2）带冗余字段，id、pid、isleaf是否为叶子、childrencount孩子结点的数目

3）采用固定的字符串00010010001

00所有分销商

01华北区

001北京市

0001北京中医医院

（本数据库设计采用：id主键、pid父结点主键、is\_leaf是否为叶子结点）

> ![SouthEast 1][]

**（5）业务逻辑解析,假设待删除结点为‘北京市’**

1)保存父结点对象。即：获取‘北京市’的父结点‘华北区’的id。

2）递归删除树结点。即：删除‘北京市’同时还要删除其孩子结点‘北京中医医院’。删除的顺序也是有要求的，先删除孩子，后删除父亲。即先删除‘北京中医医院’，后删除‘北京市’，这一点在递归代码中有所体现。

3）如果父结点下没有子结点，则修改为叶子结点。即：如果‘华北区’没有孩子，则需要设置‘华北区’为叶子结点。

**二 部分代码如下：**

package com.bjpowernode.drp.basedata.manager;
    
    import java.sql.Connection;
    import java.sql.PreparedStatement;
    import java.sql.ResultSet;
    import java.sql.SQLException;
    
    import com.bjpowernode.drp.basedata.domain.AimClient;
    import com.bjpowernode.drp.basedata.domain.Client;
    import com.bjpowernode.drp.util.Constants;
    import com.bjpowernode.drp.util.DbUtil;
    import com.bjpowernode.drp.util.IdGenerator;
    import com.bjpowernode.drp.util.PageModel;
    import com.bjpowernode.drp.util.datadict.domain.ClientLevel;
    
    /**
     * 采用单例实现
     * @author Administrator
     *
     */
    public class ClientManager {
    
    	private static ClientManager instance = new ClientManager();
    	
    	private ClientManager() {}
    	
    	public static ClientManager getInstance() {
    		return instance;
    	}
    
    		/**
    	 * 删除分销商或区域
    	 * @param id
    	 */
    	public void delClientOrRegion(int id) {
    		Connection conn = null;
    		try {
    			conn = DbUtil.getConnection();
    			//手动控制事务的开启
    			DbUtil.beginTransaction(conn);
    			
    			//保存父节点对象
    			Client currentNode = findClientOrRegionById(id);
    			
    			//递归删除树节点
    			recursionDelNode(conn, id);
    			
    			//如果父节点下没有子节点
    			if (getChildren(conn, currentNode.getPid()) == 0) {
    				//修改为叶子
    				modifyIsLeafField(conn, currentNode.getPid(), Constants.YES);
    			}
    			//提交事务
    			DbUtil.commitTransaction(conn);
    		}catch(Exception e) {
    			//如果出错则打印堆栈信息
    			e.printStackTrace();
    			//事务回滚
    			DbUtil.rollbackTransaction(conn);
    		}finally {
    			//事务重置
    			DbUtil.resetConnection(conn);
    			//关闭数据库连接
    			DbUtil.close(conn);
    		}
    	}
    	/**
    	 * 递归删除
    	 * @param conn
    	 * @param id
    	 */
    	private void recursionDelNode(Connection conn, int id) 
    	throws SQLException {
    		//根据
    		String sql = "select * from t_client where pid=?";
    		PreparedStatement pstmt = null;
    		ResultSet rs = null;
    		try {
    			conn = DbUtil.getConnection();
    			pstmt = conn.prepareStatement(sql);
    			pstmt.setInt(1, id);
    			rs = pstmt.executeQuery();
    			while (rs.next()) {
    				//如果是不叶子节点，则递归调用
    				if (Constants.NO.equals(rs.getString("is_leaf"))) {
    					recursionDelNode(conn, rs.getInt("id"));
    				}
    				//如果是叶子节点，则直接删除
    				delNode(conn, rs.getInt("id"));
    			}
    			//删除自身
    			delNode(conn, id);
    		}finally {
    			DbUtil.close(rs);
    			DbUtil.close(pstmt);
    		} 	
    	}
    		/**
    	 * 取得指定节点的孩子数目
    	 * @param conn
    	 * @param id
    	 * @return
    	 */
    	private int getChildren(Connection conn, int id) 
    	throws SQLException {
    		//sql语句通过孩子pid的个数，判断是否为叶子节点
    		String sql = "select count(*) as c from t_client where pid=?";
    		PreparedStatement pstmt = null;
    		ResultSet rs = null;
    		int count = 0; 
    		try {
    			conn = DbUtil.getConnection();
    			pstmt = conn.prepareStatement(sql);
    			pstmt.setInt(1, id);
    			rs = pstmt.executeQuery();
    			rs.next();
    			count = rs.getInt("c");
    		}finally {
    			DbUtil.close(rs);
    			DbUtil.close(pstmt);
    		} 
    		return count;
    	}
    		/**
    	 * 修改isLeaf字段
    	 * @param conn
    	 * @param id 
    	 * @param leaf Y/N
    	 */
    	private void modifyIsLeafField(Connection conn, int id, String leaf)
    	throws SQLException {
    		//如果待删除的节点的父节点没有其他孩子节点，则设置为叶子状态
    		String sql = "update t_client set is_leaf=? where id=?";
    		PreparedStatement pstmt = null;
    		try {
    			conn = DbUtil.getConnection();
    			pstmt = conn.prepareStatement(sql);
    			pstmt.setString(1, leaf);
    			pstmt.setInt(2, id);
    			pstmt.executeUpdate();
    		} finally {
    			DbUtil.close(pstmt);	
    		}
    	}
    }

[SouthEast]: /images/20220823/ff4ba605b1924e5e93f9e418d83b2b9d.png
[SouthEast 1]: /images/20220823/ec6ed9893ff24217a004696fa23515f2.png