8.二叉樹

8.1概述

????????二叉樹是一種基本的非線性數據結構，它是由n（n>=0）個節點構成的有限集合。在二叉樹中，每個節點最多有兩個子節點，通常被稱作左孩子（left child）和右孩子（right child）。此外，二叉樹還具有以下特點： 每個節點包含一個值（也可以包含其他信息）。 有一個被稱為根（root）的特殊節點，它是二叉樹的起點，沒有父節點。 如果一個節點存在左子節點，則該節點稱為左子節點的父節點；同樣，如果存在右子節點，則稱為右子節點的父節點。 每個節點的所有子孫（包括子節點、孫子節點等）構成了該節點的子樹（subtree）。 左子樹和右子樹本身也是二叉樹，且可以為空。

?遍歷：

????????廣度優先遍歷（Breadth-First Search, BFS）和深度優先遍歷（Depth-First Search, DFS）是兩種在圖或樹這類非線性數據結構中搜索節點的常用策略。

????????廣度優先遍歷（BFS）： 從根節點開始，首先訪問所有與根節點直接相連的節點（即第一層鄰居節點），然后按順序訪問它們的子節點（第二層），接著是孫子節點（第三層），以此類推。 使用隊列作為輔助數據結構，將起始節點入隊，每次從隊列頭部取出一個節點進行訪問，并將其未被訪問過的相鄰節點全部加入隊列尾部，直到隊列為空為止。 在二叉樹場景下，BFS通常實現為層序遍歷，它會按照從上到下、從左到右的順序依次訪問各個節點。

????????深度優先遍歷（DFS）： 從根節點開始，盡可能深地探索圖或樹的分支，直到到達葉子節點或者無法繼續深入時返回上一層節點，再嘗試探索其他分支。 深度優先遍歷有多種方式：前序遍歷（先訪問根節點，再遍歷左子樹，最后遍歷右子樹）、中序遍歷（先遍歷左子樹，再訪問根節點，最后遍歷右子樹）、后序遍歷（先遍歷左子樹，再遍歷右子樹，最后訪問根節點）以及反向的前后序遍歷等。 在二叉樹的DFS中，通常使用遞歸的方式實現。另外，也可以借助棧這一數據結構，模擬遞歸過程進行非遞歸實現。 總結來說，BFS保證了同一層次的節點會被一起訪問到，而DFS則是沿著一條路徑盡可能深地探索，直至無法繼續前進時回溯至另一條路徑。這兩種遍歷方式在解決不同的問題時各有優勢，如尋找最短路徑、拓撲排序等場景常常會用到BFS，而解決迷宮求解、判斷連通性等問題時DFS則更為常見。

????????前序遍歷（Preorder Traversal）： 從根節點開始，首先訪問根節點，然后按照相同的方式遍歷左子樹，最后遍歷右子樹。用文字描述就是： 訪問當前節點（即根節點）。 遞歸地對當前節點的左子樹進行前序遍歷。 遞歸地對當前節點的右子樹進行前序遍歷。

????????中序遍歷（Inorder Traversal）： 在中序遍歷中，訪問順序為：左子樹 -> 根節點 -> 右子樹。 遞歸地對當前節點的左子樹進行中序遍歷。 訪問當前節點。 遞歸地對當前節點的右子樹進行中序遍歷。

????????后序遍歷（Postorder Traversal）： 在后序遍歷中，訪問順序為：左子樹 -> 右子樹 -> 根節點。 遞歸地對當前節點的左子樹進行后序遍歷。 遞歸地對當前節點的右子樹進行后序遍歷。 訪問當前節點。