點(diǎn)擊查看：2015年計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)復(fù)習(xí)知識(shí)點(diǎn)匯總
二叉樹(shù)的遍歷
二叉樹(shù)的遍歷即是不重復(fù)地訪問(wèn)二叉樹(shù)的所有結(jié)點(diǎn)。
在遍歷二叉樹(shù)時(shí)，一般先遍歷左子樹(shù)，然后再遍歷右子樹(shù)。在先左后右的原則下，二叉樹(shù)的遍歷又可分為三種：前序遍歷、中序遍歷和后序遍歷。
1)前序遍歷
前序遍歷即先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。在遍歷左子樹(shù)和遍歷右子樹(shù)時(shí)，依然是先遍歷根結(jié)點(diǎn)，然后是左子樹(shù)，再是右子樹(shù)。
操作的具體方式：
若二叉樹(shù)為空，則結(jié)束返回。
否則：訪問(wèn)根結(jié)點(diǎn)前序遍歷左子樹(shù)前序遍歷右子樹(shù)
如上圖所示的完全二叉樹(shù)，它的前序遍歷結(jié)果是：A、B、D、H、P、Q、I、R、E、J、K、C、F、L、M、G、N、O
2)中序遍歷
中序遍歷，即先遍歷左子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)，最后是遍歷右子樹(shù)。
具體的操作方式：
若二叉樹(shù)為空，則結(jié)束返回。
否則：中序遍歷左子樹(shù)訪問(wèn)根結(jié)點(diǎn) 中序遍歷右子樹(shù)
這里強(qiáng)調(diào)，在遍歷左子樹(shù)和右子樹(shù)時(shí)，仍然要采用中序遍歷的方法。
如上圖所示的完全二叉樹(shù)，它的中序遍歷結(jié)果是：P、H、Q、D、R、I、B、J、E、K、A、L、F、M、C、N、G、O
3)后序遍歷
后序遍歷，即選遍歷左子樹(shù)，然后是遍歷右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。
具體的操作方式：
若二叉樹(shù)為空，則結(jié)束返回。
否則：前序遍歷左子樹(shù)前序遍歷右子樹(shù)訪問(wèn)根結(jié)點(diǎn)
如上圖所示的完全二叉樹(shù)，它的后序遍歷結(jié)果是：P、Q、H、R、I、D、J、K、E、B、L、M、F、N、O、G、C、A
相關(guān)推薦：
2015計(jì)算機(jī)二級(jí)公共基礎(chǔ)知識(shí)精選選擇題專(zhuān)項(xiàng)練習(xí)
| 北京 | 天津 | 上海 | 江蘇 | 山東 |
| 安徽 | 浙江 | 江西 | 福建 | 深圳 |
| 廣東 | 河北 | 湖南 | 廣西 | 河南 |
| 海南 | 湖北 | 四川 | 重慶 | 云南 |
| 貴州 | 西藏 | 新疆 | 陜西 | 山西 |
| 寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
| 黑龍江 | 內(nèi)蒙古 |
