預訂遍歷是否可能與後序遍歷的順序相同？

Question

如果T是一個有多於一個節點的有序樹。是否有可能T的前序遍歷以與T的後序遍歷相同的順序訪問節點？ 如果「是」，請舉個例子。如果「不」，請你解釋爲什麼它不會發生？

Answer 1

除非我錯過了一些顯而易見的事情，否則答案是否定的。具有> 1個節點的有序樹（例如2個節點）將如下所示。

A  
B      

或

A 
     C 

後序遍歷訪問在左右根和預購訂單的節點訪問節點根的順序-左右。爲了讓他們產生相同的輸出，「左」必須等於「根」，這是沒有意義的。通過上面的例子，預購將分別產生AB或AC，後期將產生BA和CA.

Answer 2

在一般情況下，樹的葉子是獨一無二的，因此，如果您執行前序遍歷或後序遍歷，應該以相反的方式出現。

但是，我可以看到兩種情況，其中前後遍歷是相同的：單例和重複元素。

對於單身人士，您只有一個節點，所以如果您在查找零葉之前或之後訪問它，並不重要。

如果您的樹中有重複元素，該怎麼辦？如果插入的策略是接受任何元素大於或等於根節點，那麼就會出現退化樹權：

A 
    \ 
    A 
    \ 
    A 
     \ 
     A 

如果是小於或等於根節點，你'd仍然有一棵退化的樹，但在左邊。

現在，如果您的插入策略是放棄重複元素，那麼您將留下單例情況，它仍然具有導致相同元素的前後遍歷。