3元二叉搜索樹

Question

我通過過去的考試試卷工作我先進的編程課程，我已經在這個問題

必須在二叉搜索樹中的值滿足什麼性質得到卡住？有多少個不同的二叉搜索樹包含三個值1 2 3？解釋你的答案。

我可以很容易地回答第一部分，但第二位，關於可能的樹數量我已經難倒了。我的第一本能是說只有一棵樹是可能的，以2爲根，因爲定義是這樣說的，但這個問題是整個論文中共有100個作品的總分爲100，所以我只能假設這是一個狡猾的問題，還有一個更微妙的解釋，但講義中並沒有解釋這一點。有誰知道誰來回答這個問題？

Answer 1

我認爲一個技巧是，樹可以是簡併一個（有效地，元件的鏈接列表）：

1 
\ 
    2 
    \ 
    3 

及其變型。

此外，這些樹被認爲是相同的嗎？

2  2 
/\ /\ 
3 1 1 3 

Answer 2

問題並不是說樹是平衡的，所以想想1或3是否可以在根節點。

Answer 3

試着用這三個節點思考所有可能的二叉樹。有多少棵樹滿足二叉搜索樹的屬性？

Answer 4

如果我沒記錯的話，樹的根不一定是「中間元素」。因此，還有幾棵樹的組合：

2 
1  3 
or 
1 
    2 
     3 
or 
1  
     3 
    2 
or 
     3 
    2 
1 
or 
     3 
1 
    2 

也許我忘了一些，但我想你會明白。只是爲了我的符號：Newline會在樹上下來，上邊的左邊和右邊顯示它是否是其父節點的右邊或左邊;）