java树遍历-递归与非递归（深度优先和广度优先）

之前写过一个java树迭代的笔记。是将线性结构数据(List)转化为树型结构数据《java 树迭代-反向迭代》。现在记录一个与之对应的一个逆向过程：

已有的一棵树型结构数据，如何遍历它，获取并操作里面的每一个节点。

一般存在两种方法：递归与非递归。而每种方法都有两种策略：深度优先和广度优先。这四个概念都很好理解，为了节省篇幅，这里主要用java伪代码描述一下。

非递归 广度优先

TreeNode parent; // 顶层节点
List<TreeNode> childs = getChilds(parent);
while(childs != null && childs.size() > 0) {
  List<TreeNode> oneTempChilds,
                 allTempChilds = new ArrayList<>();;
  for (child: childs) {
    // ------------------------------------
    // do what you want to child
    // ------------------------------------
    oneTempChilds = getChilds(child);
    if (oneTempChilds  != null && oneTempChilds.size() > 0) {
      tempChilds.add(oneTempChilds); // 这里应该添加的是当前child的子节点，而非child，child已经touch到了
    }
  }
  childs = tempChilds;
}

// 传入一个节点，返回其所有子节点
private List<TreeNode> getChilds(TreeNode parent) {
  // todo ...
}

递归 广度优先

TreeNode parent; //顶层节点
List<TreeNode> childs = getChilds(parent);
recursive(childs); // 调用

public void recursive(List<TreeNode> childs) {
  List<TreeNode> oneTempChilds,
                 allTempChilds = new ArrayList<>();
  for (child: childs) {
    // ------------------------------------
    // do what you want to child
    // ------------------------------------
    oneTempChilds = getChilds(child);
    if (oneTempChilds != null && oneTempChilds.size() > 0) {
      allTempChilds.add(oneTempChilds);
    }
  }
  if (allTempChilds != null && allTempChilds.size() > 0)  {
    recursive(allTempChilds); // 递归调用
  }
}

// 传入一个节点，返回其所有子节点
private List<TreeNode> getChilds(TreeNode parent) {
  // todo ...
}

递归 深度优先

TreeNode parent; //顶层节点
recursive(parent); // 调用

public void recursive(TreeNode parent) {
  List<TreeNode> childs = getChilds(parent);
  if (childs != null) {
    for (child: childs) {
      // ------------------------------------
      // do what you want to child
      // ------------------------------------
      recursive(child); // 递归调用
    }
  }
}

// 传入一个节点，返回其所有子节点
private List<TreeNode> getChilds(TreeNode parent) {
  // todo ...
}

非递归 深度优先

非递归深度优先的实现与上面三个有所不同，想了很久觉得仍无法实现，查询知网，找到了一篇相关文献（《深度优先搜索的非递归算法》）以供参考。