пытаясь напечатать вид сверху бинарного дерева, используя предзаказ

Question

ниже двух кодов должны работать одинаково, но давать разные выходные данные.Я пытался отладить код как можно лучше, но не смог найти ошибку.

CODE1: -

#include<iostream>
#include<stack>
#include<map>

using namespace std;

struct node {
    int data;
    struct node* left;
    struct node* right;
};

typedef struct label
{
    struct node* root;
    int disp;
}label;

int main() {

    struct node* n1 = (struct node*) malloc(sizeof(struct node));
    struct node* n2 = (struct node*) malloc(sizeof(struct node));
    struct node* n3 = (struct node*) malloc(sizeof(struct node));
    struct node* n4 = (struct node*) malloc(sizeof(struct node));
    struct node* n5 = (struct node*) malloc(sizeof(struct node));
    struct node* n6 = (struct node*) malloc(sizeof(struct node));
    struct node* n7 = (struct node*) malloc(sizeof(struct node));
    struct node* n8 = (struct node*) malloc(sizeof(struct node));
    struct node* n9 = (struct node*) malloc(sizeof(struct node));
    struct node* n10 = (struct node*) malloc(sizeof(struct node));
    struct node* n11 = (struct node*) malloc(sizeof(struct node));
    struct node* n12 = (struct node*) malloc(sizeof(struct node));
    struct node* n13 = (struct node*) malloc(sizeof(struct node));
    n1->data = 1;
    n2->data = 2;
    n3->data = 3;
    n4->data = 4;
    n5->data = 5;
    n6->data = 6;
    n7->data = 7;
    n8->data = 8;
    n9->data = 9;
    n10->data = 10;
    n11->data = 11;
    n12->data = 12;
    n13->data = 13;
    n1 -> left = n2;
    n1 -> right = n3;
    n2 -> left = n4;
    n2 -> right = n5;
    n4 -> left = n4 -> right = NULL;
    n5 -> left = n5 -> right = NULL;
    n3 -> left = n6;
    n3 -> right = n7;
    n6 -> left = n6 -> right = NULL;
    n7 -> left = n8;
    n7 -> right = NULL;
    n8 -> left = n9;
    n8 -> right = NULL;
    n9 -> left = n10;
    n9 -> right = NULL;
    n10 -> left = n11;
    n10 -> right = NULL;
    n11 -> left = n12;
    n11 -> right = NULL;
    n12 -> left = n13;
    n12 -> right = NULL;
    n13 -> left = NULL;
    n13 -> right = NULL;



    node* root = n1;

    stack<label*> s;
    map<int, int> m;

    label* var = new label();
    var -> root = root;
    var -> disp = 0;

    label* var1 = new label();

    s.push(var);

    while(!s.empty()) {
        m.insert( pair <int, int> ( var -> disp, var -> root -> data) );

        s.pop();
        if( var -> root -> right != NULL ) {
            var1 -> root = var -> root -> right;
            var1 -> disp = var -> disp + 1;
            s.push(var1);

        }
        if( var -> root -> left != NULL ) {
            var1 -> root = var -> root -> left;
            var1 -> disp = var -> disp - 1;
            s.push(var1);

        }
        if(!s.empty()) {

            var -> root = s.top() -> root;
            var -> disp = s.top() -> disp;
        }
    }
    map<int, int> :: iterator itr;
    for( itr = m.begin(); itr != m.end(); itr++ ) {
        cout<< itr -> second << endl;
    }

}

CODE2: -

#include<iostream>
#include<stack>
#include<map>

using namespace std;

struct node {
    int data;
    struct node* left;
    struct node* right;
};

typedef struct label
{
    struct node* root;
    int disp;
}label;

