最近在看《資料結構與演算法：Python語言描述》這本書，其中關於二叉樹的實現很不錯，於是在這裡記錄一下，權當筆記了。

二叉樹節點類：

python實現二叉樹的可以用list或者tuple。這裡用list實現。

二叉樹有節點組成，所以先實現節點類：

基於此類的物件構造的二叉樹具有遞迴結構，很容易使用遞迴的處理方式。比如：

到此我們可以來看二叉樹的遍歷演算法了

遞迴定義的遍歷函式

先根序列的遍歷函式：

中序後序於此類似，讀者可以自己完成。

廣度優先遍歷

要實現廣度優先遍歷，需要一個佇列來儲存節點，這裡使用了SQueue類(在文末會給出實現)：

非遞迴先根序列遍歷函式

採取先根序，遇到節點訪問，下一步沿著樹的左分支下行節點的右分支還沒有訪問，右子節點入棧遇到None 回溯，彈出棧中儲存的右分支，像一顆二叉樹一樣遍歷它需要用到SStack類(同樣在文末給出，只要知道它實現了常見棧操作即可)

非遞迴的後跟遍歷函式

後跟遍歷有寫難寫，在此種遍歷中，每個根結點都要經過三次，變數 t 是當前節點。在實現遍歷的迴圈中維持一種不變關係：

棧中節點序列的左邊是二叉樹的已遍歷過的部分，右邊尚未遍歷。如果 t 不空，父節點就是棧頂節點。t 空時棧頂就是應該訪問的節點。

前面構造了二叉樹的節點類，其實還可以構造一個二叉樹類把節點包括進去，能更加的方便操作，這點就留給讀者自己擴充套件了。