Java实现树结构数据的递归与非递归遍历

Java实现树结构数据的递归与非递归遍历

​ 递归，是我们常用的一种方式。在使用的过程中，递归会不断的调用当前方法，以深度遍历方式沿着一条支路走到底，然后再回来执行下一条支路。种情况下在调用当前方法之后，编译器将这个方法的所有参数和返回地址压入栈中，在这种情况下当前线程若又去调用了一遍当前这个方法，而当这个支路又足够深，那么积攒起来的栈中内容就会越来越多，直到发生内存溢出。

​ 在一个项目中，有一个需求，需要根据表中人员的工号和上级工号，查询出这个人员的所有下属。代码如下：

public String getSubordinateEmp() {
        List<Entity> emps = dao.selectAllPerson();
        StringBuilder stringB = new StringBuilder();
        //递归
        String userId = UserLoginUtils.getUserLoginId();
        log.info("开始递归");
        StringBuilder empIds = empTree(emps,userId, flag,stringB);
        log.info("结束递归");
}
public StringBuilder empTree(List<Entity> emps, String empId, StringBuilder stringB) {
        for (Entity s : emps) {
            if (s.getSupervisorId() != null) {
                if (empId.equals(s.getSupervisorId()) && !s.getEmplid().equals(empId)) {
                    empTree(emps, s.getEmplid(), flag,stringB);
                    stringB.append( "," + s.getEmplid());
                }
            }
        }
        return stringB;
    }

这种做法看起来结构清晰，容易理解。但是当递归层数过多时，就发生了堆栈溢出。后来用while循环代替递归，代码改进如下：

public void TraverseTest(){
  long start = System.currentTimeMillis();
  //所有数据
  List<Entity> emps = dao.selectAllPerson();

  //要遍历的顶层
  String parent = "0";

  //获取parent的下属
  List<String> subordinateList = getSubordinate(emps, parent);
  StringBuilder sb = new StringBuilder();
  while (subordinateList.size() > 0 && !subordinateList.contains(parent)){
    List<String> temp = new ArrayList<>();
    for (String subordinate : subordinateList) {
      sb.append(",").append(subordinate);
      List<String> list = getSubordinate(emps, subordinate);
      if(list.size() > 0){
        temp.addAll(list);
      }
    }
    subordinateList = temp;
  }
  long end = System.currentTimeMillis();
  System.out.println("business used " + (end - start) + " ms");
  System.out.println(sb);
}

private List<String> getSubordinate(List<Entity> emps,String parent){
  List<String> subordinateList = new ArrayList<>();
  for (Entity emp : emps) {
    if(emp.getSupervisorId() != null){
      if (parent.equals(emp.getSupervisorId()) && !emp.getEmplid().equals(parent)) {
        subordinateList.add(emp.getEmplid());
      }
    }
  }
  return subordinateList;
}