天天最新：什么是二叉樹的遍歷？二叉樹的遍歷順序規則是什么？

來源：CSDN 時間：2023-03-02 09:37:25

二叉樹的遍歷分為以下三種：

先序遍歷：遍歷順序規則為【根左右】

(相關資料圖)

中序遍歷：遍歷順序規則為【左根右】

后序遍歷：遍歷順序規則為【左右根】

什么是【根左右】？就是先遍歷根，再遍歷左孩子，最后遍歷右孩子；

舉個例子，看下圖（圖從網上找的）：

先序遍歷：ABCDEFGHK

中序遍歷：BDCAEHGKF

后序遍歷：DCBHKGFEA

以中序遍歷為例：

中序遍歷的規則是【左根右】，我們從root節點A看起；

此時A是根節點，遍歷A的左子樹；

A的左子樹存在，找到B，此時B看做根節點，遍歷B的左子樹；

B的左子樹不存在，返回B，根據【左根右】的遍歷規則，記錄B，遍歷B的右子樹；

B的右子樹存在，找到C，此時C看做根節點，遍歷C的左子樹；

C的左子樹存在，找到D，由于D是葉子節點，無左子樹，記錄D，無右子樹，返回C，根據【左根右】的遍歷規則，記錄C，遍歷C的右子樹；

C的右子樹不存在，返回B，B的右子樹遍歷完，返回A；

至此，A的左子樹遍歷完畢，根據【左根右】的遍歷規則，記錄A，遍歷A的右子樹；

A的右子樹存在，找到E，此時E看做根節點，遍歷E的左子樹；

E的左子樹不存在，返回E，根據【左根右】的遍歷規則，記錄E，遍歷E的右子樹；

E的右子樹存在，找到F，此時F看做根節點，遍歷F的左子樹；

F的左子樹存在，找到G，此時G看做根節點，遍歷G的左子樹；

G的左子樹存在，找到H，由于H是葉子節點，無左子樹，記錄H，無右子樹，返回G，根據【左根右】的遍歷規則，記錄G，遍歷G的右子樹；

G的右子樹存在，找到K，由于K是葉子節點，無左子樹，記錄K，無右子樹，返回G，根據【左根右】的遍歷規則，記錄F，遍歷F的右子樹；

F的右子樹不存在，返回F，E的右子樹遍歷完畢，返回A；

至此，A的右子樹也遍歷完畢；

最終我們得到上圖的中序遍歷為BDCAEHGKF，無非是按照遍歷規則來的；

根據“中序遍歷”的分析，相信先序遍歷和后序遍歷也可以輕松寫出~

責任編輯：

標簽：

天天最新：什么是二叉樹的遍歷？二叉樹的遍歷順序規則是什么？