之前寫過一個java樹迭代的筆記爽丹。是將線性結構數據(List)轉化為樹型結構數據《java 樹迭代-反向迭代》。現在記錄一個與之對應的一個逆向過程：

已有的一棵樹型結構數據，如何遍歷它，獲取并操作里面的每一個節(jié)點麻汰。

一般存在兩種方法：遞歸與非遞歸。而每種方法都有兩種策略：深度優(yōu)先和廣度優(yōu)先戚篙。這四個概念都很好理解五鲫，為了節(jié)省篇幅，這里主要用java偽代碼描述一下已球。

非遞歸 廣度優(yōu)先

TreeNode parent; // 頂層節(jié)點
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的子節(jié)點臣镣，而非child，child已經touch到了
    }
  }
  childs = tempChilds;
}

// 傳入一個節(jié)點智亮，返回其所有子節(jié)點
private List<TreeNode> getChilds(TreeNode parent) {
  // todo ...
}

遞歸 廣度優(yōu)先

TreeNode parent; //頂層節(jié)點
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); // 遞歸調用
  }
}

// 傳入一個節(jié)點忆某，返回其所有子節(jié)點
private List<TreeNode> getChilds(TreeNode parent) {
  // todo ...
}

遞歸 深度優(yōu)先

TreeNode parent; //頂層節(jié)點
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); // 遞歸調用
    }
  }
}

// 傳入一個節(jié)點，返回其所有子節(jié)點
private List<TreeNode> getChilds(TreeNode parent) {
  // todo ...
}

非遞歸 深度優(yōu)先

非遞歸深度優(yōu)先的實現與上面三個有所不同阔蛉，想了很久覺得仍無法實現弃舒，查詢知網，找到了一篇相關文獻（《深度優(yōu)先搜索的非遞歸算法》）以供參考。