從右到左

Question

遍歷一棵樹，我讀的書「算法的基本原理」的臂章和Bratley並且在樹遍歷的部分，上面寫着聲明：

預購，後序和中序遍歷從左邊的 左邊探索樹。三種相應的技術從右邊的 探索樹到左邊。

從右向左遍歷是什麼意思？我的猜測是，它們意味着從右到左的前序遍歷相當於常規的從左到右的後序遍歷嗎？而且從左到右和從右到左的順序是完全相同的算法？

Answer 1

我不確定我是否理解所有問題，所以我只回答一個問題。

從右向左遍歷是什麼意思？

所有這些遍歷樹的方法都需要遞歸。在遞歸中，你需要對元素進行操作並遍歷左/右樹。你有*L*R*。您可以插入您的do something而不是*之一。並將獲得您的前/中/後訂單。

Answer 2

這裏有一個簡單的樹，兩片葉子單個節點：

 Mom 
     ^
     /\ 
    / \ 
    / \ 
    Sally Bob 

由於有三個標籤，有六個（三級階乘）可能的訂單。這三個對應於左到右遍歷，其中Sally是Bob之前命名爲：

• 媽媽，莎莉，鮑勃←預購。媽媽在孩子面前。
• 莎莉，鮑勃，媽媽←後序。媽媽是在孩子之後。
• Sally，媽媽，鮑勃←訂購。媽媽在孩子們之間。

如果我們參觀以相反的順序孩子（鮑伯頭），那麼我們將不得不從右到左（RTL ）穿越。 （鮑勃在右邊，對吧？）再次，三種可能性：

• 媽媽，鮑勃，莎莉← RTL預購。媽媽在孩子面前。
• Bob，Sally，Mom ← RTL郵購。媽媽是在孩子之後。
• Bob，Mom，Sally ← RTL inorder。媽媽在孩子們之間。

---

以上全部是深度優先遍歷。這意味着如果我們訪問一個子節點（例如Sally），我們完成遍歷該節點，然後繼續接下來要遍歷的任何節點。