经典算法之递归

以树这样一个经典的案例，通过递归算法，实现获取所有的树节点。

方法一：递归时，加入当前节点

	//获取所有的树节点
	public List<XxxTree> getAllNodes(){
		List<XxxTree> list = new ArrayList<XxxTree>();
		List<XxxTree> rootList = getChildNodesById(0L);//获取根节点列表
		for(XxxTree root : rootList){
			doBuild(root, list);
		}
		return list;
	}
	
	//根据树节点id获取其所有直接子节点
	private List<XxxTree> getChildNodesById(Long id){
		String hql = "SELECT t FROM XxxTree t where t.uplink = ? ";
		return xxxDao.find(hql, new Object[]{id});
	}
	
	//递归获取：该节点以及该节点以下的所有的子节点
	private void doBuild(XxxTree obj, List<XxxTree> list){
		list.add(obj); //加入当前节点 
		List<XxxTree> childList = getChildNodesById(obj.getIdx());
		if(childList!=null && childList.size()>0){
			for(XxxTree child : childList){
				doBuild(child, list);
			}
		}
	}

方法二：递归时，加入当前节点的子节点列表

	//获取所有的树节点
	public List<XxxTree> getAllNodes(){
		List<XxxTree> list = new ArrayList<XxxTree>();
		List<XxxTree> rootList = getChildNodesById(0L);//获取根节点列表
		list.addAll(rootList);
		for(XxxTree root : rootList){
			doBuild(root, list);
		}
		return list;
	}
	
	//根据树节点id获取其所有直接子节点
	private List<XxxTree> getChildNodesById(Long id){
		String hql = "SELECT t FROM XxxTree t where t.uplink = ? ";
		return xxxDao.find(hql, new Object[]{id});
	}
	
	//递归获取：该节点以下的所有的子节点
	private void doBuild(XxxTree obj, List<XxxTree> list){
		List<XxxTree> childList = getChildNodesById(obj.getIdx());
		if(childList!=null && childList.size()>0){
			list.addAll(childList);//加入当前节点的子节点列表
			for(XxxTree child : childList){
				doBuild(child, list);
			}
		}
	}

上面两种方法实现递归的模拟实现，见附件，可以直接运行！

附：
oracle中connect by prior递归算法，例如：
SELECT * FROM tree START WITH idx = 123 CONNECT BY PRIOR idx = uplink
查询：idx为123的节点 以及该节点下面的所有子节点（递归）
http://www.cnblogs.com/chen1388/archive/2010/09/25/1834827.html