Ошибка в распределении указателя узла в генерации рекурсивного двоичного дерева

Question

Я делаю этот проект, где я должен создать сбалансированное двоичное дерево, используя случайно выбранные узлы, где узел может быть математическим оператором или константой. Функция createRandomNode (bool, node *) в основном возвращает случайно выбранный узел.

Дело в том, что когда я запускаю этот фрагмент кода в VS, он может работать отлично. Однако, когда я передаю его Ubuntu, значение указателя на возвращаемый узел изменяется, когда return retFtn выполняется в сегменте else.

Так, например, в VS, то дерево будет в основном выглядеть, как показано ниже, где я использовал адрес, сохраненный в указателе для представления каждого узла:

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

Для каждого узла, можно просмотреть его значение и метка при работе в VS. Однако при запуске в Ubuntu возвращается момент 0x0453c, и рекурсивная функция возвращается в retFtn-> right (где retFtn теперь 0x0543b, так как 0x0544c уже завершен), 0x0544c изменяется на какой-то странный адрес, и я больше не могу видеть значение этого узла и ярлык, хотя я все еще вижу его до возврата 0x0453c.

Ниже приведен код.

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; 
    } 
} 

Надеюсь, я ясно объяснил, спасибо вам за помощь!)

/******************************************* *****************************/ EDIT:

Ниже приведен минимальный, полный и проверенный пример, который может воссоздать проблема в Ubuntu 16.04 (странно, проблема не возникает при работе в VS):

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 

Makefile:

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

Если вы звоните createRandomTree(int depth, node* parent) с depth>1 и parent!=NULL, эта функция не попадает в инструкцию return. Таким образом, createRandomTree выполняется до конца, тогда управление передается обратно вызывающему абоненту без гарантированного возвращаемого значения. Таким образом, createRandomTree(3, NULL); приводит к retFtn->left = createRandomTree(3 - 1, retFtn);, где случайный мусор записывается в retFtn->left.

я настоятельно рекомендую вам обратить больше внимания на предупреждения компилятора:

случайным образом.каст: 29: 1: предупреждение: управление достигает конца Непустой функции [-Wreturn типа]

---

PS Вы могли бы быть insterested почему, черт возьми, это работает на VS. Не знаю точной причины (его можно исследовать, проверяя ассемблерный код, но у меня нет окружения и не хочу в него копаться прямо сейчас), но общий ответ «случайно». Я вижу два возможных пути:

1. компилятор выкинул if (retFtn->parent == NULL) проверку в бесполезный (ничего не меняет) и дорогостоящую (разветвление замедляет выполнение за счет процессора конвейерной архитектуры)
2. Есть много calling conventions, которые определяют способ передачи возвращаемого значения вызывающему абоненту. Самый быстрый - это передача значения через регистры CPU. Я могу представить себе ситуацию, когда retFtn хранится в регистре CPU для расчетов внутри функции и при выходе из функции выглядит так, как если бы возвращалось retFtn. У меня был аналогичный случай в архитектуре MIPS.

Не стесняйтесь уточнить причину и поделиться с нами.