-1

I want to write a tree data structure made up of Nodes, but I'm having a problem with my Node.h class as each Node need to have a reference Variable to other Nodes,it's children. which ends up giving me the following error

"field 'child' has incomplete type"

so I thought to myself if I was to #include "Node.h" within my Node.h class which gave another error

"#include nested too deeply

how can I have reference to my child Nodes within my node class

3
  • With a forward declaration. – Ignacio Vazquez-Abrams Jun 17 '16 at 11:52
  • thanks, I'm new to c++ so i didn't know that . anyways, i define my child node as Node* child; is this correct? – Raed Jun 17 '16 at 12:04
  • Yes node* is a pointer. Always make sure you initialise a pointer to NULL though, and check to see if it is NULL before you do anything to it. And don't forget to free the memory when you have finished with it. And never mix new/malloc and delete/free – Code Gorilla Jun 17 '16 at 12:08
0

You will need to forward declare the class and add a pointer to it from within the class. i.e.

class CElement;  // Forward declaration

class CElement
{
public:
    CElement();
    ... // Other functions
private:
    CElement *m_NextElement;
};

Just to be clear you can't have your class as a member variable, it has to be a pointer or a reference. This is because:

  1. You can't use a type that hasn't been fully defined.
  2. You would end up with your class consuming an infinite amount of memory, because every node would contain a node, which contains a node, etc...
7
  • You don't actually need to pre-declare the class the way you did on your first line: the class CElement is known about by the time the compiler gets to the CElement *m_NextElement; line – John Burger Jun 17 '16 at 13:10
  • 1
    Also, check your "Just to be clear" line: you say "you can have your class as a member variable" - you mean "you can't". If you want you can have it as a reference - you imply you can't. – John Burger Jun 17 '16 at 13:11
  • @Matt thanks, I added the forward declaration to my Node class. while i did manage to solve this I'm having a lot of trouble understanding when to use * or -> and new keyWord – Raed Jun 17 '16 at 14:22
  • @JohnBurger - Thanks, good spot. My fingers were traveling faster than my brain. Hopefully corrected them now. – Code Gorilla Jun 17 '16 at 14:30
  • @Matt Why do you think you can't have it as a reference? It may not be useful (in this instance), but it's certainly legal. – John Burger Jun 17 '16 at 14:33
0

If you have a class like this:

class Node {

public: // Methods

    inline Node() :
           left(nullptr),   // No children yet!
           right(nullptr) {
    } // Node()

public: // Variables (normally this should be private, but for this example...)

    Node *left;
    Node *right;

}; // Node

Node root; // The root of the tree

You now have a class that has two members, both pointers to Nodes. Obviously there's going to be more data in there - strings or whatever - but let's ignore that for now.

I've also created the root of the tree - note that I didn't use new! It's a file variable that is always accessible, and there's not an * in sight (except inside root...).

What are left and right? Pointers to the children. They are not the children: just pointers to them. As soon as any Node is created (after the constructor has finished), the Node has no children - both pointers are nullptr.

So (ignoring any attempt to sort the children into place) you could now do the following:

void AddChildren() {
    Node sister;           // Create a sister
    Node brother;          // Create a brother
    root.left = &sister;   // Point to sister
    root.right = &brother; // Point to brother
} // AddChildren()

Note you couldn't do node.left = sister; - you're not trying to put sister inside root, you're only trying to point to sister with one of root's children. So you take sister's address with the & operator.

Only... as soon as AddChildren() exits, both sister and brother are destroyed (they're local to the function, so get destroyed as the function leaves) - but root is still pointing to where they used to be! It doesn't know that they are dead!

That is why you call new. It creates the object on the heap rather than the stack, and the object stays around until explicitly destroyed with delete. Only, new returns a pointer to the object, not the object itself. So:

void AddChildren() {
    Node *sister = new Node();  // Point to new object on the heap
    Node *brother = new Node(); // Point to new object on the heap
    root.left = sister;         // Already a pointer! Just copy it
    root.right = brother;       // Already a pointer! Just copy it
} // AddChildren()

Or, perhaps easier:

void AddChildren() {
    root.left = new Node();  // Point to new object on the heap
    root.right = new Node(); // Point to new object on the heap
} // AddChildren()

Now, how do you access the different fields inside Node? It depends on whether you're accessing them through an object or through a pointer:

  • Through an object?
    With ., like root.left above
  • Through a pointer?
    Using ->, such as ptr->left

So finally, how can you use it for real?

// TraverseTree is going to call a function that looks like this:
typedef void TraverseFn(const Node &node);

// Traverse a (sub)tree, calling the passed-in fn() on each Node.
void TraverseTree(Node *node, TraverseFn *fn) {
    if (node == nullptr) { // Nothing to traverse!
        return;
    } // if
    TraverseTree(node->left, fn);  // Trees love recursion!
    fn(*node);                     // Call the passed-in fn with node
    TraverseTree(node->right, fn); // More recursion!
} // TraverseTree(Node)

And you can call the above with:

// A function to print the contents of Node
void PrintNode(const Node &node);

// Traverse the whole Tree, from root, calling PrintNode at each Node
TraverseTree(&root, &PrintNode);

Beware! Do not pass! Here be dragons!

(or at least pointers to member functions...)

Personally, I would have put TraverseTree() inside Node:

class Node {

public: // Methods to call with Traverse()

    // Print this Node
    void Print();

public: // Traverse

    // This is the type of the function that Traverse will call
    typedef void TraverseFn();

    // Note we're passing in a pointer-to-member-function!
    void Traverse(TraverseFn Node::*fn) {
        if (left != nullptr) {
            left->Traverse(fn);
        } // if
        (this->*)fn();
        if (right != nullptr) {
            right->Traverse(fn);
        } // if
    } // Traverse(fn)

}; // Node

If you do that, you'd print out the tree like this:

root.Traverse(&Node::Print);

Not the answer you're looking for? Browse other questions tagged or ask your own question.