二叉樹的四種遍歷方式

• 前序遍歷
• 中序遍歷
• 后序遍歷
• 層序遍歷

我們以二叉搜索樹 ——{7,4,9,2,5,8,11,3,12,1} 為例，分別分析這四種遍歷方式

前序遍歷

訪問順序：根節(jié)點(diǎn)、前序遍歷左子樹、前序遍歷右子樹 — （根節(jié)點(diǎn)訪問在前）

遍歷結(jié)果是：7、4、2、1、3、5、9、8、11、10、12

中序遍歷

訪問順序： — （根節(jié)點(diǎn)訪問在中）

1、中序遍歷左子樹、根節(jié)點(diǎn)、中序遍歷右子樹 （如果是二叉搜索樹，結(jié)果升序）

2、中序遍歷右子樹、根節(jié)點(diǎn)、中序遍歷左子樹 （如果是二叉搜索樹，結(jié)果降序）

遍歷結(jié)果是：1、2、3、4、5、7、8、9、10、11、12 （升序）

后序遍歷

訪問順序：后序遍歷左子樹、后序遍歷右子樹、根節(jié)點(diǎn) — （根節(jié)點(diǎn)訪問在后）

遍歷結(jié)果是：1、3、2、5、4、8、10、12、11、9、7

層序遍歷

訪問順序：從上到下、從左到右依次訪問每一個(gè)節(jié)點(diǎn)

遍歷結(jié)果是：7、4、9、2、5、8、11、1、3、10、12