這是很多初賽考的東西，雖然一般復(fù)賽不考，但為了初賽，我還是寫寫吧。
先給一張樹(shù)的圖：
很經(jīng)典的樹(shù)，一共六個(gè)結(jié)點(diǎn)，根是A。那我就照著這張圖，講講樹(shù)的遍歷。
壹、簡(jiǎn)介
一、先序遍歷，根在前，再是左子樹(shù)，再?gòu)淖蟮接乙活w顆子樹(shù)遍歷，即最后右子樹(shù)。
例：本圖中應(yīng)為ABDECF。
二、后序遍歷，先左子樹(shù)，從左至右，到右子樹(shù)后，再回到根。
例：本圖中應(yīng)為DEBFCA。
三、層次遍歷，一層一層來(lái)，從根，到根的兒子，到孫子……最后到葉子結(jié)點(diǎn)。
例：本圖中應(yīng)為ABCDEF。
四、葉結(jié)點(diǎn)遍歷，從左到右，依次訪問(wèn)葉子結(jié)點(diǎn)，不要考慮有兒子的結(jié)點(diǎn)。
例：本圖中應(yīng)為DEF。
貳、例子
為再鞏固下這些知識(shí)，同時(shí)避免出現(xiàn)誤區(qū)，我在給一張圖，寫寫他們的四個(gè)遍歷。
一、前序遍歷，應(yīng)為ABCEFDGHI。
二、后序遍歷，應(yīng)為EFCDBGIHA。
三、層次遍歷，應(yīng)為ABGHCDIEF。
四、葉結(jié)點(diǎn)遍歷，應(yīng)為EFDHI。
還算簡(jiǎn)單的，就這樣，多做就會(huì)。
叁、實(shí)現(xiàn)方法
一、前序和后續(xù)遍歷，用的是遞歸，即我們采用的DFS（深度優(yōu)先搜索），又叫搜索與回溯算法，因?yàn)槟阋祷刂粮Y(jié)點(diǎn)，再到下一個(gè)子結(jié)點(diǎn)。
這里主要用到的是父親孩子表示法。
二、層次遍歷，偏向于BFS（即廣度優(yōu)先搜索，又名寬度優(yōu)先搜索），可以用隊(duì)列實(shí)現(xiàn)，我具體就不細(xì)講了。見(jiàn)到一個(gè)結(jié)點(diǎn)，先收錄他的所有兒子，再收錄他的所有兄弟的兒子，以此類推……
這里主要用到的是孩子兄弟表示法。
三、葉結(jié)點(diǎn)遍歷，很少用，也沒(méi)有對(duì)應(yīng)的算法，莫非是……找個(gè)死胡同？
這里主要用到的是兒子表示法，找到?jīng)]兒子的那一個(gè)。
好勒，就這樣，明天日更，等你。
