0

只是显示二叉树的节点的样子。我不确定出了什么问题，但我感觉它与私有功能有关。如何比较私有数据，以便查看我要查找的值是否在该节点内？

    class binarytree
    {
    private:
        class node
        {
        public:

            int data;
            node * left;
            node * right;

            node (int x)
            {
                data = x;
                left=NULL;
                right=NULL;
            }


        };

    node * root;

这就是我插入节点的方式

    void insert(int x, node * &r)
        {
            if(r==NULL)
            {
                r= new node(x);
            }

            else
    {
        if(x < r->data)
        {
            //insert left
            insert(x, r->left);
        }

        else
        {
            //insert right
            insert(x, r->right);
        }
    }
}

这是当我尝试将 x 与 r->data 进行比较时给我带来麻烦的代码部分，程序崩溃并给我错误消息“访问冲突读取位置 0x00000000”

void remove(int x, node * &r)
{

    if(x == r->data)
    {
        if(r->right == NULL && r->left == NULL)
        {

            r = NULL;

        }

        else if(r->right == NULL && r->left != NULL)
        {
            r = r->left;

        }

        else if(r->right != NULL && r->left == NULL)
        {
            r = r->right;
        }

        else
        {
            node * temp;
            temp =r;
            r = r->left;
            while(r->right != NULL)
            {
                r = r->right;
            }

            r->right = temp->right;
            delete temp;
        }
    }

    else if ( x < r->data)
    {

        remove(x, r->left);

    }

    else if (x > r->data)
    {
        remove(x , r->left);
    }


}

这是功能公开的地方。然后我调用私有函数，以便我可以操作私有树。

public:

    binarytree()
    {
    root =  NULL;
    }

    ~binarytree()
    {
    //tooo: write this
    }

//return true if empty, false if not
    bool empty()
    {}


    void insert(int x)
    {
    insert(x, root);

    }




    void remove(int x)
    {
        remove(x,root);

    }

};

编辑：这是该程序的另一个功能，但可能导致 r 指向 NULL。

    int extractMin(node * &r)
{

    if(r->left == NULL)
    {
        if(r->right == NULL)
        {

            return r->data;

        }

        else
        {
            int x = r->data;
            r = r->right;
            return x;

        }
    }

    else
    {

        return extractMin(r->left);

    }
}

这是检查 r 是否为 NULL 的新函数

    void remove(int x, node * &r)
{
    if(r == NULL)
    {
        cout<<"why am I null?"<<endl;
    }

    else
    {
        if(x == r->data)
        {
            if(r->right == NULL && r->left == NULL)
            {

                r = NULL;

            }

            else if(r->right == NULL && r->left != NULL)
            {
                r = r->left;

            }

            else if(r->right != NULL && r->left == NULL)
            {
                r = r->right;
            }

            else
            {
                node * temp;
                temp =r;
                r = r->left;
                while(r->right != NULL)
                {
                    r = r->right;
                }

                r->right = temp->right;
                delete temp;
            }
        }

        else if ( x < r->data)
        {

            remove(x, r->left);

        }

        else if (x > r->data)
        {
            remove(x , r->left);
        }

    }
}
4

4 回答 4

2

NULL在尝试访问内部成员之前，您应该始终检查：

void remove(int x, node * &r)
{
    if(r != NULL)
    {
       // Your code
    }
}

你打电话用ras删除，NULL然后尝试检查r.Left. 那么在这里你有访问冲突

我还必须问，如果这对你有用吗？特别insert不会以这种方式工作。尝试

    void insert(int x, node * &r)
    {
        if(r==NULL)
        {
            r= new node(x);
        }
        else
        {
            if(x < r->data)
            {
                if(r->left != NULL)
                {
                   //insert left
                   insert(x, r->left);
                }
                else
                {
                    r->left = new node(x);
                }
            }
            else
            {
                if(r->right != NULL)
                {
                   //insert right
                   insert(x, r->right);
                }
                else
                {
                    r->left = new node(x);
                }

            }
        }
    }
于 2013-09-16T06:06:03.763 回答
0

r不知何故为空。您需要检查r传入的是否为NULL，或检查 是否root为非空，并且remove仅在子项存在时才调用它们。

于 2013-09-16T06:07:00.017 回答
0

好吧，错误说，当您尝试取消引用它时， r 指向 NULL。因此，您必须确保将内存分配给 r 时它不会返回 NULL。

binarytree()
{
    root =  NULL;
}

void remove(int x)
{
    remove(x,root);

}

在您的情况下，您试图取消引用 NULL（如错误所述）当您在调用插入之前调用删除时，这会在您的代码中发生。您只需在 remove 的开头检查 r 是否指向 NULL。或者更好的是，确保在 r 为 NULL 时不会对其进行解析。

于 2013-09-16T06:03:49.227 回答
0

您正在x与root. 当你的树是空的时，root == nullptr. 您应该先检查一下r == nullptr，例如：

bool remove(int x, node * &r) {
   if(!r) {
      return false; // Indicate whether removal succeeded
   }

   //... etc.
}
于 2013-09-16T06:15:45.217 回答