BST 中的隔离错误迭代插入

Question

我正在尝试编写代码以迭代方式在BST中插入新元素。当我尝试执行代码时，出现段错误。有人可以查看代码并帮助我更正吗？

bool insert2(int item)
{
    BstNode *parent;
    BstNode *root=new BstNode;
    cout<<root->data;
    cout<<"n";
    BstNode *ptr;
    int ctr=0;
    //cout<<root->data;
    if (root==NULL)
    {
        BstNode *temp=new BstNode;
        temp->data=item;
        temp->left=NULL;
        temp->right=NULL;
        root=temp;
        //cout<<root->data;
        return true;
    } 
    else
    {
        ptr=root;
        while (ptr!=NULL)
        {
            ctr=ctr+1;
            cout<<ctr;
            if (ptr->data==item)
            {
                cout<<ptr->data;
                return false;
            }
            if (item < ptr->data)
            {
                parent=ptr;
                ptr=ptr->left;
            } 
            else
            {
                parent=ptr;
                ptr=ptr->right;
            }
        }
        BstNode *add=new BstNode;
        add->data = item;
        add->left= NULL;
        add->right= NULL;
        return true;
    }
}

在编辑根>数据部分时，代码将进入第一个 if 块并返回 true，这让我猜测我的问题出在减速的某个地方。

Answer 1

你做错了很多事情。 首先，正如PaulMcKenzie所指出的，你不应该在函数的开头创建根。 如果 BST 开始时不为空，则根已经存在，您不想创建一个新根。 相反，根应该是一个公共变量（这只允许你有一个BST），或者函数应该将指向根的指针作为参数之一。 创建根，然后测试它以查看它是否为 NULL，这当然是没有意义的。 除非内存不足，否则在创建后它不会立即为 NULL。

代码的另一个问题是，在 BST 中找到适当的位置后，创建新节点，但不将其附加到树。 相反，您可能希望在初始化add后插入以下行：

if(item < parent->data)
    parent->left = add;
else
    parent->right = add;

至于每次调用函数时都出现段错误的事实，可能是因为当您声明 root 时，您没有初始化其right并left指向 NULL 的指针。因此，while 循环在达到 root->left 或 root->right 时不会停止。 当您尝试稍后在循环中顺从ptr时，您将引用未初始化的指针，从而导致段错误。