之前寫過一個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)先搜索的非遞歸算法》)以供參考。