Originally Posted by
kr0n1x
I found a way to implement it with a queue.
I should make the code better (at least the level_insert() function), but I'll post it anyway just for someone who could need it.
Tree level insert with a queue:
[C] level_insert - Pastebin.com
Thanks for posting your solution; let's just move that into the page so we don't loose that link in the future.
Code:
#include <stdio.h>
#include <stdlib.h>
/* this is going to contain the queue, made of pointers to tree's nodes */
struct queue {
struct node *pointer;
struct queue *next;
};
/* this represents the tree's nodes */
struct node {
int inf;
struct node *left;
struct node *right;
};
void level_insert(struct node **); // enter a new node into the tree keeping it a "complete tree"
void inQueue(struct queue **, struct queue **, struct node *); // push a node into the queue
struct node *outQueue(struct queue **, struct queue **); // pop a node out of the queue
void preorder(struct node *); // tree's preorder visit (just for test purpose)
void level_visit(struct node *); // tree's level visit
int main(void) {
struct node *Tree = NULL;
int i;
/* I'm making the tree this way to be sure it's made how I want xD */
Tree = (struct node *)malloc(sizeof(struct node));
Tree->inf = 5;
Tree->left = (struct node *)malloc(sizeof(struct node));
Tree->left->inf = 3;
Tree->right = (struct node *)malloc(sizeof(struct node));
Tree->right->inf = 7;
Tree->left->left = (struct node *)malloc(sizeof(struct node));
Tree->left->left->inf = 10;
Tree->left->left->left = NULL;
Tree->left->left->right = NULL;
Tree->left->right = (struct node *)malloc(sizeof(struct node));
Tree->left->right->inf = 8;
Tree->left->right->left = NULL;
Tree->left->right->right = NULL;
Tree->right->left = (struct node *)malloc(sizeof(struct node));
Tree->right->left->inf = 4;
Tree->right->left->left = NULL;
Tree->right->left->right = NULL;
Tree->right->right = NULL;
/* preorder visit to be sure the tree is made correctly */
preorder(Tree);
printf("\n\n");
level_insert(&Tree); // entering a new node
level_visit(Tree); // showing the new tree
level_insert(&Tree); // entering another new node
level_visit(Tree); // level visit test again :D
for(i = 0; i < 10; ++i) {
level_insert(&Tree);
level_visit(Tree);
}
return 0;
}
void level_visit(struct node *a) {
struct queue *testa = NULL, *coda = NULL;
struct node *aus = a;
if(a != NULL) {
inQueue(&testa, &coda, aus);
while(testa != NULL) {
aus = outQueue(&testa, &coda);
printf("%d ", aus->inf);
if(aus->left != NULL)
inQueue(&testa, &coda, aus->left);
if(aus->right != NULL)
inQueue(&testa, &coda, aus->right);
}
}
}
void level_insert(struct node **a) {
struct queue *testa = NULL, *coda = NULL;
struct node *aus = *a;
int flag = 0;
if(*a != NULL) {
inQueue(&testa, &coda, aus);
while(testa != NULL && flag == 0) {
aus = outQueue(&testa, &coda);
if(aus != NULL) {
if(aus->left == NULL || aus->right == NULL) {
if(aus->left == NULL) {
aus->left = (struct node *)malloc(sizeof(struct node));
printf("\nEnter a number: ");
scanf("%d", &(aus->left->inf));
aus->left->left = NULL;
aus->left->right = NULL;
flag = 1;
}
else {
aus->right = (struct node *)malloc(sizeof(struct node));
printf("\nEnter a number: ");
scanf("%d", &(aus->right->inf));
aus->right->left = NULL;
aus->right->right = NULL;
flag = 1;
}
}
else {
inQueue(&testa, &coda, aus->left);
inQueue(&testa, &coda, aus->right);
}
}
else {
aus = (struct node *)malloc(sizeof(struct node));
printf("\nEnter a number: ");
scanf("%d", &(aus->inf));
aus->left = NULL;
aus->right = NULL;
flag = 1;
}
}
}
else {
*a = (struct node *)malloc(sizeof(struct node));
printf("\nEnter a number: ");
scanf("%d", &((*a)->inf));
(*a)->left = NULL;
(*a)->right = NULL;
}
}
void inQueue(struct queue **head, struct queue **tail, struct node *ele) {
struct queue *nuovo = NULL;
nuovo = (struct queue *)malloc(sizeof(struct queue));
nuovo->pointer = ele;
nuovo->next = NULL;
if(*tail != NULL)
(*tail)->next = nuovo;
else
*head = nuovo;
*tail = nuovo;
}
struct node *outQueue(struct queue **head, struct queue **tail) {
struct node *aus = NULL;
aus = (*head)->pointer;
if(*head != NULL) {
*head = (*head)->next;
if(*head == NULL)
*tail = NULL;
}
return aus;
}
void preorder(struct node *p) {
if(p != NULL) {
printf("%d ", p->inf);
preorder(p->left);
preorder(p->right);
}
}