一、什麼是深度優先遍歷
深度優先遍歷算法是經典的圖論算法。從某個節點v出發開始進行搜索。不斷搜索直到該節點所有的邊都被遍歷完，當節點v所有的邊都被遍歷完以後，深度優先遍歷算法則需要回溯到v以前驅節點來繼續搜索這個節點。
注意：深度優先遍歷問題一定要按照規則嘗試所有的可能才行。
二、二叉樹
1. 二叉樹簡介
二叉樹是一種特殊的數據結構，常見的數據結構包含數組，鏈表，圖、隊列、散列表和樹。二叉樹屬於樹結構，二叉樹中的每一個節點都有兩個分支稱為左子樹和於右子樹。二叉樹每一層最多有(2n−1) (2^n - 1)(2
n
−1)個節點。和普通樹不同，普通樹的節點沒有分支限制，並且普通樹的節點沒有左右、子樹之分。
2.二叉樹類型
二叉樹類型：空二叉樹、滿二叉樹、完全二叉樹、完美二叉樹、平衡二叉樹。
空二叉樹：有零個節點
完美二叉樹：每一層節點都是滿的二叉樹（如1中舉例的圖）
滿二叉樹：每一個節點都有零個或者兩個子節點
完全二叉樹：出最後一層外，每一層節點都是滿的，並且最後一層節點全部從左排列
平衡二叉樹：每個節點的兩個子樹的深度相差不超過1.
注：國內對完美二叉樹和滿二叉樹定義相同
3.二叉樹相關術語
4. 二叉樹的節點代碼
因為每個·節點都有兩個子節點相連接，所以我們只需要擁有根節點就能找到二叉樹上的任意節點，每個節點定義都相同
5. 二叉樹遍歷順序
二叉樹三種遍歷形式：
- DLR（先序）：
- LDR（中序）：
- LRD(後序）：
注意：L代表左子樹R代表右子樹；D代表根
6.深度優先遍歷和廣度優先遍歷
深度優先遍歷：前序、中序和後序都是深度優先遍歷
從根節點出發直奔最遠節點，
廣度優先遍歷：首先訪問舉例根節點最近的節點，按層次遞進，以廣度優先遍歷上圖的順序為：1-2-3-4-5-6-7
三、面試題
企鵝運維面試題：
1.二叉樹遍歷順序：看上文
小明同學有給大家準備一些資料，可以幫小明同學轉發這篇文章後，私信小明：學習資料，即可獲取啦。
分享到:
