二叉樹的遍歷

二叉樹的遍歷即是不重復地訪問二叉樹的所有結點。

在遍歷二叉樹時，一般先遍歷左子樹，然后再遍歷右子樹。在先左后右的原則下，二叉樹的遍歷又可分為三種：前序遍歷、中序遍歷和后序遍歷。

1)前序遍歷

前序遍歷即先訪問根結點，然后遍歷左子樹，最后遍歷右子樹。在遍歷左子樹和遍歷右子樹時，依然是先遍歷根結點，然后是左子樹，再是右子樹。

操作的具體方式：

若二叉樹為空，則結束返回。

否則：訪問根結點?前序遍歷左子樹?前序遍歷右子樹

如上圖所示的完全二叉樹，它的前序遍歷結果是：A、B、D、H、P、Q、I、R、E、J、K、C、F、L、M、G、N、O

2)中序遍歷

中序遍歷，即先遍歷左子樹，然后訪問根結點，最后是遍歷右子樹。

具體的操作方式：

若二叉樹為空，則結束返回。

否則：中序遍歷左子樹?訪問根結點 ?中序遍歷右子樹

這里強調，在遍歷左子樹和右子樹時，仍然要采用中序遍歷的方法。

如上圖所示的完全二叉樹，它的中序遍歷結果是：P、H、Q、D、R、I、B、J、E、K、A、L、F、M、C、N、G、O

3)后序遍歷

后序遍歷，即選遍歷左子樹，然后是遍歷右子樹，最后訪問根結點。

具體的操作方式：

若二叉樹為空，則結束返回。

否則：前序遍歷左子樹?前序遍歷右子樹?訪問根結點

如上圖所示的完全二叉樹，它的后序遍歷結果是：P、Q、H、R、I、D、J、K、E、B、L、M、F、N、O、G、C、A

更多精彩資訊請關注查字典資訊網，我們將持續為您更新最新資訊!