N-ary Tree implementation: cannot convert 'Tree::node*' to 'node*' in assignment

Question

I am trying to make a n-ary tree with a List of Lists implemented with pointers, this is my implementation of my Tree:

class Tree{
public:

struct nodeSon{
    struct node* node_ptr;
    nodeSon* nextNodeSon_ptr;
};

struct node{
    char label;
    node* nextNode_ptr;
    struct nodeSon* nSon;
};

node* root;

void AddSon(int i, node n, char l); //Adds a son with label l to n at i position
};

The problem happens when I try to implement Tree::AddSon():

void Tree::AddSon(int i, nodo n, char l){

node* nextPtr = root->nextNode_ptr;
node* newNode = new node();
newNode->label= l;
root->nextNode_ptr = newNode;
newNode->nextNode_ptr = nextPtr;

node* it = root;
while (it != &n) {
    it = it->nextNode_ptr;
}

nodeSon* it2 = it->nSon;
int counter = 1;
while (contador != i) {
    it2 = it2->sigNodoHijo_ptr;
}
nodeSon* nextPtrNH = it2->nextNodeSon_ptr;
nodeSon* newNodeNH = new nodeSon();
newNodeNH->node_ptr = newNodo; //error indication at this line
it2 = newNodeNH;
newNodoNH->nextNodeSon_ptr = nextPtrNH;
.
.
.
}

I receive this error when I try to build it:

Tree.cpp:110:27: error: cannot convert 'Tree::node*' to 'node*' in assignment

---

• Why does this happen?
• How do I solve the problem?

Answer 1

The Problem

class Tree{
  public:

    struct nodeSon{
      struct node* node_ptr;    // (1)
      nodeSon* nextNodeSon_ptr;
    };
};

At (1) you are basically telling the compiler that node_ptr shall point towards a type that you have not yet defined, but that the definition of this type will be available at a later time.

The problem is that the compiler cannot assume that this type resides within class Tree—since you have not said that this is the case—instead it will assume that struct node refers to a type in the global namespace.

When you later declare a type named node inside class Tree it is already too late; the type of Tree::nodeSon::node_ptr will not change just because a more (from our perspective) suitable type has become available.

---

Example

We can reproduce your error with the following, much reduced, testcase.

struct A {
  struct B {
    struct C * ptr;
  };

  struct C { };
};

struct C { };

int main () {
  A::B x;
  A::C y;
  C    z;

  x.ptr = &y; // error,  `y` is of type `A::c`
  x.ptr = &z; // ok,     `z` is of type `::C`
}

---

The Solution

You will need to tell the compiler that there will exist a type named node in Tree by forward-declaring it, prior to writing the definition of Tree::nodeSon.

class Tree{
  public:
    struct node; // forward-declare Tree::node

    struct nodeSon{
      struct node* node_ptr;
      nodeSon* nextNodeSon_ptr;
    };

    struct node{
      char label;
      node* nextNode_ptr;
      struct nodeSon* nSon;
    };

    node* root;

    void AddSon (int i, node n, char l); //Adds a son with label l to n at i position
};