Self-referential structs

[arczi w]

Hello,

I have recently faced a problem of creating the self-referential structures. Whenever I try to use them, the program behaves weirdly. Take, for instance, the code below.

#include <iostream>
using namespace std;
struct N
{
    int value;
    N *left;
    N *right;
}N;
int main()
{
    N.value = 1;
    N.right->value = 2;
    N.right->right->value = 3;
    N.right->right->right->value = 4;
    cout<<N.right->right->right->value;
    return 0;
}

If anything, it seems to decide whether to output the given value without a coherent pattern that I would recognize. Why is that?

[tpb]

You're not doing it correctly. You can't dereference right (or left) with -> (or *) when the pointer hasn't been set to point to allocated memory. You need to allocate memory for the new nodes with the "new" operator.

#include <iostream>

struct N {
    int value;
    N *left;
    N *right;
};

int main() {
    N n;

    n.value = 1;

    n.right = new N;
    n.right->value = 2;

    n.right->right = new N;
    n.right->right->value = 3;

    n.right->right->right = new N;
    n.right->right->right->value = 4;

    std::cout << n.right->right->right->value << '\n';

    // We should probably be setting all the "left" pointers of the new nodes to null since they don't point to anything.
    // And we should usually "delete" the allocated memory, but we can leave that to the OS.
}

Or you could do something like this, using a constructor for the struct.

#include <iostream>

struct Node {
    int value;
    Node* left;
    Node* right;
    
    Node(int v, Node* lf=0, Node* rt=0) : value(v), left(lf), right(rt) {}
};

void print(const Node *nd) {
    if (!nd) return;
    print(nd->left);
    std::cout << nd->value << ' ';
    print(nd->right);
}

void deleteTree(Node *nd) {
    if (!nd) return;
    deleteTree(nd->left);
    deleteTree(nd->right);
    delete nd;
}

int main() {
    Node* root = 0;   // empty tree
    /* Create tree:
            5
        3       7
      1   4   6   9
    */
    root = new Node(5,
               new Node(3,
                   new Node(1), new Node(4)),
               new Node(7,
                   new Node(6), new Node(9)));

    print(root);
    std::cout << '\n';

    deleteTree(root);
}

[arczi w]

Thank you! Much appreciated.