二叉樹的遍歷

一. preorder——先序遍歷VLR

1. 遞歸先序遍歷

2. 迭代先序遍歷


3.先序遍歷圖解

二. inorder——先序遍歷LVR

1. 遞歸中序遍歷

2.迭代中序遍歷

3.迭代中序遍歷優化空間復雜度
<1>定義直接后繼

<2>借用直接后繼優化算法
解釋：
① backtrack相當于將原輔助棧換成一個標志位。
② 每當抵達一個節點，借助該標志即可判斷此前是否剛做過一次自下而上的回溯。若不是，則按照中序遍歷的策略優先遍歷左子樹。反之，若剛發生過一次回溯，則意味著當前節點的左子樹已經遍歷完畢（或等效地，左子樹為空），于是便可訪問當前節點，然后再深入其右子樹遍歷。
③ 每個節點被訪問之后，都應轉向其在遍歷序列中的直接后繼。
④ 檢查右子樹是否為空判斷后繼位置：如果非空則后繼在右子樹，否則后繼為某一祖先（回溯）。

4.迭代中序遍歷進一步優化

5.中序遍歷圖解

三. postorder——后序遍歷LRV

1. 遞歸后序遍歷

2.迭代后序遍歷
將樹T畫在二維平面上，并假設所有節點和邊均不透明。于是從左側水平向右看去，未被遮擋的最高葉節點v——稱作最高左側可見葉節點（HLVFL）——即為后序遍歷首先訪問的節點
下面的代碼尋找最高左側可見葉節點


后序遍歷步驟：
① 訪問當前節點。 ② 遍歷以其右兄弟（若存在）為根的子樹。③ 向上回溯至其
父節點（若存在）并轉入下一片段

3.后序遍歷圖解

四.levelorder——層次遍歷

1. 算法實現

2. 層次遍歷圖解

總結

二叉樹遍歷用到了棧（stack）和隊列（quene）這兩個數據結構使得代碼優化（從遞歸到迭代的空間優化）
這幾天看了二叉樹，感覺迷迷糊糊（差的還很遠），暫且能把代碼看明白（讓我寫感覺差的太遠了）而且已經開學了只能抽時間看看這些東西，所以趕快把一些自己感覺有用的東西記下來方便以后復習，同時也供大家一起學習（如果有錯誤麻煩指出來共同進步）。以上代碼全是圖片（自己本來想這照著寫一遍，發現還是有點難度，所以先記下來以后抽空寫一下）圖片全部來源于鄧俊輝老師的《數據結構C++語言版》

總結

以上是生活随笔為你收集整理的邓公数据结构C++语言版学习笔记——二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。