在递归二叉树生成中分配节点指针时出错

Question

我正在做这个项目，我应该使用随机选择的节点创建平衡二叉树，其中节点可以是数学运算符或常量。函数 createRandomNode(bool, node*) 基本上 return 是一个随机选择的节点。

问题是，当我运行这段代码在 VS 中时，它可以运行非常好。但是，当我将其移至 Ubuntu 时，在 else 段中执行 return retFtn 时，指向 returned 节点的指针值会发生变化。

因此，例如在 VS 中，树基本上如下所示，我使用存储在指针中的地址来表示每个节点：

                             0x0543b
                            /       \
                      0x0544c       0x0456d
                     /       \     /       \
                 0x0342d  0x0453c 0x665f  0x893a

对于每个节点，我在VS中运行ning的时候可以查看它的值和标签。然而，当运行ning in Ubuntu 时，0x0453c 的时刻被 returned 并且递归函数 returns 到 retFtn->right（其中 retFtn 现在是 0x0543b，因为 0x0544c 已经已完成），0x0544c 更改为一些奇怪的地址，我无法再看到该节点的值和标签，尽管在 0x0453c 被 returned 之前我仍然可以看到它。

下面是有问题的代码。

node* createRandomTree(int depth, node* parent)
{
    if (depth > 1)
    {
        node* retFtn = createRandomNode(true, parent);
        retFtn->left = createRandomTree(depth - 1, retFtn);
        retFtn->right = createRandomTree(depth - 1, retFtn);
        if (retFtn->parent == NULL)
            return retFtn;
    }
    else
    {
        node* retFtn = createRandomNode(false, parent);
        return retFtn;
    }
}

希望我已经解释清楚了，谢谢您的帮助！ :)

/******************************************** *******************************/ 编辑：

下面是一个最小的、完整的、可验证的示例，它可以重现 Ubuntu 16.04 中的问题（奇怪的是，在 VS 中运行ning 时不会出现该问题）：

main.cpp:

#include "node.h"
#include "random.h"
#include <iostream>
int main(int argc, char * const argv[])
{
    node* createdTree = createRandomTree(3, NULL);
    std::cout << createdTree << endl;
    inOrder(createdTree);
}

random.cpp:

#include "random.h"

void inOrder(node* tree)
{
    if (!tree)
        return;
    cout << "(";
    inOrder(tree->left);
    cout << tree->label;
    inOrder(tree->right);
    cout << ")";
}

node* createRandomTree(int depth, node* parent)
{
    if (depth > 1)
    {
        node* retFtn = createRandomNode(true, parent); //isOperator==true
        retFtn->left = createRandomTree(depth - 1, retFtn);
        retFtn->right = createRandomTree(depth - 1, retFtn);
        if (retFtn->parent == NULL)
            return retFtn;
    }
    else
    {
        node* retFtn = createRandomNode(false, parent); //isOperator==true
        return retFtn;
    }
}

node* createRandomNode(bool isOperator, node* parent)
{
    int randn = -1;
    node* retFtn = NULL;

    if (isOperator)
        randn = 1;
    else
        randn = 0;

    switch (randn)
    {
        case 0:
        {
            retFtn = new ConstantValueNode(parent);
            break;
        }
        case 1:
        {
            retFtn = new AddNode(parent);
            break;
        }
        default:
        {
            cout << "invalid random number\n\n\n";
            break;
        }
    }
    return retFtn;
}

random.h

#ifndef random_H
#define random_H

#include "node.h"

node* createRandomNode(bool isOperator, node* parent);
node* createRandomTree(int depth, node* parent);
void inOrder(node* tree);
#endif

node.cpp:

#include "node.h"

/***************/
/*Constant Node*/
/***************/
ConstantValueNode::ConstantValueNode(node* retFtn)
{
    left=NULL;
    right=NULL;
    negate_Or_Not = false;
    constVal = rand()% 21 + (-10);
    key_value = constVal;
    parent = retFtn;
    label = "Constant";
};

ConstantValueNode::ConstantValueNode(double preSetVal)
{
    left=NULL;
    right=NULL;
    negate_Or_Not = false;
    constVal = preSetVal;
    key_value = constVal;
    label = "Constant";
};

double ConstantValueNode::eval(map<string,double> inputMapping)
{
    if (negate_Or_Not) //negation is true
        return !constVal;
    else
        return constVal;
}

