Input elements in n-Ary tree using Level order

Question

Given structure:

struct node {
int data;
struct node *next;
struct node *child;
};

How can I add elements in n-Ary tree level by level? The reason behind this is that I want to make my tree complete or nearly complete.

Could use any form of help, hint, suggestion.

User will input number n, which means that every node can have that many children, not greater than that. The problem is, I only know to add root and first n elements after. I am not sure how to get back to the first element after root, so that I can now put other nodes as his children and so on.

Root -> NULL
 |
 V
Child-1.1 -> Child-1.2 -> ... -> Child-1.n -> NULL
 |              |                   |            
 |              V                   V
 |              ...              Child-1.n.1 -> ... -> NULL
 V
Child-1.1.1 -> Child-1.1.2 -> ... -> NULL
 |
 ... etc

We are not doing your homework. Also the last } is out of the code. — prgrm
How does binaryTreeNode* temp = Q -> front -> data; work exactly? — Henk Holterman
My goal was to make complete or nearly complete binary complete tree directly from user input given number of nodes, that's why I used Lever Order. Now, I want to do the same thing but this time, user can input how many children will each node have, that why it's n-ary type. — Kospet

Sorin Sorin · Accepted Answer · 2018-04-10T12:32:27

In your code you check left and right children because you only have two:

if(temp -> left != NULL){
    Q = insertQ(Q, temp -> left);
}
else{
    temp -> left = newNode;
    free(Q);
    return root;
}

if(temp -> right != NULL){
    Q = insertQ(Q, temp -> right);
}
else{
    temp -> right = newNode;
    free(Q);
    return root;
    }
}

What you need to do now is iterate using the next pointer and make sure you reach n. Something like:

for (int i = 1 ; i < n; ++i, temp = temp->next) {
  if (temp->child) Q = insertQ(Q, temp->child);
  if (!(temp->next) && i < n-1) {
    // You don't have n nodes yet, so add the padding.
    temp->next = new Node;
  }
}

Input elements in n-Ary tree using Level order

1 Answers