C++ 树指针问题

Question

我遇到了二叉搜索树指针的问题，无法确定原因。我有一个函数，我在其中取两棵树并在预定位置交换树的两个子树。这是进行上述交换的代码。

opNode* tmp = new opNode();
opNode* tmp2 = new opNode();
tmp = this->clone();
tmp2 = secondParentNode->clone();
this->operation = tmp2->operation;
this->val = tmp2->val;
this->lChild = tmp2->lChild;
this->rChild = tmp2->rChild;
secondParentNode = tmp;

至此我已经确定了要交换的每棵子树的位置。 "this"指针代表第一个交换点，secondParentNode是代表第二个的opNode指针。

这里有两个问题：

首先是交易所可以造成一个节点只有一个的情况child。我未能确定这是如何发生的。

其次，也许是一些相关的信息，一旦 this->lChild 设置为 tmp2->lChild 并且 this->rChild = tmp2->rChild，我插入了一个检查是否是 secondParentNode->lChild或 secondParentNode->rChild 为空。这至少会导致段错误。

克隆（深拷贝）功能没有用吗？如果是这样，为什么不呢？对于可能导致这些问题的任何想法，我们将不胜感激。

opNode 是我的节点class:

struct opNode
{
    string operation;
    double val;
    opNode* lChild;
    opNode* rChild;
    opNode* clone();
};

和相关的克隆函数：

opNode* opNode::clone()
{
    if(this != nullptr)
    {
        opNode* n = new opNode();
        n->val = val;
        n->operation = operation;
        n->rChild = rChild->clone();
        n->lChild = lChild->clone();
        return n;
    }
    return nullptr;
}

编辑* 按要求，交换功能。 randPoint1 和 randPoint2 通过取 uniform distribution:

来确定

uniform_int_distribution<int> dist(0, mate[k].root->count(0) - 1);

其中mate[k]是根树指针，count定义为：

int opNode::count(int c)
{
    if(this != nullptr)
    {
        c++;
        if(lChild != nullptr)
            c += lChild->count(0);
        if(rChild != nullptr)
            c += rChild->count(0);
        return c;
    }
    return 0;
}

兑换功能：

void opNode::recombination(opNode*& secondParentNode, int& randPoint1, int& randPoint2, bool& done)
{
    if(done)
        return;
    if(secondParentNode != nullptr && !done)
    {
        if(randPoint2 > 0 && secondParentNode->lChild != nullptr)
        {
            randPoint2--;
            recombination(secondParentNode->lChild, randPoint1, randPoint2, done);
        }

        if(randPoint2 > 0 && secondParentNode->rChild != nullptr)
        {
            randPoint2--;
            recombination(secondParentNode->rChild, randPoint1, randPoint2, done);
        }
    }
    if(this != nullptr && randPoint2 == 0 && !done)
    {
        if(randPoint1 > 0 && lChild != nullptr)
        {
            randPoint1--;
            lChild->recombination(secondParentNode, randPoint1, randPoint2, done);
        }
        if(randPoint1 > 0 && rChild != nullptr)
        {
            randPoint1--;
            rChild->recombination(secondParentNode, randPoint1, randPoint2, done);
        }
    }
    if(this != nullptr && secondParentNode != nullptr && randPoint1 == 0 && randPoint2 == 0 && !done)
    {
        opNode* tmp = new opNode();
        opNode* tmp2 = new opNode();
        tmp = this->clone();
        tmp2 = secondParentNode->clone();
        this->operation = tmp2->operation;
        this->val = tmp2->val;
        this->lChild = tmp2->lChild;
        this->rChild = tmp2->rChild;
        secondParentNode = tmp;
    }
}

Answer 1

如果rChild或lChild是nullptr，那么调用rChild->clone();或lChild->clone()将导致段错误。

我们可以将函数重写为：

void opNode::clone(opNode* n)
{
    if (n)
    {
        n->val = val;
        n->operation = operation;
        if (rChild)
        {
            if (n->rChild)
            {
                 // release all right children.
            }
            n->rChild = new opNode;
            clone(n->rChild);
        }

        if (lChild)
        {
            if (n->lChild)
            {
                 // release all left children nodes.
            }
            n->lChild = new opNode;
            clone(n->lChild);
        }
    }
}

兑换代码可以简化为：

opNode* tmp = new opNode;
clone(tmp);
secondParentNode->clone(this);
tmp->clone(secondParentNode);

C++ 树指针问题

C++ Tree pointer issues

c++

binary-tree

pointers

deep-copy