二叉樹的遍歷是一個數據結構中經常會遇到的知識點, 具體又分為前序, 中序和后序三種.

什么是樹?

先來理解一下什么是樹, 從一個我們相對熟悉的家譜樹(Family Tree)說起吧.

家族的根是爺爺, 然后生了兩個娃, 大伯和你爸爸. 繼續往下, 有堂哥堂姐, 還有你以及你妹, 等等.

一個家族繁衍下來, 很像一棵樹開枝散葉, 當然跟真的樹相比, 畫出來時通常是倒過來的, 根在上面.

二叉樹 VS 多叉樹

明白了什么是樹, 那什么又是二叉樹呢?

首先這里每個人稱為樹的一個節點. 而每個節點下面呢? 可以看到最多只有兩個節點.

可能養三個娃太費勁了, 或者計劃生育, 頂多兩個葫蘆娃, 超生了就罰款, 當然現在應該不會了.

一個節點, 在它之下的節點, 多則兩個,少則一個甚至沒有, 這就是二叉樹.

而如果像下邊這樣, 大伯之后還有個二伯, 你爸是老三, 那這就不算了.

所以前面的圖是二叉樹, 后面的的則不是.

二叉樹的節點(Node)

再來看二叉樹的幾種節點.

首先爺爺這里叫做 根節點, 老祖宗.

給他一個綠色, 不是帽子啊. 只是為了區分.

然后一個節點下面不是頂多兩個節點嘛, 那左邊這個呢就叫 左節點, 標成紅色.

這里像大伯, 堂哥, 你還有外甥, 不管處在哪個層級或者說輩分也好, 只要在左邊的就是左節點.

那其余的自然就是 右節點 了. 用藍色表示.

二叉樹的子樹(subtree)

了解了左右節點后, 再來看一個子樹的概念.

根節點左邊這一支呢, 也就是你大伯一家子, 與節點類似, 就叫 左子樹, 還是用紅色表示.

右邊的自然就是 右子樹 了, 也就是你爸爸這一家子.

二叉樹的遍歷(traversal)

有了以上概念后, 再來看遍歷. 那什么是遍歷呢?

假設來說吧, 有一天你變得很出名, 然后有個好事的記者呢, 就想對你這整個家族的人, 都采訪一下, 挖點奇聞軼事或者你小時候的糗事出來.

這種把一個樹上全部節點都訪問一次的行為, 就是遍歷, 都歷經一遍.

既然都要訪問, 那現在的問題就是, 這里這么多人, 到底按什么順序去訪問.

對于二叉樹, 深度優先的遍歷有這么三種:

• 前序遍歷(preorder)
• 中序遍歷(inorder)
• 后序遍歷(postorder)

二叉樹的前序遍歷

先來看什么是前序遍歷.

它的大規則或者說大的方向是先訪問根節點, 然后是左子樹, 最后是右子樹. 簡稱 “根-左-右”.

先采訪爺爺. 然后是大伯一家子, 最后到你家.

當然這兩家子下面又還有很多人, 到底又先采訪誰的小規則我們晚點再說.

先說另一個問題, 不知道你想過沒有, 為什么大規則要這樣安排呢?

二叉樹遍歷的就近原則

這里介紹二叉樹遍歷的一個可以叫做就近的原則吧.

假設來說, 這是個地圖, 爺爺在江西, 然后子女通常圍繞父母就近開枝散葉, 比如大伯就去了臨近的廣東, 而你爸爸則到了旁邊的福建, 這是很自然的.

再往下呢, 也是類似的, 堂哥堂姐們就隨著大伯在廣東混了, 而你和你妹自然就在福建, 也是很合理的.

那回到記者采訪的問題上, 假如這個記者剛采訪完廣東的大伯, 又大老遠跑到福建去采訪你爸爸,
左右橫跳, 飛來飛去, 好不容易掙點稿費, 都交給鐵道部或者民航局了, 不劃算.

另外, 我們可能注意到一點, 大伯和你爸和爺爺之間都有一條線連接.

想象這是一棵樹, 而記者則是一只螞蟻, 他現在在大伯這個節點上, 他要去你爸那邊, 其實他要先沿著左邊的路爬回到爺爺這個根節點, 再順著右邊的樹枝才能爬到你爸的節點上.

大伯和你爸之間其實是沒有連線的. 如果有的話, 這就不是樹形結構而是圖形結構了.

左子樹的前序遍歷

明白了這個就近原則后, 我們繼續看這個左子樹里面的節點要按什么順序去訪問.

前面說了大規則是 根-左-右, 然后說子樹里面要確定一個小規則. 其實呢, 并不存在所謂的小規則.

當把左子樹單拎出來, 其實它還是一顆樹. 因此依然可以按照 “根-左-右” 的規則.

先訪問根節點, 大伯;

之后是左子樹, 堂哥一家子;

最后是右子樹, 堂姐, 或者說右節點, 目前就她一個, 可能還沒出嫁或者還沒生娃.

這里利用了子樹和整棵樹之間的一種自相似特性. 想象一下, 把一棵樹的一個樹枝掰斷了, 插在地上, 它看上去是不是就像一顆小樹?

兒子跟老子長得一樣, 這就是自相似. 因為存在這種相似性, 就可以重復使用同一個規則, 而不需要針對各個子部分又發明新的規則, 這就是遞歸處理.

左子樹的展開

那么將左子樹展開, 爺爺之后是大伯, 然后是堂哥一家, 這個需要繼續展開;

然后是堂姐, 最后到你家, 也是需要進一步展開.

左子樹的繼續展開

繼續展開堂哥一家, 依然是按照 “根-左-右” 的順序.

先是堂哥, 然后左子樹, 這個大侄子這里沒有, 可能因為他太調皮搗蛋了, 堂哥不要他, 讓別人抱養走了;

左子樹或者左節點沒有就跳過;

最后是右子樹, 你侄女, 或者說右節點, 小學剛畢業呢, 還沒到合法生娃的年紀, 下面沒人了, 所以展開到她這里也結束了.

左子樹的完全展開

這樣就完全確定了大伯一家子的采訪順序.

大伯之后是堂哥, 再之后是侄女, 最后是堂姐.

右子樹的展開

左子樹展開完了, 再看右子樹, 那就簡單了, 依然是按照 “根-左-右” 的順序,

先是爸爸這個根節點; 然后是左子樹, 或者說左節點, 也就是你, 光桿司令一個, 就不用繼續展開了; 最后是右子樹, 妹妹一家, 需要繼續展開.

右子樹的繼續展開

展開后就是這樣.

先是根節點爸爸, 其次是左節點你, 最后是右子樹, 妹妹一家.

右子樹的完全展開

最后妹妹一家再展開. 還是 “根-左-右” 的順序:

先是根節點, 妹妹; 再到左節點, 你外甥;

然后是右節點, 暫時沒有, 還沒懷上呢, 或者還沒生出來, 還在媽媽肚子里喝羊水呢, 那就也不用管它, 跳過就完了.

至此, 這一大家子人的采訪順序就全部確定了.

顯然, 無論這棵樹有多深, 哪怕向天再借500年, 家族不斷繁衍, 子又生孫孫又生子, 子又有子子又有孫, 子子孫孫祖宗十八代, 照樣可以按照這同一條規則去確定遍歷的順序.

前序遍歷的總結

最后, 對前序遍歷做個總結.

記住 “根-左-右” 這個順序. 先是爺爺這個根節點, 然后左子樹, 右子樹.

左子樹里面, 又繼續按照 “根-左-右” 的順序:

先是大伯這個根節點, 然后左子樹, 之后右節點堂姐.

再之后, 堂哥這里, 還是按照 “根-左-右” 的順序:

當然這時沒有左子樹, 那跳過就行了, 先是根節點, 然后右節點.

而右子樹呢, 也是按照 “根-左-右, 根-左-右” 的順序不斷遞歸展開, 最終得到了前序遍歷下, 所有節點的訪問順序.

二叉樹的中序遍歷

明白了前序遍歷后, 再來看中序遍歷, 就很容易理解了, 唯一的區別是訪問順序.

中序遍歷按照 “左-根-右” 的順序, 根節點在中間.

先是左子樹, 堂哥一家子這次排在了最前;

然后才到根節點, 爺爺這里, 處于中間;

最后才是右子樹, 也是你爸爸一家.

而每一個子部分呢, 遞歸地按照 “左-根-右” 的順序展開, 直到完全展開成我們看到的這個順序.

在這里, 像爺爺, 大伯, 爸爸這些根節點呢, 大概是處在中間, 或者是每個子部分的中間

那么這就是中序遍歷, 也叫中根遍歷, 根在中間.

二叉樹的后序遍歷

最后, 來看下后序遍歷, 同樣的道理, 只是順序變成了 “左-右-根”, 根在最后.

讀者可自己依葫蘆畫瓢, 嘗試一下展開.

最終結果就是這樣, 每一子部分都是按照"左-右-根"的順序不斷展開, 最終許多根節點是相對處在后面的.

讀者可以核對一下自己展開的結果是否正確. 如果有什么疑問, 可以對照著前面的前序和中序遍歷好好理解一下, 舉一反三, 因為道理都是類似的, 這里就不再展開那些細節了.

如果你得到了正確的訪問順序, 那可以說你已經正確地掌握了這三種遍歷形式.

二叉樹的遍歷總結

最后是對二叉樹這三種遍歷的一個總結.

• 前序, 又叫 前根遍歷, 按照 “根-左-右” 的順序遞歸展開;
• 中序, 又叫 中根遍歷, 按照 “左-根-右” 的順序遞歸展開;
• 后序, 又叫 后根遍歷, 按照 “左-右-根” 的順序遞歸展開;

所以, 主要區別就在根的位置上.

1. 首先, 前中后指的就是根的位置.
2. 其次, 左右子樹則始終是先左后右.
3. 最后, 遞歸應用以上規則直到子樹全部展開.

關于二叉樹的前序, 中序和后序這三種遍歷方式就講到這里, 謝謝大家.