有關插入空的二叉搜索樹的考試問題

我在解釋將元素插入二叉搜索樹的某個問題時遇到問題。我熟悉前序，後序和inorder遍歷，但我不熟悉以下問題：有關插入空的二叉搜索樹的考試問題

假設我們將元素3,5,6,1,2,4,7插入排序到最初的空二叉搜索樹中。

如果我只給了一組按照該順序插入的數字，我該如何將它變成二叉搜索樹？ 3會是根？我是否會自己平衡其他數字到正確的子樹？在這種情況下不會有很多解釋嗎？有沒有遵循某種約定？

謝謝。

2011-06-26 Jigglypuff

將項目添加到樹中時，現有樹不會重新排序。新項目僅添加到葉節點。這意味着當你第一次添加3時，3將是結果的根節點。當您添加5，這將是對3的權利，等等。這導致以下三種：

2011-06-26 12:29:44 Sjoerd

有沒有告訴放在哪裏的一種方式7？因爲不能它也走到4或2的右邊？ – Jigglypuff

7大於3，所以它在3的右邊。它大於5，所以它在5的右邊等。 – Sjoerd

哦，我明白了。謝謝。我一直誤解整個事情，認爲你只看直接節點而不是之前的節點。 – Jigglypuff

如果沒有關於樹如何平衡的規則的進一步信息，我將不得不假設它指的是一個「天真」的不平衡樹。

所以這個：

  3 
    /-----/ \-----\ 
1    5 
    \--\  /--/ \--\ 
     2  4   6 
         \-\ 
          7

2011-06-26 12:26:36

謝謝你回答 – Jigglypuff

是，3將是根，因爲第一次插入後整棵樹只有一個元素。保持相同的邏輯，如果（數字，左，右）代表你會得到一個節點：

2011-06-26 12:26:51

謝謝你的答案 – Jigglypuff

回答