Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement