java樹遍歷-遞歸與非遞歸(深度優(yōu)先和廣度優(yōu)先)

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

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末聋呢,一起剝皮案震驚了整個濱河市苗踪,隨后出現的幾起案子,更是在濱河造成了極大的恐慌削锰,老刑警劉巖通铲,帶你破解...
    沈念sama閱讀 222,729評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現場離奇詭異器贩,居然都是意外死亡颅夺,警方通過查閱死者的電腦和手機,發(fā)現死者居然都...
    沈念sama閱讀 95,226評論 3 399
  • 文/潘曉璐 我一進店門蛹稍,熙熙樓的掌柜王于貴愁眉苦臉地迎上來吧黄,“玉大人,你說我怎么就攤上這事唆姐∞挚” “怎么了?”我有些...
    開封第一講書人閱讀 169,461評論 0 362
  • 文/不壞的土叔 我叫張陵奉芦,是天一觀的道長赵抢。 經常有香客問我,道長仗阅,這世上最難降的妖魔是什么昌讲? 我笑而不...
    開封第一講書人閱讀 60,135評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮减噪,結果婚禮上,老公的妹妹穿的比我還像新娘车吹。我一直安慰自己筹裕,他們只是感情好,可當我...
    茶點故事閱讀 69,130評論 6 398
  • 文/花漫 我一把揭開白布窄驹。 她就那樣靜靜地躺著朝卒,像睡著了一般。 火紅的嫁衣襯著肌膚如雪乐埠。 梳的紋絲不亂的頭發(fā)上抗斤,一...
    開封第一講書人閱讀 52,736評論 1 312
  • 那天,我揣著相機與錄音丈咐,去河邊找鬼瑞眼。 笑死,一個胖子當著我的面吹牛棵逊,可吹牛的內容都是我干的伤疙。 我是一名探鬼主播,決...
    沈念sama閱讀 41,179評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼徒像!你這毒婦竟也來了黍特?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 40,124評論 0 277
  • 序言:老撾萬榮一對情侶失蹤锯蛀,失蹤者是張志新(化名)和其女友劉穎灭衷,沒想到半個月后,有當地人在樹林里發(fā)現了一具尸體旁涤,經...
    沈念sama閱讀 46,657評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡今布,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,723評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現自己被綠了拭抬。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片部默。...
    茶點故事閱讀 40,872評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖造虎,靈堂內的尸體忽然破棺而出傅蹂,到底是詐尸還是另有隱情,我是刑警寧澤算凿,帶...
    沈念sama閱讀 36,533評論 5 351
  • 正文 年R本政府宣布份蝴,位于F島的核電站,受9級特大地震影響氓轰,放射性物質發(fā)生泄漏婚夫。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,213評論 3 336
  • 文/蒙蒙 一署鸡、第九天 我趴在偏房一處隱蔽的房頂上張望案糙。 院中可真熱鬧,春花似錦靴庆、人聲如沸时捌。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽奢讨。三九已至,卻和暖如春焰薄,著一層夾襖步出監(jiān)牢的瞬間拿诸,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評論 1 274
  • 我被黑心中介騙來泰國打工塞茅, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留亩码,地道東北人。 一個月前我還...
    沈念sama閱讀 49,304評論 3 379
  • 正文 我出身青樓凡桥,卻偏偏與公主長得像蟀伸,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,876評論 2 361

推薦閱讀更多精彩內容

  • 1 序 2016年6月25日夜啊掏,帝都蠢络,天下著大雨,拖著行李箱和同學在校門口照了最后一張合照迟蜜,搬離寢室打車去了提前租...
    RichardJieChen閱讀 5,108評論 0 12
  • Android 自定義View的各種姿勢1 Activity的顯示之ViewRootImpl詳解 Activity...
    passiontim閱讀 172,328評論 25 707
  • 買車前需要了解哪些知識娜睛? 對汽車行業(yè)不是很了解的朋友髓霞,買車前需要注意或者知道哪些知識呢,對于一位不了解汽車的人來說...
    芒果青檸閱讀 350評論 0 0
  • 今天沒有想要開始的話題畦戒,就用一句我曾看到的話來濫竽充數方库、蒙混過關吧。 我們喜歡的障斋,要么錯過了纵潦,要么已經名花草有主了...
    _三公子_閱讀 167評論 0 0
  • 常在江湖走,哪能不動情垃环。 那時候邀层,我們之間就像在下一盤永無止盡的棋。 你欲拒還迎遂庄,我虛張聲勢寥院。 你戲謔挑弄,我假戲...
    洛小婭閱讀 379評論 0 2