二叉樹的PostOrder遍歷不一致地跳轉到兄弟或父節點

Question

在二叉樹中輸入以下值（{18,26,52,78,45,16,67,58,73,11}）時，您會收到這棵樹：

兩個預購和中序遍歷工作，我希望他們。然而，當談到PostOrder（PO）時，我收到了與我原先想象的不同的東西。

據我所知，PO首先搜索左側子樹，然後右側子樹，最終搜索節點（結束於根節點）。

當在PO中穿越此樹時，最終得到以下結果： {11，16，45，58，73，67，78，52，26，18}。 在寫出此結果背後的邏輯時，您會得到以下結果： 從根開始，完全左邊，最後到達11，這是您的第一個節點。之後，你升到一個級別，並採取其父母（16）。你繼續這樣做，直到你到達根（因爲它不是一個leftChild而沒有被包含）。一旦你通過這個最初的左子樹，你在右邊下一級並在那裏檢查leftChilds。如果沒有，則進入另一個級別，這是我們找到的位置45.

此時我們有一個{11,16,45}的列表。我們繼續這樣做，最終以58結果，這是我們在結果中的下一個價值。這就是我的困惑所在：我們得到的下一個值是73，與預期的67相反。爲什麼當找到另一個leftChild（它的父親）時，它跳到了73？

下面的代碼需要穿越低谷後序樹的護理：

public void postorderTraversal(){ 
    postorderHelper(root); 
} 

private void postorderHelper(Node node){ 
    if(node != null){ 
     postorderHelper(node.getLeftNode()); 
     postorderHelper(node.getRightNode()); 
     System.out.print(node.getData() + " "); 
    } 
} 

我猜這是因爲值73節點的parentNode（左右最高優先級）前處理，但是爲什麼45-52-78三角形不是這樣呢？

Answer 1

我猜這是因爲具有值73的節點在parentNode（左右優先級）之前處理，但爲什麼45-52-78三角形中不是這種情況呢？

是，在這45來78之前，這來之前52

左同胞將永遠是正確的兄弟姐妹，這將永遠是父母前參觀前參觀。什麼其他之間訪問這些將取決於孩子的左，右兄弟姐妹。

的wikipedia page on tree traversal把它描述爲：

要遍歷一個非空的二叉樹在後序，遞歸地在每個節點處執行以下操作：

• 遍歷左子樹。
• 遍歷右側子樹。
• 訪問根目錄。

所以你永遠只能訪問一個節點，如果你訪問過的所有其兒，你就永遠是右子樹前訪問左子樹。結果中的所有內容都與此一致。