分别采用深度和广度遍历数据库中邻接表中存储的树形结构的数据

╰半夏微凉° 2022-06-17 02:11 104阅读 0赞

1. 概述

我们在开发项目的时候，经常需要把具有层次结构的数据使用树结构进行展示，这样直观明了。这样就需要将树进行遍历，树的遍历有深度遍历和广度(层次)遍历。我们在实际的项目中还遇到将邻接表中的数据用树状进行展示，或将树状的记录固定地在有限的层级里面展示。当然这个也可以使用数据库进行展示邻接表的树状(start whit ..connect by prio ...)。

2. 实现使用到的技术

1) 邻接表：表中有ID字段和存储上一节点的主键的PID字段；

2) 使用Spring.jar中的JdbcTemplate进行操作数据库；

3) 使用堆栈和队列数据结构，以及递归技术。

3. 详细实例

package com.lanp.tree;
    
    import java.math.BigDecimal;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Map;
    import java.util.Stack;
    
    import org.springframework.jdbc.core.support.JdbcDaoSupport;
    
    /**
     * 分别采用深度和广度遍历数据库中邻接表中存储的树形结构的数据
     * @author LanP
     * @since 2011-11-26 22:00
     * @version V1.0
     */
    public class ShowTreeInfo extends JdbcDaoSupport{
    	private int countInt = 0;
    	/**
    	 * 存放遍历树状结构中每层的数据集
    	 */
    	private List<Map<String,Object>> lstInfo;
    	/**
    	 * 深度遍历树结构时使用的堆栈
    	 */
    	private Stack<Map<String,Object>> nodes = new Stack<Map<String,Object>>();
    	/**
    	 * 广度(层次)遍历树状结构时使用的队列
    	 */
    	private List<Map<String,Object>> quNodes = new ArrayList<Map<String,Object>>();
    	/**
    	 * 组织机构的SQL语句，遍历时使用
    	 */
    	private String orgSql = "select dept_id,dept_code,dept_name,parentid from t_dept_info where parentid=?";
    	/**
    	 * 存放广度(层次)遍历好的数据集
    	 */
    	private List<Map<String,Object>> allNodes = new ArrayList<Map<String,Object>>();
    	/**
    	 * 获取节点路径的SQL语句
    	 */
    	private String sql = "select dept_id,dept_code,dept_name,parentid from t_dept_info where dept_id=?";
    	
    	/**
    	 * 执行数据库，根据父节点遍历树
    	 * @param BigDecimal pId
    	 * @return List<Map<String,Object>>
    	 */
    	@SuppressWarnings("unchecked")
    	public List<Map<String,Object>> getMstMateInfoByPrId(BigDecimal pId) {
    		return getJdbcTemplate().queryForList(orgSql, new Object[]{pId});
    	}
    	
    	/**
    	 * 使用堆栈深度遍历树
    	 * @param BigDecimal pId
    	 */
    	private void recursionGetMateInfo(BigDecimal pId) {
    		lstInfo = getMstMateInfoByPrId(pId);
    		if(null != lstInfo && lstInfo.size()>0) {
    			for(int i=0; i<lstInfo.size(); i++) {
    				nodes.push(lstInfo.get(i));
    				while(!nodes.empty()) {
    					Map<String,Object> nodesBuf = nodes.pop();
    					System.out.println("=== " + nodesBuf + " === " + (++countInt));
    					List<Map<String,Object>> lstInfoBuf = getMstMateInfoByPrId(new BigDecimal(nodesBuf.get("dept_id").toString()));
    					if(null != lstInfoBuf && lstInfoBuf.size()>0) {
    						for(int j=0; j<lstInfoBuf.size(); j++) {
    							nodes.push(lstInfoBuf.get(j));
    						}
    					}
    				}
    			}
    		}
    	}
    	
    	/**
    	 * 使用队列广度(层次)遍历树
    	 * @param BigDecimal pId
    	 */
    	private void levelLstMateInfo(BigDecimal pId) {
    		lstInfo = getMstMateInfoByPrId(pId);
    		if(null != lstInfo && lstInfo.size()>0) {
    			for(int i=0; i<lstInfo.size(); i++) {
    				quNodes.add(lstInfo.get(i));
    				while(null != quNodes && quNodes.size()>0) {
    					Map<String,Object> nodesBuf = quNodes.get(0);
    					allNodes.add(nodesBuf);
    //					System.out.println("=== 节点信息： " + nodesBuf);
    					quNodes.remove(0);
    					List<Map<String,Object>> lstInfoBuf = getMstMateInfoByPrId(new BigDecimal(nodesBuf.get("dept_id").toString()));
    					if(null != lstInfoBuf && lstInfoBuf.size()>0) {
    						for(int j=0; j<lstInfoBuf.size(); j++) {
    							quNodes.add(lstInfoBuf.get(j));
    						}
    					}
    				}
    			}
    		}
    	}
    	
    	/**
    	 * 执行数据库，获取节点路径
    	 * @param BigDecimal pId
    	 * @return List<Map<String,Object>>
    	 */
    	@SuppressWarnings("unchecked")
    	private List<Map<String,Object>> getPathInfo(BigDecimal pId) {
    		return getJdbcTemplate().queryForList(sql, new Object[]{pId});
    	}
    	
    	/**
    	 * 获取节点所在的路径,使用递归
    	 * @param BigDecimal pId
    	 * @param String name
    	 * @return String
    	 */
    	private String getNodePath(BigDecimal pid,String name) {
    		String path = "";
    		List<Map<String,Object>> resultList = getPathInfo(pid);
    		if(null != resultList && resultList.size()>0) {
    			path = getNodePath(new BigDecimal(resultList.get(0).get("parentid").toString()),resultList.get(0).get("dept_name").toString()) + "," + name;
    		} else {
    			path = name;
    		}
    		return path;
    	}
    	
    	/**
    	 * 根据节点的路径，获取节点的所在的层次和直接父节点
    	 * @param String pathStr
    	 * @return String[]
    	 */
    	private String[] getNodeParentInfo(String pathStr) {
    		String[] resultList = new String[2];
    		if(null != pathStr && !"".equals(pathStr)) {
    			String[] paths = pathStr.split(",");
    			int level = paths.length;
    			resultList[0] = level + "";
    			if(level > 1) {
    				resultList[1] = paths[level - 2];
    			} else {
    				resultList[1] = "0";
    			}
    		}
    		return resultList;
    	}
    	
    	/**
    	 * 主调方法
    	 */
    	public void showTreeNodesInfo() {
    		//深度遍历树
    //		recursionGetMateInfo(new BigDecimal(0));
    		//广度遍历树
    		levelLstMateInfo(new BigDecimal(0));
    		
    		//封装节点，节点信息、所在层次和直接节点
    		if(null != allNodes && allNodes.size()>0) {	//为了方便就直接该变量中的数据，其实就使用select dept_id,dept_code,dept_name,parentid from t_dept_info中的记录就可以 
    			for(int i=0; i<allNodes.size(); i++) {
    				Map<String,Object> nodesBuf = allNodes.get(i);
    				String pathStr = getNodePath(new BigDecimal(nodesBuf.get("parentid").toString()),nodesBuf.get("dept_name").toString());
    //				System.out.println("节点信息：" + nodesBuf + " == 节点路径：" + pathStr);
    				//获取节点所在的层级及直接父节点
    				String[] parent = getNodeParentInfo(pathStr);
    				//重新封装一个节点的完整信息,添加了节点所在的层级和直接父节点
    				Map<String,Object> nodeInfo = nodesBuf;
    				nodeInfo.put("LEVEL", parent[0]);
    				nodeInfo.put("PARENT", parent[1]);
    				System.out.println("=== 节点的完整信息为：" + nodeInfo + " ===");
    			}
    		}
    	}
    	
    }

TKS!