Advertisement
pasqoo

level_insert

Sep 11th, 2011
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 5.14 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. /* this is going to contain the queue, made of pointers to tree's nodes */
  5. struct queue {
  6.     struct node *pointer;
  7.     struct queue *next;
  8. };
  9.  
  10. /* this represents the tree's nodes */
  11. struct node {
  12.     int inf;
  13.     struct node *left;
  14.     struct node *right;
  15. };
  16.  
  17. void level_insert(struct node **); // enter a new node into the tree keeping it a "complete tree"
  18. void inQueue(struct queue **, struct queue **, struct node *); // push a node into the queue
  19. struct node *outQueue(struct queue **, struct queue **); // pop a node out of the queue
  20. void preorder(struct node *); // tree's preorder visit (just for test purpose)
  21. void level_visit(struct node *); // tree's level visit
  22.  
  23. int main(void) {
  24.     struct node *Tree = NULL;
  25.     int i;
  26.  
  27.     /* I'm making the tree this way to be sure it's made how I want xD */
  28.     Tree = (struct node *)malloc(sizeof(struct node));
  29.     Tree->inf = 5;
  30.  
  31.     Tree->left = (struct node *)malloc(sizeof(struct node));
  32.     Tree->left->inf = 3;
  33.  
  34.     Tree->right = (struct node *)malloc(sizeof(struct node));
  35.     Tree->right->inf = 7;
  36.     Tree->left->left = (struct node *)malloc(sizeof(struct node));
  37.     Tree->left->left->inf = 10;
  38.     Tree->left->left->left = NULL;
  39.     Tree->left->left->right = NULL;
  40.     Tree->left->right = (struct node *)malloc(sizeof(struct node));
  41.     Tree->left->right->inf = 8;
  42.     Tree->left->right->left = NULL;
  43.     Tree->left->right->right = NULL;
  44.     Tree->right->left = (struct node *)malloc(sizeof(struct node));
  45.     Tree->right->left->inf = 4;
  46.     Tree->right->left->left = NULL;
  47.     Tree->right->left->right = NULL;
  48.     Tree->right->right = NULL;
  49.  
  50.     /* preorder visit to be sure the tree is made correctly */
  51.     preorder(Tree);
  52.  
  53.     printf("\n\n");
  54.  
  55.     level_insert(&Tree); // entering a new node
  56.  
  57.     level_visit(Tree); // showing the new tree
  58.  
  59.     level_insert(&Tree); // entering another new node
  60.  
  61.     level_visit(Tree); // level visit test again :D
  62.  
  63.     for(i = 0; i < 10; ++i) {
  64.         level_insert(&Tree);
  65.         level_visit(Tree);
  66.     }
  67.  
  68.     return 0;
  69. }
  70.  
  71. void level_visit(struct node *a) {
  72.     struct queue *testa = NULL, *coda = NULL;
  73.     struct node *aus = a;
  74.  
  75.     if(a != NULL) {
  76.         inQueue(&testa, &coda, aus);
  77.         while(testa != NULL) {
  78.             aus = outQueue(&testa, &coda);
  79.             printf("%d ", aus->inf);
  80.             if(aus->left != NULL)
  81.                 inQueue(&testa, &coda, aus->left);
  82.             if(aus->right != NULL)
  83.                 inQueue(&testa, &coda, aus->right);
  84.         }
  85.     }
  86. }
  87.  
  88. void level_insert(struct node **a) {
  89.     struct queue *testa = NULL, *coda = NULL;
  90.     struct node *aus = *a;
  91.     int flag = 0;
  92.  
  93.     if(*a != NULL) {
  94.         inQueue(&testa, &coda, aus);
  95.         while(testa != NULL && flag == 0) {
  96.             aus = outQueue(&testa, &coda);
  97.             if(aus != NULL) {
  98.                 if(aus->left == NULL || aus->right == NULL) {
  99.                     if(aus->left == NULL) {
  100.                         aus->left = (struct node *)malloc(sizeof(struct node));
  101.                         printf("\nEnter a number: ");
  102.                         scanf("%d", &(aus->left->inf));
  103.                         aus->left->left = NULL;
  104.                         aus->left->right = NULL;
  105.                         flag = 1;
  106.                     }
  107.                     else {
  108.                         aus->right = (struct node *)malloc(sizeof(struct node));
  109.                         printf("\nEnter a number: ");
  110.                         scanf("%d", &(aus->right->inf));
  111.                         aus->right->left = NULL;
  112.                         aus->right->right = NULL;
  113.                         flag = 1;
  114.                     }
  115.  
  116.                 }
  117.                 else {
  118.                     inQueue(&testa, &coda, aus->left);
  119.                     inQueue(&testa, &coda, aus->right);
  120.                 }
  121.             }
  122.             else {
  123.                 aus = (struct node *)malloc(sizeof(struct node));
  124.                 printf("\nEnter a number: ");
  125.                 scanf("%d", &(aus->inf));
  126.                 aus->left = NULL;
  127.                 aus->right = NULL;
  128.                 flag = 1;
  129.             }
  130.         }
  131.     }
  132.     else {
  133.         *a = (struct node *)malloc(sizeof(struct node));
  134.         printf("\nEnter a number: ");
  135.         scanf("%d", &((*a)->inf));
  136.         (*a)->left = NULL;
  137.         (*a)->right = NULL;
  138.     }
  139. }
  140.  
  141. void inQueue(struct queue **head, struct queue **tail, struct node *ele) {
  142.     struct queue *nuovo = NULL;
  143.  
  144.     nuovo = (struct queue *)malloc(sizeof(struct queue));
  145.     nuovo->pointer = ele;
  146.     nuovo->next = NULL;
  147.  
  148.  
  149.     if(*tail != NULL)
  150.         (*tail)->next = nuovo;
  151.  
  152.     else
  153.         *head = nuovo;
  154.  
  155.     *tail = nuovo;
  156.  
  157. }
  158.  
  159. struct node *outQueue(struct queue **head, struct queue **tail) {
  160.     struct node *aus = NULL;
  161.  
  162.     aus = (*head)->pointer;
  163.  
  164.     if(*head != NULL) {
  165.         *head = (*head)->next;
  166.         if(*head == NULL)
  167.             *tail = NULL;
  168.     }
  169.  
  170.     return aus;
  171. }
  172.  
  173. void preorder(struct node *p) {
  174.     if(p != NULL) {
  175.         printf("%d ", p->inf);
  176.         preorder(p->left);
  177.         preorder(p->right);
  178.     }
  179. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement