同一棵樹要把每個節點都經過一次其實不難,難的是決定「先走誰、後走誰」——順序不同,用途也天差地別。 想像你要清點一棟大樓的每個房間:可以一路往深處鑽到底、走完再回頭,也可以一層一層由上往下、由左到右挨個看。 換個走法,同一棵樹就走出完全不同的節點順序——有的剛好把數字由小排到大,有的方便你先算完子項再回頭處理自己。 下面四個面板會用同一棵樹,讓你同步比對四種遍歷順序各自走出什麼路線。
「遍歷」就是把樹上每個節點都走過一遍,差別在走的順序。前序先看自己再看左右子樹(適合複製整棵樹); 中序先左、再自己、再右(在二元搜尋樹會剛好由小到大排序);後序先看完左右子樹才處理自己(適合算資料夾總大小這種要先知道子項的情況); 層序則一層一層由上往下、由左到右走。你可以同步看四種順序分別以什麼路線走過同一棵樹。