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

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

如果必须更改当前节点，则必须检查每个!并重新插入你的 key ，因为你的根可能会在每次插入时发生变化!并且您绘制的树永远不会生成您的代码生成的唯一可能形式的树是针对给定输入的这些树:

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