二叉搜索树。插入方法插入不正确

Question

我遇到一个问题，二叉树中的项目插入不正确。我在每个节点中插入字符串。我想我可能做错了什么，因为我似乎总是选择错误的树。即

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

}

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