尝试使用预购打印二叉树的顶视图

Question

下面的两个代码应该以相同的方式工作，但给出不同的输出。我尝试尽我所能调试代码，但找不到错误。

代码 1:-

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

}

代码 2:-

#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

你说，在 CODE2 中你创建了 2 个局部变量。从技术上讲，你是对的，我想有一些误解：

查看行

label* var1 = new label();

在你的循环中：您在堆上创建了一个 local 变量，and 数据（您通过 new label() 分配的内存）。即使在下一次迭代中，此内存也会保留在那里。

然后将指向该分配内存的指针推入堆栈。您可能认为您分配的内存内容是 copied/pushed 到堆栈上。这不是真的。复制到堆栈上的是 指向内存 的指针的副本。分配的内存不会以任何方式被触及。

由于在 CODE2 中每次迭代循环时都会分配新内存，因此堆栈上的指针指向 distinct 内存区域（label 的不同实例结构）。

在 CODE1 中，您不会每次都创建内存，而只是分配一次并在每次迭代中重复使用相同的内存位置。

你把指向这个位置的指针（在var1）压入栈中，但是因为它总是同一个指针，所以栈上的所有指针都指向同一个内存地址（同一个实例你的 label 结构）。

每当你做你的

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

因为var1总是指向同一个内存，你只需一遍又一遍地覆盖相同的位置。

提供一个简单的类比：

这就像每当你做一个 var1 = new label() 你拿一个新盒子，用一个数字标记它。您删除其中的任何内容，然后将新内容放入其中。当您压入堆栈时，就像您将这个数字写到数字列表中一样。

在 CODE2 中，你在每次迭代中取一个 new 空盒子，用 new 数字标记它，把你的东西放进去，然后在 sheet 纸上的列表中写下新号码。

IN CODE1 ，你只有 ONE 框。在每次迭代中，你再次拿起这个盒子，移除你放在那里的东西，放入新的东西，然后将盒子的编号 - 每次相同的编号 - 添加到你 sheet 纸上的列表中。

当然，此框始终只包含您在上一次迭代中放入的内容。您在迭代之前放入其中的所有其他内容都丢失了，因为您替换了它。

另一个小问题是您永远不会释放分配的内存，尽管是在这种情况下。在这种情况下这无关紧要，因为在进程终止时无论如何都会释放内存，但这是一个坏习惯，在更复杂的程序中会导致内存泄漏和最终进程终止。

Answer 2

有点跑题了，不过可以简单的分配栈上的所有节点，这里不需要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};
}

尝试使用预购打印二叉树的顶视图

trying to print top view of binary tree using pre-order

c++

binary-tree

data-structures