姓名：呂彬 學(xué)號：16130140354

【嵌牛導(dǎo)讀】最近學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)二叉樹部分，對其饒有興趣，我們一起來看下二叉樹的三種遍歷方式的遞歸算法。

【嵌牛鼻子】二叉樹是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的有序樹。通常子樹的根被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。二叉樹的每個(gè)結(jié)點(diǎn)至多只有二棵子樹(不存在度大于2的結(jié)點(diǎn))，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的 i -1次方個(gè)結(jié)點(diǎn)；深度為k的二叉樹至多有2^(k) -1個(gè)結(jié)點(diǎn)；對任何一棵二叉樹T，如果其終端結(jié)點(diǎn)數(shù)(即葉子結(jié)點(diǎn)數(shù))為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0 = n2 + 1。

【嵌牛提問】遞歸算法如何實(shí)現(xiàn)？

【嵌牛正文】二叉樹的遍歷：遍歷是對樹的一種最基本的運(yùn)算，所謂遍歷二叉樹，就是按一定的規(guī)則和順序走遍二叉樹的所有結(jié)點(diǎn)，使每一個(gè)結(jié)點(diǎn)都被訪問一次，而且只被訪問一次。由于二叉樹是非線性結(jié)構(gòu)，因此，樹的遍歷實(shí)質(zhì)上是將二叉樹的各個(gè)結(jié)點(diǎn)轉(zhuǎn)換成為一個(gè)線性序列來表示。

二叉樹的三種遞歸的遍歷方法：（源代碼截圖如下）

先序遍歷：

圖片發(fā)自簡書App

中序遍歷：

圖片發(fā)自簡書App

后序遍歷：

圖片發(fā)自簡書App