二叉搜索樹。插入方法插入不正確

我有一個問題，我的二進制樹中的項目插入不正確。我在每個節點中插入字符串。我想我可能會做錯事，因爲它似乎總是以錯誤的方式結束。即二叉搜索樹。插入方法插入不正確

A，B，C

我應該有

B 
/\ 
A C

但不知何故，我結束了像：

C 
/\ 
B A

或依賴於我在插入其中爲了不同的東西我樹。

這是我的樹類：

這是我的插入方法和插入的輔助方法。你能看一看，看看我做錯了什麼嗎？提前致謝。

void BinarySortTree::insert(string key) 
{ 
    if(root != NULL) 
    { 
     insert(key, root); 
    } 
    else 
    { 
     root = new TreeNode; 
     root->item = key; 
     root->left = NULL; 
     root->right = NULL; 
    } 
} 

void BinarySortTree::insert(string key, TreeNode *node) 
{ 
    bool done = false; 

    while(!done) 
    { 
     if(key.compare(node->item) < 0) 
     { 
      if(node->left != NULL) 
      { 
       node = node->left; 
      } 
      else 
      { 
       node->left = new TreeNode; 
       node->left->item = key; 
       node->left->left = NULL; 
       node->left->right = NULL; 
       done = true; 
      } 
     } 
     else if(key.compare(node->item) > 0) 
     { 
      if(node->right != NULL) 
      { 
       node = node->right; 
      } 
      else 
      { 
       node->right = new TreeNode; 
       node->right->item = key; 
       node->right->left = NULL; 
       node->right->right = NULL; 
       done = true; 
      } 
     } 
     else if(key.compare(node->item) == 0) 
     { 
      done = true; 
     } 
    } 

}

來源

2011-03-13 Tony

你的算法是不是遞歸的，請糾正你的問題的標籤。我建議你重新閱讀插入的方式和方法。 – 2011-03-13 19:21:23

@ Mr.TAMER：你看到的*實現*當然不是遞歸的。至於*算法*本身......並不那麼簡單。它可以在算法遞歸的廣義定義下正式稱爲遞歸。事實上，從算法的角度來看，任何循環都可以被解釋爲遞歸的退化形式。 – AnT 2011-03-13 19:47:06

@AndreyT：謝謝，我不知道...經驗教訓:) – 2011-03-13 19:50:22

它becouse當你永遠不會改變什麼periviusly插入，例如，如果你刀片C起初插入（例如B）永遠不能因此如果你插入「C」拿根處的下一個項目，「B」，「A」的順序你將有一個樹形如：

C 
/
    B 
/
A

你必須每次檢查當前節點必須改變！並重新插入你的鑰匙，你的根可能會改變每一個插入！和你畫絕不會產生樹木的唯一pissible形式的代碼生成的樹是這些給定輸入：

ABC  ACB  BAC  CBA  CAB 
        BCA   
A   A   B   C  C    
    \   \  /\  / /  
    B   C  A C  B  A    
    \  /    /  \ 
    C  B     A   B

來源

2011-03-13 19:47:07 Ali1S232

您正在描述自平衡二叉搜索樹。看起來他試圖在沒有平衡的情況下實現簡單的二叉搜索樹，在您描述的最壞情況下退化爲線性列表。 – Antti 2011-03-13 19:52:59

爲了保持平衡，我需要做些什麼？我只需要添加，不需要刪除。 – Tony 2011-03-13 22:18:54

對於平衡二叉樹，您需要[紅黑樹]（http://en.wikipedia.org/wiki/Red-black_tree）或[AVL樹]（http://en.wikipedia.org/wiki/AVL_tree）。然而，實施這些有點棘手，你可能會首先想解決你原來的問題。 – Antti 2011-03-14 17:53:54

二叉搜索樹。插入方法插入不正確

回答

相關問題