이진 검색 트리. 삽입 방법이 잘못 삽입되었습니다.

Question

내 바이너리 트리의 항목이 잘못 삽입되는 문제가 있습니다. 각 노드에 문자열을 삽입하고 있습니다. 나는 틀린 나무로 항상 끝내는 것처럼 보이기 때문에 내가 뭔가 잘못하고 있다고 생각합니다. 즉

A, B, C

는

나는

B 
/\ 
A C 

을해야하지만, 어떻게 든 내가 좋아하는 끝낼 :

C 
/\ 
B A 

또는 뭔가 다른 내가에 삽입되는 순서에 따라 내 나무.

이 내 나무 클래스 :

이 내 삽입 방법이고 도우미 메서드를 삽입합니다. 너는 내가 뭘 잘못하고 있는지 한번 볼 수 있니? 미리 감사드립니다.

당신이 periviusly 삽입 된 것을 변경하지 않을 경우 렸기 때문에의

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; 
     } 
    } 

} 

Answer 1

는, 예를 들어, 당신은 당신이 "C"를 삽입 그래서 만약 루트에서 일어날 수없는 절대 (예 : B에 대한)를 삽입 먼저 다음 항목에서 C를 삽입 할 경우, "B"는 "A"의 순서로 당신이 나무 모양의 것 :

C 
/
    B 
/
A 

당신은 현재 노드를 변경해야하는 경우 모든 검사해야! 그리고 삽입 할 때마다 루트가 바뀔 수도 있습니다. 그리고 당신이 그리는 나무는 주어진 입력에 대해서만 코드가 생성하는 나무의 유일한 형태를 생성하지 않습니다 :

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