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

Question

我有一个问题，我的二叉树中的项目被错误地插入。我在每个节点中插入字符串。我想我可能做错了什么，因为似乎我总是以错误的树结束。IE

甲、乙、丙

我应该

   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