Ошибки с указателями

Question

Я работал над простым бинарным деревом поиска для более крупного проекта. Я понимаю концепцию бинарного дерева поиска и просто испытываю проблемы с синтаксисом реализации в C ++. Я намеренно не использую контейнеры дерева наддува. Мой код для дерева выглядит следующим образом.

  struct Tree{
int nodeValue;
Tree *nodeChild1;
Tree *nodeChild2;
Tree(int userProvidedValue){
    nodeValue = userProvidedValue;
    nodeChild1 = NULL;
    nodeChild2 = NULL;
}
static void placeValue(Tree &parent, int value);
static Tree findValue(Tree parent, int value);
static void crawl(Tree parent);
~Tree(){

    delete nodeChild1;
    delete nodeChild2;
}
};

 void Tree::placeValue(Tree &parent, int value){
Tree node = Tree(value);
cout<<"made node"<<endl;
if(value>parent.nodeValue){
    cout<<"eval node child 2"<<endl;
    if(parent.nodeChild2 ==NULL){
        cout<<"reaching this";
        parent.nodeChild2 = &node;
    }
    else{
        placeValue(*parent.nodeChild2, value);
    }
}
if(value<=parent.nodeValue){
    cout<<"eval node child 1"<<endl;
    if(!parent.nodeChild1){
                cout<<"assigning"<<endl;
                parent.nodeChild1 = &node;
    }
            else{
                        placeValue(*parent.nodeChild1, value);
            }
        }
}

Однако всякий раз, когда я строю дерево с Tree parent = Tree(5), затем добавляю к нему еще один узел с Tree::placeValue(parent, 4), он прекрасно компилируется, но появляется сообщение о том, что исполняемый файл аварийно завершился.

Может кто-нибудь помочь мне понять, откуда происходит этот сбой? Заранее спасибо.

Код для обхода дерева выглядит так:

void Tree::crawl(Tree parent){
cout<<parent.nodeValue<<endl;
if(NULL!=parent.nodeChild1){
    crawl(*parent.nodeChild1);
}
if(NULL!=parent.nodeChild2){
    crawl(*parent.nodeChild2);
}
}

Дополнительный вопрос: Когда Tree :: crawl принимает аргумент Tree & parent вместо Tree parent, он работает нормально. Однако без & однако это не удается. Может кто-нибудь объяснить, почему это так?

Answer 1

Вы должны разместить дерево (и) в куче.

Tree node = Tree(value);

Здесь вы размещаете дерево в стеке. Адрес этой переменной будет удален после выхода из области видимости. Чтобы разместить его в куче, просто используйте новый оператор:

Tree *node = new Tree(value);

А затем назначьте его дочерним по отношению к родителю:

parent.nodeChild2 = node;

Что касается ошибки Tree :: crawl, она основана на той же ошибке. Вы продолжаете размещать Tree (и) в стеке, поэтому, как только он выходит из области видимости, вызывается его деструктор, delete (ing) nodeChild1 и nodeChild2. Вы должны управлять такими структурами, используя либо указатели, либо всегда используя ссылки, чтобы после завершения функции деструктор Дерева не вызывался. Поэтому:

void Tree::crawl(const Tree &parent){
  cout<<parent.nodeValue<<endl;
  if(NULL!=parent.nodeChild1){
      crawl(*parent.nodeChild1);
  }
  if(NULL!=parent.nodeChild2){
      crawl(*parent.nodeChild2);
  }
}

Это должно сделать это. Не забудьте сделать то же самое для Tree :: findValue, вы должны использовать эту сигнатуру для этой функции:

static Tree findValue(const Tree &parent, int value);

Answer 2

Вы выделяете свой Tree() экземпляр, содержащий новое значение в стеке, т.е. Tree node = Tree(value);.Когда вызов функции возвращается, этот экземпляр уничтожается, поэтому при попытке доступа к нему позже происходит сбой программы.

Кроме того, ваш деструктор вызывает delete для обоих дочерних элементов, поэтому, вероятно, вам следует выделитьTree экземпляр в куче, чтобы исправить вашу проблему: Tree* node = new Tree(value);

Answer 3

Tree node = Tree(value);

node имеет область действия программного блока, в котором он был объявлен. Он будет автоматически удален после выхода из Tree::placeValue.Когда вы получите указатель на него (parent.nodeChild2 = &node;), он будет указывать на ничто после выхода и попытаться разыменовать это приведет к неопределенному поведению.Создайте его динамически, как это:

Tree * node = new Tree(value);