當兩棵樹相等時？

Question

如果兩棵樹（非二叉搜索樹）的順序遍歷是相同的，它是否保證兩棵樹是相同的？

如果答案是否定的，那麼有序和預序遍歷都是一樣的嗎？

Answer 1

絕對不是。兩棵樹

b 
/\ 
a d 
/\ 
    c e 

和

d 
/\ 
    b e 
/\ 
a c 

都具有a b c d e的序遍歷。實際上，它們是旋轉，一個操作which preserves inorder traversal。

Answer 2

我在想「不」。

兩棵樹可能有不同的平衡，但具有相同的節點值「順序」。舉例來說，如果設定的

1,2,3,4,5,6,7 

的您打造一個樹：

  4 
     2 6 
    1 3 5 7 

中序遍歷將產生1,2,3,4,5,6,7。

但是，如果你選擇一個不同的根節點（如果列表不排序預先正確）

  5 
     4 6 
     2  7 
    1 3 

這兩棵樹可以得到同樣的中序遍歷結果，但（顯然）不相同。

甚至

 7 
    6 
    5 
    4 
    3 
2 
1 

等等。

這也與BSP（二元空間分區）樹的問題有關，該樹通常用於遊戲開發碰撞檢測和可視性確定。

BSP在樹中存儲三角形。每個節點都包含一個三角形或方面。左側節點包含所有「後面」小孩，而右側小孩則包含「前面」的所有內容。按預期緩步。

如果您選擇場景中最左側的面作爲根，則右側的孩子將擁有其他每個面。如果你爲正確的孩子做出錯誤的決定，同樣的事情會發生。建立一個BSP編譯器是完全可能的，通過白癡分析，構建一個實際上是列表的「樹」（就像我上面的最後一個例子）。問題在於對數據集進行分區，以便每個節點儘可能均等地分割剩餘列表。這是BSP通常在編譯時生成的原因之一，因爲爲非常複雜的幾何構建一個BSP可能需要幾個小時才能找到最佳解決方案。

Answer 3

NO，以及它與這個簡單的例子可見

3   2   
    2   1 3 
1   0 
0 

兩者都有相同序遍歷[0,1,2,3]

但如果序和預訂遍歷是相同的，那麼樹是相等的。