當前位置:成語大全網 - 新華字典 - Python算法系列—深度優先遍歷算法

Python算法系列—深度優先遍歷算法

壹、什麽是深度優先遍歷

深度優先遍歷算法是經典的圖論算法。從某個節點v出發開始進行搜索。不斷搜索直到該節點所有的邊都被遍歷完,當節點v所有的邊都被遍歷完以後,深度優先遍歷算法則需要回溯到v以前驅節點來繼續搜索這個節點。

註意:深度優先遍歷問題壹定要按照規則嘗試所有的可能才行。

二、二叉樹

2.二叉樹類型

二叉樹類型:空二叉樹、滿二叉樹、完全二叉樹、完美二叉樹、平衡二叉樹。

空二叉樹:有零個節點

完美二叉樹:每壹層節點都是滿的二叉樹(如1中舉例的圖)

滿二叉樹:每壹個節點都有零個或者兩個子節點

完全二叉樹:出最後壹層外,每壹層節點都是滿的,並且最後壹層節點全部從左排列

平衡二叉樹:每個節點的兩個子樹的深度相差不超過1.

註:國內對完美二叉樹和滿二叉樹定義相同

3.二叉樹相關術語

術語 解釋

度 節點的度為節點的子樹個數

葉子節點 度為零的節點

分支節點 度不為零的節點

孩子節點 節點下的兩個子節點

雙親節點 節點上壹層的源節點

兄弟節點 擁有同壹雙親節點的節點

根 二叉樹的源頭節點

深度 二叉樹中節點的層的數量

DLR(先序):

LDR(中序):

LRD(後序):

註意:L代表左子樹R代表右子樹;D代表根

6.深度優先遍歷和廣度優先遍歷

深度優先遍歷:前序、中序和後序都是深度優先遍歷

從根節點出發直奔最遠節點,

廣度優先遍歷:首先訪問舉例根節點最近的節點,按層次遞進,以廣度優先遍歷上圖的順序為:1-2-3-4-5-6-7

三、面試題+勵誌

企鵝運維面試題:

1.二叉樹遍歷順序:看上文

2.用妳熟悉的語言說說怎麽創建二叉樹? python看上文