int main() {

    struct node* n1 = (struct node*) malloc(sizeof(struct node));
    struct node* n2 = (struct node*) malloc(sizeof(struct node));
    struct node* n3 = (struct node*) malloc(sizeof(struct node));
    struct node* n4 = (struct node*) malloc(sizeof(struct node));
    struct node* n5 = (struct node*) malloc(sizeof(struct node));
    struct node* n6 = (struct node*) malloc(sizeof(struct node));
    struct node* n7 = (struct node*) malloc(sizeof(struct node));
    struct node* n8 = (struct node*) malloc(sizeof(struct node));
    struct node* n9 = (struct node*) malloc(sizeof(struct node));
    struct node* n10 = (struct node*) malloc(sizeof(struct node));
    struct node* n11 = (struct node*) malloc(sizeof(struct node));
    struct node* n12 = (struct node*) malloc(sizeof(struct node));
    struct node* n13 = (struct node*) malloc(sizeof(struct node));
    n1->data = 1;
    n2->data = 2;
    n3->data = 3;
    n4->data = 4;
    n5->data = 5;
    n6->data = 6;
    n7->data = 7;
    n8->data = 8;
    n9->data = 9;
    n10->data = 10;
    n11->data = 11;
    n12->data = 12;
    n13->data = 13;
    n1 -> left = n2;
    n1 -> right = n3;
    n2 -> left = n4;
    n2 -> right = n5;
    n4 -> left = n4 -> right = NULL;
    n5 -> left = n5 -> right = NULL;
    n3 -> left = n6;
    n3 -> right = n7;
    n6 -> left = n6 -> right = NULL;
    n7 -> left = n8;
    n7 -> right = NULL;
    n8 -> left = n9;
    n8 -> right = NULL;
    n9 -> left = n10;
    n9 -> right = NULL;
    n10 -> left = n11;
    n10 -> right = NULL;
    n11 -> left = n12;
    n11 -> right = NULL;
    n12 -> left = n13;
    n12 -> right = NULL;
    n13 -> left = NULL;
    n13 -> right = NULL;



    node* root = n1;

    stack<label*> s;
    map<int, int> m;

    label* var = new label();
    var -> root = root;
    var -> disp = 0;


    s.push(var);

    while(!s.empty()) {
        m.insert( pair <int, int> ( var -> disp, var -> root -> data) );
        s.pop();
        if( var -> root -> right != NULL ) {
            label* var1 = new label();
            var1 -> root = var -> root -> right;
            var1 -> disp = var -> disp + 1;
            s.push(var1);   
        }
        if( var -> root -> left != NULL ) {
            label* var2 = new label();
            var2 -> root = var -> root -> left;
            var2 -> disp = var -> disp - 1;
            s.push(var2);
        }
        if(!s.empty()) {
            var -> root = s.top() -> root;
            var -> disp = s.top() -> disp;
        }
    }
    map<int, int> :: iterator itr;
    for( itr = m.begin(); itr != m.end(); itr++ ) {
        cout<< itr -> second << endl;
    }

}

Код 2 дает правильный вывод, а код 1 - нет.В Code2 создаются две локальные переменные метки, а в Code1 создается одна локальная переменная метки и значения переопределяются.

Answer 1

Немного не по теме, но вы можете просто выделить все узлы в стеке, не нужно здесь malloc / new.Пример:

struct node {
    int data;
    struct node* left;
    struct node* right;
};

int main() {
    node a{1};
    node c{3};
    node b{2, &a, &c};
}

Answer 2

Вы говорите, что в CODE2 вы создаете 2 локальные переменные.Хотя технически вы правы, я думаю, что есть некоторое недопонимание:

Глядя на строку

label* var1 = new label();

в вашем цикле: вы создаете локальную переменную, и данные в куче (память, которую вы выделяете через new label()).Эта память остается там даже на следующей итерации.

Затем вы помещаете указатель на эту выделенную память в свой стек.Вы, вероятно, думаете, что содержимое выделенной памяти копируется / помещается в стек.Это неправда.В стек копируется копия указателя в память .Выделенная память никак не затрагивается.

Поскольку в CODE2 новая память выделяется при каждой итерации цикла, указатели в стеке указывают на отдельные области памяти (различные экземпляры)вашей label struct).

В CODE1 вы не создаете память каждый раз, а просто выделяете один раз и повторно используете одну и ту же ячейку памяти в каждой итерации.

Вы помещаете указатель (в var1) в это место в стек, но, поскольку он всегда один и тот же указатель, все указатели в стеке указывают на один и тот же адрес памяти (один и тот же экземпляр вашей структуры label)).

Всякий раз, когда вы делаете

var1 -> root = var -> root -> right;
var1 -> disp = var -> disp + 1;

Поскольку var1 всегда указывает на одну и ту же память, вы просто перезаписываете одно и то же местоположение снова и снова.

Чтобы предложить простой аналог:

Это похоже на то, что когда вы делаете var1 = new label(), вы берете новую коробку, пометьте ее номером.Вы удаляете все, что там есть, а затем помещаете в него новые вещи.Когда вы нажимаете на стек, это похоже на то, как вы записываете это число в список чисел.

В CODE2 вы берете пустое поле new в каждой итерации, помечаете еговведите новый номер, а затем запишите новый номер в свой список на листе бумаги.

В КОДЕ 1, у вас есть только ONE коробка.В каждой итерации вы снова берете этот блок, удаляете то, что вставляете туда, добавляете что-то новое и добавляете номер блока - один и тот же номер каждый раз - в список на вашем листе бумаги.

Конечно, это поле всегда содержит только то, что вы добавили в него в последней итерации.Все остальные вещи, которые вы вставили в него итерациями ранее, потеряны, потому что вы заменили его.

Еще одна, хотя и в этом случае, небольшая проблема заключается в том, что вы никогда не освобождаете выделенную память.В этом случае это не имеет большого значения, так как после завершения процесса память все равно будет освобождена, но это плохой навык, который в более сложных программах приведет к утечкам памяти и окончательному завершению процесса.