ConstantValueNode* ConstantValueNode::clone(node* parent_clone)
{
    ConstantValueNode* retTree = new ConstantValueNode(key_value);
    if (parent_clone != NULL)
        retTree->parent = parent_clone;
    else
        retTree->parent = NULL;
    return retTree;
}

string ConstantValueNode::getLabel()
{
    return label;
}

/**********/
/*Add Node*/
/**********/
AddNode::AddNode()
{
    label = "AddNode";
    negate_Or_Not = NULL; //will be false by default
}
AddNode::AddNode(node* retFtn)
{
    label = "AddNode";
    negate_Or_Not = NULL;
    parent = retFtn;
}
double AddNode::eval(map<string,double> inputMapping)
{
    if (left && right)
        return left->eval(inputMapping) + right->eval(inputMapping);
    else
    {
        cout << "left and right not defined in add"<<endl;
        return -1.0;
    }
}

AddNode* AddNode::clone(node* parent_clone)
{
    AddNode* retNode = new AddNode();
    retNode->left = left->clone(retNode);
    retNode->right = right->clone(retNode);
    if (parent_clone != NULL)
        retNode->parent = parent_clone;
    else
        retNode->parent = NULL;
    return retNode;
}

string AddNode::getLabel()
{
    return label;
}

node.h:

#ifndef Node_H
#define Node_H
#include<iostream>
#include<map>

using std::string; //This will allow you to use "string" as an unqualified name
                  //(resolving to "std::string")
using std::cout;
using std::endl;
using std::map;

class node
{
    // Virtual function can be overriden and the pure virtual must be implemented.
    // virtual void Function() = 0; is a pure virtual. The "= 0" indicates is purity
    public:
        bool negate_Or_Not;
        string label;
        int key_value;
        node* left;
        node* right;
        node* parent;
        virtual double eval(map<string,double> inputMapping)=0;
        virtual node* clone(node* clone)=0;
        virtual string getLabel()=0;
};

class ConstantValueNode : public node
{
    double constVal;
    public:
        ConstantValueNode(node* retFtn);
        ConstantValueNode(double preSetVal);
        virtual double eval(map<string,double> inputMapping);
        virtual ConstantValueNode* clone(node* clone);
        virtual string getLabel();
};

class AddNode : public node
{
    public:
        AddNode();
        AddNode(node* retFtn);
        virtual double eval(map<string,double> inputMapping);
        virtual AddNode* clone(node* clone);
        virtual string getLabel();
};
#endif

生成文件：

CXX = g++
CXXFLAGS = -Wall -std=c++11
# ****************************************************
main: main.o node.o random.o
    $(CXX) $(CXXFLAGS) -o main main.o node.o random.o

main.o: main.cpp node.h random.h
    $(CXX) $(CXXFLAGS) -c main.cpp

node.o: node.h 
random.o: node.h random.h

Answer 1

如果您使用 depth>1 和 parent!=NULL 调用 createRandomTree(int depth, node* parent)，此函数不会命中任何 return 语句。所以 createRandomTree 一直执行到最后，然后控制权返回给调用者，没有提供保证的 return 值。因此 createRandomTree(3, NULL); 导致 retFtn->left = createRandomTree(3 - 1, retFtn); 结果是随机垃圾被写入 retFtn->left。

我强烈建议您多注意编译器警告：

random.cpp:29:1: warning: control reaches end of non-void function [-Wreturn-type]

PS 你可能会好奇为什么它在 VS 上运行。不知道确切的原因（可以通过检查汇编代码来调查，但我现在没有环境也不想深入研究），但一般的答案是"by chance"。我看到两种可能的方式：

编译器丢弃了 if (retFtn->parent == NULL) 检查，因为它无用（不改变任何东西）且代价高昂（由于 CPU 传送带架构，分支会减慢执行速度）
有很多calling conventions，指定了将return值传递给调用者的方式。最快的是通过 CPU 寄存器传递值。我可以想象这种情况，当 retFtn 存储在 CPU 寄存器中用于函数内的计算和函数退出时，它看起来好像 retFtn 是 returned。我在 MIPS 架构上有类似的案例。

请随时检查确切原因并与我们分享。

在递归二叉树生成中分配节点指针时出错

error in allocating pointer of node in recursive binary tree generation

c++

ubuntu

recursion

binary-tree

pointers