JavaScript二叉樹遍歷詳解

二叉樹概述

二叉樹（Binary tree）是每個節點最多存在左右兩個分支的樹形數據結構。通常分支被稱作“左子樹”或“右子樹”，節點有根節點和子節點。二叉樹的分支順序不能隨意顛倒。

二叉樹遍歷有以下幾種方式：

1、深度遍歷，包括：

• 先序優先（DLR）：根結點 > 左子樹 > 右子樹

• 中序優先（LDR）：左子樹 > 根結點 > 右子樹

• 後序優先（LRD）：左子樹 > 右子樹 > 根結點

2、廣度遍歷(層級遍歷)

樹結構代碼構建

深度遍歷實現

• 先序優先遍歷DLR。

• 中序優先遍歷LDR。

• 後序優先遍歷LRD。

廣度優先(層級遍歷)，構造棧來打印。

深度遍歷(先序優先非遞歸版)。

深度遍歷(後序優先非遞歸版)。

總結

二叉樹遍歷非常有用，理解起來其實非常簡單。主要利用的是遞歸調用和棧(或隊列)來完成遍歷。